八大排序算法

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int q[N];
int w[N],s[N];
int n,sz;
//直接插入排序 ,对于某一个元素加入到一个有序的序列中，将该元素依次从该位置开始
//从后往前比较，
//大于该元素的都往后挪一位，直到找到比他小的元素，将该元素插入到比他小的元素的后面。
//
void insert_sort(){for(int i=0;i<n;i++){   // 这里i=1 开始也对int t=q[i],j=i;while(j>0&&q[j-1]>t){swap(q[j],q[j-1]);  // 这里写成q[j]=q[j-1] 也对j--;}q[j]=t;}
}
//折半插入排序 就是在排序的基础上进行二分优化，就是在“将该元素依次从后往前比较”
//这一步中 直接通过二分找到比他小的最大元素 
void binary_search_insert_sort(){for(int i=0;i<n;i++){int t=q[i];if(t>=q[i-1]){q[i]=t;continue;}int l=0,r=i;while(l<r){int mid=l+r>>1;if(q[mid]>t) r=mid;else l=mid+1;}for(int j=i-1;j>=r;j--){q[j+1]=q[j];}q[r]=t;}
}
//冒泡排序  a,b,c,d 从后往前依次做 if c > d 交换二者位置，这样每遍历一次，可以将
//第 i 小的数 放在第i个位置 一共只需要做n-1次。
//y总写的这个是把小的往前冒
//也可以把大的往后冒
void bubble_sort(){for(int i=0;i<n-1;i++){bool has_swap=false;//小优化  如果说当前遍历的过程中，没发生一次交换，说明//当前序列已经是有序的了 可以直接breakfor(int j=n-1;j>i;j--){if(q[j]<q[j-1]) {swap(q[j],q[j-1]);has_swap=true;}}if(!has_swap) break;}
}
//最简单的一集,依次从前往后遍历，每次把后面的最小的一个选出来 放到当前位置。
//总共需要遍历n-1次，因为最后一个位置肯定是符合有序的
void select_sort(){for(int i=0;i<n-1;i++){int k=i;for(int j=i+1;j<n;j++){if(q[j]<q[k]){k=j;}}swap(q[k],q[i]);}
}
//希尔排序:分组+插入排序
void shell_sort(){for(int d=n/3;d;d = d == 2 ? 1 : d / 3){  // 因为希尔排序最后要求公差必须是1//但你每次除三到最后不一定是1 可能是2  2的话我们令公差为1for(int start=0;start<d;start++){for(int i=start+d;i<n;i+=d){int t=q[i],j=i;while(j>start&&t<q[j-d]){swap(q[j],q[j-d]);j=j-d;}q[j]=t;}}}
}
//具体理解 可以参考B站动画演示
void quick_sort(int l,int r){if(l>=r) return;int i=l-1,j=r+1,x=q[(l+r)>>1];while(i<j){do i++;while(q[i]<x);do j--;while(q[j]>x);if(i<j) swap(q[i],q[j]);}quick_sort(l,j);quick_sort(j+1,r);
}
//堆排序要从下标1开始,具体过程可以参考B站动画演示
void down(int t){int u=t;if(u*2<=sz&&q[u*2]>q[t]) t=u*2;if(u*2+1<=sz&&q[u*2+1]>q[t]) t=u*2+1;if(u!=t){ //如果t不是叶子结点 且与儿子结点发生了交换 那么需要递归重新构建儿子的大根堆swap(q[u],q[t]);down(t);//重新构建叶子节点大根堆}
}
void heap_sort(){sz=n;for (int i = n / 2; i; i -- ) down(i);//从最大的非叶子结点开始 将原数组变为一个大根堆for(int i=0;i<n-1;i++){swap(q[1], q[sz]);  // 将堆顶与堆低元素互换 sz -- ;//并且删除堆低元素down(1);//因为发生了交换 破坏了原有的大根堆 需要重新构造大根堆}
}
//归并排序
void merge_sort(int l,int r){if(l>=r) return;int mid=l+r>>1;merge_sort(l,mid),merge_sort(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(q[i]<=q[j]) w[k++]=q[i++];else w[k++]=q[j++];}while(i<=mid) w[k++]=q[i++];while(j<=r) w[k++]=q[j++];for(i=l,j=0;i<=r;i++,j++) q[i]=w[j];
}
void bucket_sort(){for(int i=0;i<n;i++) s[q[i]]++;for(int i=1;i<N;i++) s[i]=s[i]+s[i-1];for(int i=n-1;i>=0;i--) w[--s[q[i]]]= q[i];// 举个例子  5 3 4 1 1 //s[1]=2  则w[--2]=1  也即w[1]=1 第1个位置应该放后一个1 //s[1]=1  则w[--1]=1  也即w[0]=1 第0个位置应该放前一个1 （先后顺序未发生改变稳定！）//s[4]=4  则w[--4]=4  也即w[3]=4 第三个位置应该放4//s[3]=3  则w[--3]=3  也即w[2]=3 第二个位置应该放3//s[5]=5  则w[--5]=5  也即w[4]=5 第四个位置应该放5//倒着排序可以保证稳定性for(int i=0;i<n;i++) q[i]=w[i];
}
int main(){cin >> n;for(int i=0;i<n;i++){cin >> q[i];}//insert_sort();//binary_search_insert_sort();//bubble_sort();//select_sort();//shell_sort();//quick_sort(0,n-1);//heap_sort();//merge_sort(0,n-1);bucket_sort();for(int i=0;i<n;i++){cout << q[i] << " ";}return 0;
}