排序

排序概览

一.快速排序

1. 排序思想

   • 排序区间为[l, r]
     • 如果区间长度小于等于1则直接退出, 否则选一个区间中随机的数字x与l位元素交换作为比较元素
     • 将大于x的数字放在左边, 小于的放在右边,等于的也要换边!!
     • 此时x的位置已经固定, 对两边区域的分别递归
   • 一开始的区间为[1, n]
   • 两个指针分别从l和r开始向中间扫描, 直到相遇结束一次扫描

2. 代码实现

   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); }

3. 补充

   • 实际打比赛可用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, 然后排一半即可

二.归并排序

1. 排序思想
   • 排序区间为[l, r]
     • 如果区间长度为1则直接退出, 否则将区间分为[l, m]和[m+1, r]俩部分, 其中m = ( l + r ) / 2
     • 递归两个子区间进行排序
     • 将两个已经排好的子区间合并
   • 一开始只要对区间[1, n]排序即可
2. 代码实现

   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]; }

三.计数排序

1. 排序思想

   • 统计每个数据出现了几次
   • 统计完每个元素后, 求一遍前缀和, 就知道每个数字在排序完后的序列中出现的位置
   • 把数字填入对应的位置即可

2. 代码实现

   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"); }

3. 补充

   • 适用于值域范围较小的数字排列

四.基数排序

1. 排序思想

   • 拆分成m个关键字, 从后往前对这些关键字排序, 每次排序会使用上一次的排序结果
   • 每一次是用计数排序来实现
   • 假设已经排完了第i个及以后的关键字, 现在要排第i - 1个关键字,这里是一个双关键字排序, 第一关键字是第i - 1个关键字, 第二关键字是第i个及以后的关键字的rank
   • 我们只需要把数字按照第i个及以后的关键字从小到大排序放在数组里, 再进行一次计数排序即可( 因为计数排序是稳定的 )

2. 代码实现

   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(); } }

3. 补充

   • 基数排序经常被用于字符串的排序, 比如说后缀数组的核心就是基数排序