参考课程是我高中信息竞赛邱老师的课程 以及 波波微课。
【10-1排序：冒泡、选择、插入】 https://www.bilibili.com/video/BV14c411q7HA/?share_source=copy_web&vd_source=2c56c6a2645587b49d62e5b12b253dca
【10-2排序：归并、快排、堆排】 https://www.bilibili.com/video/BV1NN411j7JR/?share_source=copy_web&vd_source=2c56c6a2645587b49d62e5b12b253dca
https://space.bilibili.com/518029478?spm_id_from=333.337.0.0
代码部分
快排
选一个pivot 比他小的放一边 通过swap实现 然后再把数周放在合适的地方
合并归并排序
空间n所以必须建 vectmp 两个指针所以ij要用 然后三次while 一佛如
插入排序
j=i-1
选择排序
min
堆排序
要比较当前位置与下面两个子节点的大小因此 必须知道位置 i lr然后比较 如果large为hi变量 那么交换节点
同时递归调用
主函数首先建堆 从n/2-1开始 然后对于删除部分每次交换玩再对话
希尔排序
冒泡排序
二分查找
冒泡排序
时间复杂度：O(n^2)
插入排序
将数组分为已排序和未排序两部分
依次从未排序中取出一个元素，放入已排序中
就是打牌
时间复杂度：O(n)~O(n^2)
空间复杂度：O(1)
选择排序
从未排序区找最小元素，和当前元素交换（双指针，当min≠i时即替换并i++）
时间复杂度：O(n^2) 扫描n n轮
空间复杂度：O(1)
堆排序
建堆
排序：将最大元素取出，将最小元素替换上去（利用删除的性质）
算法复杂度：
空间复杂度O(1)
桶排序 T407375
https://www.luogu.com.cn/problem/T407375
用vector开桶，计算桶的大小，桶大小=max-min+1/N， 然后输入到各个桶，idx=(a[i]-min)/N； if(idx==N) idx=N-1； pushback(a[i])
#include<bits/stdc++.h>
using namespace std;
int N;
int a[100005];
//开N个桶，涉及范围max min，单个桶的大小就是range=max-min+1 / N
int main(){
vector<int> buk[100005];
cin>>N;
int min_n=(int)1e9, max_n=0;
for(int i=0;i<N;i++){
cin>>a[i];
max_n=max(max_n,a[i]);
min_n=min(min_n,a[i]);
}
long long range = (long long)max_n – min_n + 1;
double bk_size = (double)range / N;
for(int i=0;i<N;i++){
int idx=(a[i]-min_n)/bk_size;//落入区间是当前值-最小值/桶大小
if(idx >= N) idx = N – 1;
buk[idx].push_back(a[i]);
}
for(int i=0;i<N;i++){
//对各个桶排
sort(buk[i].begin(),buk[i].end());
for(int x:buk[i]){
cout<<x<<" ";
}
}
}
