1. 冒泡排序
// 朴素冒泡void bubble_sort_1(int n) { // 总共需要排序 n-1轮 for(int i=n-1; i>=1; i--) { for(int j=0; j s[j+1]) swap(s[j], s[j+1]); } }}// 带优化的冒泡void bubble_sort_2(int n) { for(int i=n-1; i>=1; i--) { // 标记是否有序 bool f = false; for(int j=0; j s[j+1]) swap(s[j], s[j+1]), f=true; } // 说明没有发生交换 if(!f) break; }} 2. 快速排序
void quick_sort(int l, int r) { if(l >= r) return ; int i=l, j=r; int num = s[l]; while(i < j) { // 从右面找比num小的 while(i < j && s[j] > num) j--; // 从左面找比num大的 while(i < j && s[i] < num) i++; // 交换 if(i < j) swap(s[i], s[j]); } quick_sort(l, j-1); quick_sort(j+1, r);} 3. 插入排序
void insert_sort(int n) { // s[0]已经排序排好了 for(int i=1; i<=n-1; i++) { int j = i-1; // j+1 即为要插的位置 while(j >= 0 && s[j] > s[i]) j--; int tmp = s[i]; for(int k=i-1; k>=j+1; k--) s[k+1] = s[k]; s[j+1] = tmp; } return ;}// 代码优化版本void insert_sort(int n) { // s[0]已经排序排好了 for(int i=1; i<=n-1; i++) { int j = i-1; // j+1 即为要插的位置 int tmp = s[i]; while(j >= 0 && s[j] > tmp) { s[j+1] = s[j]; j--; } s[j+1] = tmp; } return ;} 4. 希尔排序
void shell_sort(int n) { for(int gap = (n>>1); gap; gap>>=1) { // 共分gap个组 for(int i=0; i = i && s[k] > tmp) { s[k+gap] = s[k]; k-=gap; } s[k+gap] = tmp; } } }} 5. 选择排序
void select_sort(int n) { // 共n-1轮次 for(int i=0; i 6. 堆排序
这里比较trick的点就是,就是比如小根堆，根节点是最小的，因此呢，在排序的时候，s[0]和s[n]交换一下，排序结果就是从大到小的。
想要从小到大的排序结果，需要用大根堆。// 对堆从st调整， 数组元素为nvoid heap_down(int st, int n) { int c = st; // 有左儿子 while(2*c+1 <= n) { int l = 2*c+1; int mn = c; if(s[mn] > s[l]) mn = l; if(l+1 <= n && s[mn] > s[l+1]) mn = l+1; if(mn == c) break; swap(s[c], s[mn]); c = mn; } return ;}void heap_sort(int n) { for(int i=n/2; i>=0; i--) heap_down(i,n); for(int i=n; i>0; i--) { swap(s[i], s[0]); heap_down(0, i-1); } return ;} 7. 归并排序
void merge_sort(int l,int r) { if(l >= r) return ; int mid = (l+r)/2; merge_sort(l, mid); merge_sort(mid+1, r); int l1=l, l2=mid+1; int k = l; while(l1 <= mid && l2 <= r) { if(s[l1] > s[l2]) t[k++] = s[l2++]; else t[k++] = s[l1++]; } while(l1 <= mid) t[k++] = s[l1++]; while(l2 <= r) t[k++] = s[l2++]; for(int i=l; i<=r; i++) s[i] = t[i]; return ;} 8. 分桶排序
void bubble_sort(int n) { for(int i=0; i 9. 基数排序
int get_max(int n) { int mx = INT_MIN; for(int i=0; i =0; i--) { output[bucket[(s[i]/exp)%10]-1] = s[i]; bucket[(s[i]/exp)%10]--; } for(int i=0; i 0; exp *= 10) { count_sort(n,exp); }}