知识总结
排序算法
排序算法的稳定性
稳定性：排序前后，两相等元素的相对位置是否有变，若不变，则为稳定的，否则为不稳定。
注：排序算法是否稳定取决于具体算法的实现（比如冒泡排序交换条件要不要取等），不稳定的算法在某种条件下可转变为稳定的，稳定的算法也可以在某种条件下转变为不稳定的。
排序算法复杂度稳定性分析
选择排序
思想
每次把最大（小）的数选出来交换到最前面。即每次从头到尾扫描序列，找出待排序序列中最小的一个交换到最前面，不断重复直到整个序列都有序。
代码实现使用双层循环，外层循环遍历待排序序列的第一个数，范围：1 ~ n-1，内层循环遍历待排序序列第一个数起后面的所有数，范围：i+1 ~ n，每轮打擂台找出当前待排序序列中的一个最小值交换到最前面。
代码
for(int i = 1; i <= n - 1; i++){ // i: 遍历待排序序列第一个位置
for(int j = i + 1; j <= n; j++){ // j: 遍历待排序序列后面的每个值
if(a[j] < a[i]){ // 如果发现后面有更小的数
swap(a[i], a[j]); // 交换到待排序序列第一个位置
}
}
}
冒泡排序
思想
每次检查相邻两个元素，如果发现前面的元素比后面的元素大（即构成逆序对），就交换这两个元素。当序列中不再存在逆序对时，排序完成。
由于在算法的执行过程中，较大（或较小）的元素像是气泡般慢慢「浮」到数列的顶端，故叫做冒泡排序。
代码
for(int i = 1; i <= n - 1; i++){ // i: 冒泡轮数，总共 n - 1 轮
for(int j = 1; j <= n - i; j++){ // j: 每轮冒泡要比较的相邻元素对数
if(a[j] > a[j + 1]){ // 如果发现相邻元素是逆序对
swap(a[j], a[j + 1]); // 交换逆序对
}
}
}
插入排序
思想
将待排列元素划分为「已排序」和「待排序」两部分，每次从「待排序」的元素中选择一个插入到「已排序」中的正确位置。
一开始，把序列的第一个元素归为「已排序」序列，剩下元素归为「待排序」序列。那么操作就可以从第二个数开始到最后一个。
在实现过程中，每次选择无序序列第一个数作为元素插入到有序序列中扩展有序序列长度，将待插入元素依次与有序序列中元素进行比较，若发现插入元素比某位置的值小，我们就把有序序列的数从这个位置开始依次后移一位，腾出空给取出来的数，插入该数。
代码
for(int i = 2; i <= n; i++){ // 初始假设第一个元素是有序的，无序起点从 a[2] 开始
int x = a[i], j = i - 1; // 将 a[i] 插入到 a[1] ~ a[i-1] 中，要暂存 a[i] 的值
for( ; j >= 1 && a[j] > x; j--){ // 将有序序列中比 a[i] 大的元素依次后移
a[j + 1] = a[j];
}
a[j + 1] = x; // 将 a[i] 插入在 j 停下来时后面空出的位置
}
计数排序（桶排序）
思想
桶排序是基于开桶思想的一种排序方法。实现思路非常简单，先开桶把所有元素都入桶，然后从小到大遍历所有的桶，把桶内元素出桶即可。
代码
int n, x, a[maxn]; // maxn：数据范围最大值 + 5
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> x;
a[x]++;
}
for(int i = 1; i <= maxn; i++){ // i: 遍历数据范围
for(int j = 1; j <= a[i]; j++){ // j: 遍历 i 出现的次数
cout << i << " ";
}
}
return 0;
}
归并排序
思想
代码
int n, a[maxn], b[maxn];
void mergeSort(int l, int r){ // 对 [l,r] 归并排序
if(l == r) return; // 边界：只有一个元素
int mid = (l + r) / 2;
mergeSort(l, mid);
mergeSort(mid + 1, r);
int p1 = l, p2 = mid + 1, p = l;
while(p1 <= mid && p2 <= r){
if(a[p1] < a[p2]){ // 左比右小，选左边
b[p++] = a[p1++];
}
else{ // 左比右大，选右边
b[p++] = a[p2++];
}
}
while(p1 <= mid){
b[p++] = a[p1++];
}
while(p2 <= r){
b[p++] = a[p2++];
}
for(int i = l; i <= r; i++){ // 将 l ~ r 拷贝回 a[]
a[i] = b[i];
}
}
快速排序
思想
以序列第一个数（也可以用其他方法选这个数）作为基准，把数组中小于基准数的数放在左半边，大于基准数的放在右半，基准数放在中间。当每个基准数最终位置都确定时，排序完成。
代码
int n, a[maxn];
void quickSort(int l, int r){ // 对 [l,r] 快速排序
if(l >= r) return; // 边界：l >= r
int p = a[l], i = l, j = r;
while(i < j){ // 左右指针相遇前，查找逆序对交换
while(i < j && a[j] >= p) j--; // 从左往右找 < 枢纽的数
while(i < j && a[i] <= p) i++; // 从右往左找 > 枢纽的数
swap(a[i], a[j]); // i 和 j 各自停下时交换逆序对
}
swap(a[i], a[l]); // i == j 停止时(a[i] <= a[l])，i 即为枢纽 a[l] 的最终位置
quickSort(l, i - 1); // 递归快排左边
quickSort(i + 1, r); // 递归快排右边
}
堆排序（了解）
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为 O(nlogn)，它也是不稳定排序。
堆排序主要由 构建初始堆 + 交换堆顶元素和末尾元素并重建堆 两部分组成。其中构建初始堆经推导复杂度为 O(n)，在交换并重建堆的过程中，需交换 n-1 次，而重建堆的过程中，根据完全二叉树的性质，近似为 nlogn。所以堆排序时间复杂度一般认为就是 O(nlogn)。
希尔排序（了解）
希尔排序是插入排序的一种改进版本，也称为“缩小增量排序”（Diminishing Increment Sort），是 不稳定 的排序算法。、希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
- 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列（由相隔某个“增量”的记录组成的）分别进行直接插入排序，
- 然后依次缩减增量再进行排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
STL 中排序相关的函数
排序：sort(begin, end, compare)
begin 和 end 分别为待排序数组的首地址和尾地址；compare 表示排序的比较函数，可省略不填。
默认为升序，若要降序，可在第三个参数处填入 greater<int>()。sort 排序采用的是成熟的“快速排序算法”，可以保证很好的平均性能，其时间复杂度为 O(nlogn)。
稳定排序：stable_sort (begin, end, compare)
stable_sort() 能保持相等元素的相对顺序在排序前后一致。即使原来相同的值在序列中的相对位置不变。例如初始序列中有两个元素 A 和 B 的值相等，且 A 排在 B 的前面，排序后 A 仍然排在 B 的前面，这种排序叫作稳定排序。
去重：unique(begin, end)
将区间 [begin,end) 中的连续相同元素进行去重，返回去重后的尾指针（减去数组名可获得元素个数）。
不连续的相同元素不会被压缩去重，因此一般先排序后去重。
初赛真题
单选题
- 以下排序算法的常见实现中，哪个选项的说法是错误的：（ ）。
- A. 冒泡排序算法是稳定的
- B. 简单选择排序是稳定的
- C. 简单插入排序是稳定的
- D. 归并排序算法是稳定的
- 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少 1 个逆序对，因此序列 5，4，3，2，1 需要执行（ ）次操作，才能完成冒泡排序。
- A. 0
- B. 5
- C. 10
- D. 15
- 体育课的铃声响了，同学们都陆续地奔向操场，按老师的要求从高到矮站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法。
- A. 快速排序
- B. 插入排序
- C. 冒泡排序
- D. 归并排序
- 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少 1 个逆序对，因此序列 5，4，3，2，1 需要执行（ ）次操作，才能完成冒泡排序。
- A. 0
- B. 5
- C. 10
- D. 15
- ( ) 的平均时间复杂度为 O(nlogn)，其中 n 是待排序的元素个数。
- A. 快速排序
- B. 插入排序
- C. 冒泡排序
- D. 基数排序
- 对于给定的序列 {a1，a2，… an} 我们把 (i, j) 称为逆序对当且仅当 i
aj。那么 序列 {1, 7, 2, 3, 5, 4 } 的逆序对数为（ ）个。 - A. 4
- B. 5
- C. 6
- D. 7
- 设 A 和 B 是两个长为 n 的有序数组，现在需要将 A 和 B 合并成一个排好序的数组，任何以元素比较作为基本运算的归并算法在最坏情况下至少要做（ ）次比较。
- A. n^2
- B. nlogn
- C. 2n
- D. 2n-1
- 以下排序算法中，不需要进行关键字比较操作的算法是（ ）。
- A. 基数排序
- B. 冒泡排序
- C. 堆排序
- D. 直接插入排序
完善程序
（计数排序）计数排序是一个广泛使用的排序方法。下面的程序使用双关键字计数排序，将 n 对 10000 以内的整数，从小到大排序。
例如有三对整数 (3,4)、(2,4)、(3,3)，那么排序之后应该是 (2,4)、(3,3)、(3,4) 。 输入第一行为 n 接下来 n 行，第 i 行有两个数 a[i] 和 b[i]，分别表示第 i 对整数的第一关键字和第二关键字。 从小到大排序后输出。 数据范围 1<n<10^7, 1<a[i],b[i]<10^4。
提示：应先对第二关键字排序，再对第一关键字排序。数组 ord[] 存储第二关键字排序的结果，数组 res[] 存储双关键字排序的结果。 试补全程序。
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 10000000;
const int maxs = 10000;
int n;
unsigned a[maxn], b[maxn], res[maxn], ord[maxn];
unsigned cnt[maxs + 1];
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d%d", &a[i], &b[i]);
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; ++i)
// ①利用 cnt 数组统计数量
for(int i = 0; i < maxs; ++i)
cnt[i + 1] += cnt[i];
for(int i = 0; i < n; ++i)
// ②记录初步排序结果
memset(cnt, 0, sizeof(cnt));
for(int i = 0; i < n; ++i)
// ③利用 cnt 数组统计数量
for(int i = 0; i < maxs; ++i)
cnt[i + 1] += cnt[i];
for(int i = n - 1; i >= 0; --i)
// ④记录最终排序结果
for(int i = 0; i < n; i++)
printf("%d %d", ⑤);
return 0;
}
- ① 处应填（）
A. ++cnt [i]
B. ++cnt[b[i]]
C. ++cnt[a[i] * maxs + b[i]]
D. ++cnt[a[i]]
- ② 处应填（）
A. ord[–cnt[a[i]]] = i
B. ord[–cnt[b[i]]] = a[i]
C. ord[–cnt[a[i]]] = b[i]
D. ord[–cnt[b[i]]] = i
- ③ 处应填（）
A. ++cnt[b[i]]
B. ++cnt[a[i] * maxs + b[i]]
C. ++cnt[a[i]]
D. ++cnt [i]
- ④处应填（）
A. res[–cnt[a[ord[i]]]] = ord[i]
B. res[–cnt[b[ord[i]]]] = ord[i]
C. res[–cnt[b[i]]] = ord[i]
D. res[–cnt[a[i]]] = ord[i]
- ⑤ 处应填（）
A. a[i], b[i]
B. a[res[i]], b[res[i]]
C. a[ord[res[i]]], b[ord[res[i]]]
D. a[res[ord[i]]], b[res[ord[i]]]
经典例题
排序
思路
要排序的数据量达到了 10^5，可以手写快排或归并排序通过，使用 sort() 也可以。
代码-1：归并排序 merge_sort()
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, a[maxn], b[maxn];
void mergeSort(int l, int r){ // 对 [l,r] 归并排序
if(l == r) return;
int mid = (l + r) >> 1; // 计算中间点下标
mergeSort(l, mid); // 归并排序左半区间
mergeSort(mid + 1, r); // 归并排序右半区间
int p1 = l, p2 = mid + 1, p3 = l;
while(p1 <= mid && p2 <= r){ // 合并两半区间
if(a[p1] < a[p2]){
b[p3++] = a[p1++];
}
else{
b[p3++] = a[p2++];
}
}
while(p1 <= mid){
b[p3++] = a[p1++];
}
while(p2 <= r){
b[p3++] = a[p2++];
}
for(int i = l; i <= r; i++){
a[i] = b[i];
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
mergeSort(1, n);
for(int i = 1; i <= n; i++){
printf("%d ", a[i]);
}
return 0;
}
代码-2：快速排序 quick_sort()
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, a[maxn];
void quickSort(int l, int r){ // 对 [l,r] 快速排序
if(l >= r) return; // 边界：l >= r
int p = a[l], i = l, j = r;
while(i < j){ // 左右指针相遇前，查找逆序对交换
while(i < j && a[j] >= p) j--; // 从左往右找 < 枢纽的数
while(i < j && a[i] <= p) i++; // 从右往左找 > 枢纽的数
swap(a[i], a[j]); // i 和 j 各自停下时交换逆序对
}
swap(a[i], a[l]); // i == j 停止时(a[i] <= a[l])，i 即为枢纽 a[l] 的最终位置
quickSort(l, i - 1); // 递归快排左边
quickSort(i + 1, r); // 递归快排右边
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
quickSort(1, n);
for(int i = 1; i <= n; i++){
printf("%d ", a[i]);
}
return 0;
}
代码-3：sort()
#include <bits/stdc++.h>
using namespace std;
int n, a[100005];
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
// a[1] ~ a[n] n 个数
sort(a + 1, a + 1 + n); // 默认从小到大排
for(int i = 1; i <= n; i++){
printf("%d ", a[i]);
}
return 0;
}
求第 k 小的数
思路
因为快速排序的每一轮都能确定一个枢纽元素的最终位置，因此可以根据这个位置和 k 的大小比较更新下轮排序区间：
- 若枢纽元素位置 i 就是第 k 位，返回该元素的值；
- 若 k < i，说明第 k 小的数在当前枢纽元素的左边，递归求解区间 [l, i – 1];
- 若 k > i, 说明第 k 小的数在当前枢纽元素的右边，递归求解区间 [i + 1, r];
代码
#include <bits/stdc++.h>
#define maxn 5000005
using namespace std;
/*
*/
int n, k, a[maxn], ans;
int findk(int l, int r){ // 对 [l,r] 快速排序
int p = a[l], i = l, j = r;
while(i < j){ // 左右指针相遇前，查找逆序对交换
while(i < j && a[j] >= p) j--; // 从左往右找 < 枢纽的数
while(i < j && a[i] <= p) i++; // 从右往左找 > 枢纽的数
swap(a[i], a[j]); // i 和 j 各自停下时交换逆序对
}
swap(a[i], a[l]); // i == j 停止时(a[i] <= a[l])，i 即为枢纽 a[l] 的最终位置
if(i == k) return a[i];
if(k <= i - 1) return findk(l, i - 1);
if(k >= i + 1) return findk(i + 1, r);
}
int main(){
scanf("%d %d", &n, &k);
k += 1; // 最小的数是第 0 小
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
printf("%d", findk(1, n));
return 0;
}
逆序对
思路
用归并排序求解逆序对。抓住归并排序的特点，在进行 “并” 的时候，左右两半边数组都是局部有
序的状态了，换句话说，单独某半边的数组里是不会存在逆序对的，一定是左半边的元素与右半边的元
素构成了逆序对。
找到左半边第一个与右半边元素 a[p2] 构成逆序对的元素位置，设为 p1 ，而 p1 后的数都比
a[p1] 大，因此易知，左半 a[p1] … a[mid] 都与 a[p2] 构成逆序对，由此计算出当前 a[p2] 构成的逆序
对个数 (mid – p1 + 1)，累加到最终答案上。
注意数据会比较大，逆序对个数开 long long。
代码
#include <bits/stdc++.h>
#define maxn 500005
using namespace std;
int n, a[maxn], b[maxn];
long long ans;
void mergeSort(int l, int r){ // 对 [l,r] 归并排序
if(l == r) return; // 边界：只有一个元素
int mid = (l + r) / 2;
mergeSort(l, mid);
mergeSort(mid + 1, r);
int p1 = l, p2 = mid + 1, p = l;
while(p1 <= mid && p2 <= r){
if(a[p1] <= a[p2]){ // 左比右小，选左边
b[p++] = a[p1++];
}
else{ // 左比右大，选右边，此时构成逆序对
ans += (mid - p1 + 1); // 从 p1 ~ mid 有 mid-p1+1 个元素与 a[p2] 构成逆序对
b[p++] = a[p2++];
}
}
while(p1 <= mid){
b[p++] = a[p1++];
}
while(p2 <= r){
b[p++] = a[p2++];
}
for(int i = l; i <= r; i++){ // 将 l ~ r 拷贝回 a[]
a[i] = b[i];
}
}
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
mergeSort(1, n);
printf("%lld", ans);
return 0;
}
货仓选址
思路
要在数轴上选择一个点，使得该点到所有商店的距离之和最小，可以先对所有商店位置进行排序，排序后最中间的位置就是最优解，计算每个点到该点距离的绝对值累加总和就是答案。
代码
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n, a[maxn];
long long ans;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
sort(a + 1, a + 1 + n);
int x = a[(1 + n) / 2]; // 选择中位数所在位置
for(int i = 1; i <= n; i++) {
ans += abs(a[i] - x);
}
printf("%lld", ans);
return 0;
}
[NOIP2006 普及组] 明明的随机数
思路
先排序再去重，可以使用 sort() 和 unique() 完成。
代码
#include <bits/stdc++.h>
#define maxn 105
using namespace std;
int n, a[maxn], k;
int main(){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
sort(a + 1, a + 1 + n);
k = unique(a + 1, a + 1 + n) - (a + 1);
printf("%d\n", k);
for(int i = 1; i <= k; i++){
printf("%d ", a[i]);
}
return 0;
}
[CSP-J2020] 直播获奖
思路
看题目数据范围，n 最大到 10^5，因此若每读入一个数使用 sort() 排序一次算排位肯定会超时。但是分数范围是 600，因此可以对分数用开桶思想计数每个分出现次数，从高分到低分遍历进行获奖名额分配，每次名额分配完结束时的分数就是即时的获奖分数线。
代码
#include <bits/stdc++.h>
using namespace std;
int n, w, a[100005];
int t, b[605];
int main(){
cin >> n >> w;
for(int i = 1; i <= n; i++){
cin >> t;
b[t]++; // b[t] 记录分数为 t 的人的个数
int s = max(1, i * w / 100); // 人数为 i 时的获奖人数
for(int j = 600; j >= 0; j--){ // 从高到低分配获奖名额
s -= b[j]; // 获奖总人数 减去分数为 j 的人数
if(s <= 0){ // 若减完后 刚刚好 或 人数不够分配
cout << j << " "; // 输出此时的分数 j
break; // 跳出内层循环
}
}
}
return 0;
}
[NOIP2009 普及组] 分数线划定
思路
自定义排序规则对学生按成绩从大到小排序，找到排名第 m 位为分数线，但由于可能有重分，还要加上分数线同分的人数才是最后进入面试的总人数，最后从高到低输出选手信息。
代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
struct P{
int k, s;
};
bool cmp(P x, P y){
if(x.s == y.s) // 成绩等时
return x.k < y.k; // 报名号小优先
return x.s > y.s; // 成绩高优先
}
int main(){
cin >> n >> m;
m = 1.5 * m; // 排名第 m 位为分数线
P a[5005];
for(int i = 1; i <= n; i++)
cin >> a[i].k >> a[i].s;
sort(a + 1, a + 1 + n, cmp);
int s1 = a[m].s; // 面试分数线
while(a[m].s == a[m + 1].s) m++; // 加上同分的人数
cout << s1 << " " << m << "\n";
for(int i = 1; i <= m; i++){
cout << a[i].k << " " << a[i].s << "\n";
}
return 0;
}
[NOIP1998 提高组] 拼数
思路
考虑两个字符串数字 x 和 y，它们组合后的情况只有 x + y 和 y + x 两种且是等长的，那么若想使得组合之后数字尽可能大，就看哪一种字典序更大就更优先排前面。因此可自定义 cmp 排序规则，返回字典序更大的优先排列顺序。最后按排序后顺序依次输出数字即可。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
string a[25];
bool cmp(string x, string y){
return x + y > y + x; // 返回字典序更大的优先排列顺序
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a + 1, a + 1 + n, cmp);
for(int i = 1; i <= n; i++) {
cout << a[i];
}
return 0;
}
[CSP-J 2021] 插入排序
思路
直接模拟，操作 1 就修改 a[x] = v，操作 2 求解 a[x] 排序后的位次，可以先假设其下标 x 就是它的位次。
然后遍历 x 之前的数，每找到一个更大的，意味着位次要减 1，再遍历 x 之后的数，每找到一个更小的，意味着位次要加 1，最后输出调整后的位次即可。
代码
#include <bits/stdc++.h>
#define maxn 8005
using namespace std;
int n, q, a[maxn];
int main(){
scanf("%d %d", &n, &q);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
while(q--){
int op, x, v;
scanf("%d %d", &op, &x);
if(op == 1){ // 将 a[x] 改为 v
scanf("%d", &v);
a[x] = v;
}
else{ // 求原 a[x] 排序后新位置
int p = x; // 假设 a[x] 排名在 x
for(int i = 1; i < x; i++){
if(a[i] > a[x]) p--; // 发现前面有更大的，p 要减 1
}
for(int i = n; i > x; i--){ // 发现后面有更小的，p 要加 1
if(a[i] < a[x]) p++;
}
printf("%d\n", p);
}
}
return 0;
}