排序算法（快排、归并、计数、基数排序）

排序排序概览排序方法时间复杂度平均时间复杂度最坏稳定性快速排序nlognn方不稳定归并排序nlognnlogn稳定计数排序nknk稳定基数排序n kn k稳定堆排序nlognnlogn不稳定选择排序n方n方不稳定冒泡排序n方n方稳定插入排序n方n方稳定一.快速排序排序思想排序区间为[l, r]如果区间长度小于等于1则直接退出, 否则选一个区间中随机的数字x与l位元素交换作为比较元素将大于x的数字放在左边, 小于的放在右边,等于的也要换边!!此时x的位置已经固定, 对两边区域的分别递归一开始的区间为[1, n]两个指针分别从l和r开始向中间扫描, 直到相遇结束一次扫描代码实现void quicksort(int l,int r){ if(l r) return; swap(a[l], a[l rand() % (r - l 1)]); int x a[l]; int i l, j r; while(i j){ while(i j a[j] x) j--; if(i j) a[i] a[j]; while(i j a[i] x) i; if(i j) a[j--] a[i]; } a[i] x; quicksort(l, i - 1); quicksort(i 1, r); }补充实际打比赛可用sort()函数, 可以直接快排对于多关键字排序可以重构比较符号struct Node{ int x, y; bool operator (const Node A) const{ if(x ! A.x) return x A.x; return y A.y; } } a[N 1];找第k小的数用快排, 每一轮只要比较i和k, 然后排一半即可二.归并排序排序思想排序区间为[l, r]如果区间长度为1则直接退出, 否则将区间分为[l, m]和[m1, r]俩部分, 其中m ( l r ) / 2递归两个子区间进行排序将两个已经排好的子区间合并一开始只要对区间[1, n]排序即可代码实现void mergesort(int l,int r){ if(l r) return; int m (l r) / 2; mergesort(l, m); mergesott(m 1, r); int p1 l, p2 m 1, tot 0; while(p1 m p2 r){ if(a[p1] a[p2]) c[tot] a[p1]; else c[tot] a[p2]; } while(p1 m) c[tot] a[p1]; while(p2 r) c[tot] a[p2]; for(int i 1; i tot; i) a[i l - 1] c[i]; }三.计数排序排序思想统计每个数据出现了几次统计完每个元素后, 求一遍前缀和, 就知道每个数字在排序完后的序列中出现的位置把数字填入对应的位置即可代码实现int n, m, a[N 1], c[M 1], r[N 1]; inline void countingsort(){ memset(c, 0, sizeof(c)); for(int i 1; i n; i) c[a[i]]; for(int i 1; i m; i){ for(int j 1; j c[i]; j) printf(%d, r[i]); } printf(\n); for(int i 2; i m; i) c[i] c[i-1]; for(int i n; i; --i) r[i] c[a[i]]--; for(int i 1; i n; i) printf(%d, r[i]); printf(\n); }补充适用于值域范围较小的数字排列四.基数排序排序思想拆分成m个关键字, 从后往前对这些关键字排序, 每次排序会使用上一次的排序结果每一次是用计数排序来实现假设已经排完了第i个及以后的关键字, 现在要排第i - 1个关键字,这里是一个双关键字排序, 第一关键字是第i - 1个关键字, 第二关键字是第i个及以后的关键字的rank我们只需要把数字按照第i个及以后的关键字从小到大排序放在数组里, 再进行一次计数排序即可( 因为计数排序是稳定的 )代码实现int n, m, a[N 1], sa[N 1], v[N 1], r[N 1], c[M 1]; inline void countingsort(){ memset(c, 0, sizeof(c)); for(int i 1; i n; i) c[a[i]]; for(int i 2; i m; i) c[i] c[i-1]; for(int i n; i; --i) r[sa[i]] c[v[sa[i]]]--; for(int i 1; i n; i) sa[r[i]] i; } inline void radisort(){ for(int i 1; i n; i) sa[i] i; int x 1; for(int i 1; i m; i, x*10){ for(int j 1; j n; j) v[j] a[j] / x % 10; countingsort(); } }补充基数排序经常被用于字符串的排序, 比如说后缀数组的核心就是基数排序