当前位置：首页 > news >正文

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

news 2026/7/23 2:33:59

排序

排序概览

排序方法	时间复杂度（平均）	时间复杂度（最坏）	稳定性
快速排序	nlogn	n方	不稳定
归并排序	nlogn	nlogn	稳定
计数排序	*n+k*	*n+k*	稳定
基数排序	*n k*	*n k*	稳定
堆排序	nlogn	nlogn	不稳定
选择排序	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]和[m+1, 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(); } }