C++ 算法竞赛中的排序算法
算法背景
对于给定的由整数组成的长度为
n
n
n 的数组
a
a
a，将其重新排列顺序，变成从左到右**非递减**的数组。
非递减： 即对于排序好的数组中的每一个元素
a i ( 1 < i ⩽ n ) a_i\;(1<i\leqslant n) ai(1<i⩽n)，都有 a i ⩾ a i − 1 a_i \geqslant a_{i-1} ai⩾ai−1。非递增： 即对于排序好的数组中的每一个元素
a i ( 1 < i ⩽ n ) a_i\;(1<i\leqslant n) ai(1<i⩽n)，都有 a i ⩽ a i − 1 a_i \leqslant a_{i-1} ai⩽ai−1。除特殊说明外，如下介绍算法的算法流程默认均为排序成非递减的。
排序算法的稳定性：若在某个排序算法完成后，数组中的值相同的元素的相对位置不变，则称使用的排序算法是稳定的；反之，则称所使用的的排序算法是不稳定的。
冒泡排序Bubble Sort
算法流程
设数组中后
i
+
1
∼
n
i+1\sim n
i+1∼n 项元素已经排序成整个数组中的第
i
+
1
∼
n
i+1 \sim n
i+1∼n 大的元素，设指针
j
=
1
j=1
j=1。
执行以下操作：
- 若 a j > a j + 1 a_j>a_{j+1} aj>aj+1，则将这两项元素交换；
- 若 j = i j=i j=i，则停止，否则令 j = j + 1 j=j+1 j=j+1。
对于
i
=
n
∼
1
i=n \sim 1
i=n∼1 都执行一次该**算法流程**，即可完成排序。
特殊地，对于
i = n i=n i=n，数组内并没有所谓第 n + 1 n+1 n+1 项元素，但这不影响算法的实现。
算法的正确性与稳定性
正确性：
该算法流程保证了数组中的前
1
∼
i
1 \sim i
1∼i 项中的**最大值**移动到数组的第
i
i
i 个位置，故该算法是正确的。
就像所有数字都沉于水中，而每次最大的数字都会『咕咕冒泡』般地浮上来，因此该算法被称为冒泡排序Bubble Sort。
稳定性：
当遇到相同值的元素时，该算法并不交换两项元素的顺序，故该算法是稳定的。
C++ 代码实现
voidBubble_Sort(vector<int>&a){int n = a.size();for(int i = n -1; i >=0;--i){for(int j =0; j < i;++j){if(a[j]> a[j +1]){swap(a[j], a[j +1]);}}}}
如果读者不熟悉
vector，可以把它想象成一个不定长的动态数组，而
a.size()是返回
a这个不定长数组长度的值的函数。
- 代码第 1 1 1 行，
vector<int> &a有两个目的：
- 防止
a的改变只在函数内，并不实际改变a；- 防止程序复制一遍
a，降低代码效率。
- 由于
vector的下标从 0 0 0 开始，故下标可能与算法流程描述有所不同。- 算法流程体现在代码中的：
- 代码第 5 ∼ 6 5 \sim 6 5∼6 行即为算法流程的第 1 1 1 步；
- 代码第 4 4 4 行，
for循环的终止条件为j=i，若不终止则执行++j，即 j = j + 1 j=j+1 j=j+1，体现了算法流程的第 2 2 2 步。使用方法：
- 传入想要排序的
vector a即可，函数会将a自动排序成非递减的。- 如果想要排序成非递增的，则将代码第 5 5 5 行的
if判断语句内的条件改为a[j]<a[j+1]即可。- 需要引用的头文件和命名空间：
#include<vector>#include<algorithm>usingnamespace std;
算法的时间复杂度
代码由两层
for
循环组成，每层的最坏循环次数为
n
n
n 次，其中
n
n
n 为数组内的元素个数，故该算法的时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。
算法拓展
冒泡排序Bubble Sort的交换次数
Q：在冒泡排序Bubble Sort中，两项元素的交换次数总共为多少次？
A：交换次数为逆序对的数量。
逆序对：
- 在排序要求是非递减的情况下，对于原始数组中的两个不同的元素 a i , a j a_i,a_j ai,aj，若 a i > a j a_i>a_j ai>aj，则称 ( a i , a j ) (a_i,a_j) (ai,aj) 为 1 1 1 对逆序对；
- 在排序要求是非递增的情况下，对于原始数组中的两个不同的元素 a i , a j a_i,a_j ai,aj，若 a i < a j a_i<a_j ai<aj，则称 ( a i , a j ) (a_i,a_j) (ai,aj) 为 1 1 1 对逆序对；
证明：
对于算法流程的第 1 1 1 步来说，若 a j > a j + 1 a_j>a_{j+1} aj>aj+1，则说明 ( a j , a j + 1 ) (a_j,a_{j+1}) (aj,aj+1) 是 1 1 1 对逆序对，经过交换后，则这 1 1 1 对逆序对就消除了；
但是对于数组 1 ∼ j − 1 1\sim j-1 1∼j−1 和 j + 2 ∼ n j+2 \sim n j+2∼n 项来说， a j , a j + 1 a_j,;a_{j+1} aj,aj+1 与它们之间的相对位置没有改变，故只会减少这 1 1 1 对逆序对；
所以只要存在逆序对，冒泡排序Bubble Sort就不应该停止，但每次交换只会消除 1 1 1 对逆序对，故冒泡排序Bubble Sort的交换次数为逆序对的数量。
□ \Box□
归并排序Merge Sort
算法流程
设当前数组
a
a
a 中需要排序的范围为
[
l
,
r
]
[l,r]
[l,r]，令
m
i
d
=
⌊
l
+
r
2
⌋
mid=\left\lfloor \frac{l+r}{2}\right \rfloor
mid=⌊2l+r⌋。
先对
[
l
,
m
i
d
]
,
[
m
i
d
+
1
,
r
]
[l,mid],\;[mid+1,r]
[l,mid],[mid+1,r] 两部分执行该**算法流程**，保证数组
a
a
a 的
[
l
,
m
i
d
]
,
[
m
i
d
+
1
,
r
]
[l,mid],\;[mid+1,r]
[l,mid],[mid+1,r] 两部分在自身范围内都是非递减的。
也就是说，先假定算法流程能够实现怎样的功能，再去谈算法流程如何具体实现。
令
i
=
l
,
j
=
m
i
d
+
1
,
p
=
0
i=l,\;j=mid+1,\;p=0
i=l,j=mid+1,p=0，再定义一个长度为
r
−
l
+
1
r-l+1
r−l+1 的空的临时数组
t
t
t 执行以下操作：
[ l , r ] [l,r] [l,r] 的数组 a a a 的长度即为 r − l + 1 r-l+1 r−l+1。
- 若 a i ⩽ a j a_i \leqslant a_j ai⩽aj，则令 t p = a i t_p=a_i tp=ai，并令 i = i + 1 , p = p + 1 i=i+1,;p=p+1 i=i+1,p=p+1；
- 反之，若 a j < a i a_j<a_i aj<ai，则令 t p = a j t_p=a_j tp=aj，并令 j = j + 1 , p = p + 1 j=j+1,;p=p+1 j=j+1,p=p+1；
- 直到 i > m i d i>mid i>mid 或 j > r j>r j>r 时，终止第 1 , 2 1,2 1,2 步操作，并执行如下操作；否则，继续从第 1 1 1 步开始执行；1. 若满足 i ⩽ m i d i\leqslant mid i⩽mid，则令 t p = a i t_p=a_i tp=ai，并令 i = i + 1 , p = p + 1 i=i+1,;p=p+1 i=i+1,p=p+1，直到 i > m i d i>mid i>mid 为止；2. 若此时 j ⩽ r j \leqslant r j⩽r，则令 t p = a j t_p=a_j tp=aj，并令 j = j + 1 , p = p + 1 j=j+1,;p=p+1 j=j+1,p=p+1，直到 j > r j>r j>r 为止。
- 用临时数组 t t t 覆盖数组 a a a 的 [ l , r ] [l,r] [l,r] 部分，即 a l = t 0 , a l + 1 = t 1 , ⋯ , a r = t p − 1 a_l=t_0,;a_{l+1}=t_1,;\cdots,a_r=t_{p-1} al=t0,al+1=t1,⋯,ar=tp−1。
因为临时数组
t t t 从下标 0 0 0 开始存值，而 p p p 可以看作数组 t t t 存值的长度，故 t p − 1 t_{p-1} tp−1 即为数组 t t t 所存储的最后一个值，此时 p = r − l + 1 p=r-l+1 p=r−l+1。
则对于数组
a
a
a，需要排序的范围是
[
1
,
n
]
[1,n]
[1,n]，对此范围应用该**算法流程**，即可完成排序。
特殊地，对于
l = r l=r l=r 时，则单个元素就不需要排序，也就不需要执行如上**算法流程**了。
算法的正确性与稳定性
正确性：
该算法流程保证了临时数组
t
t
t 中的元素是从左到右非递减排序的，故保证了数组
a
a
a 中
[
l
,
r
]
[l,r]
[l,r] 范围内的元素是从左到右非递减的，该算法是正确的。
对于算法流程的第
1 , 2 1,2 1,2 步，保证存储临时数组 t t t 中的元素是从左到右非递减的。若执行到算法流程的第
3 3 3 步，则只会执行第 3.1 3.1 3.1 或 3.2 3.2 3.2 步，若此时：
- 只执行第 3.1 3.1 3.1 步，说明数组 a a a 中 [ m i d + 1 , r ] [mid+1,r] [mid+1,r] 范围内的元素均小于 [ i , m i d ] [i,mid] [i,mid] 范围内的元素；
- 只执行第 3.2 3.2 3.2 步，说明数组 a a a 中 [ l , m i d ] [l,mid] [l,mid] 范围内的元素均小于 [ j , r ] [j,r] [j,r] 范围内的元素。
因此整个算法流程保证了临时数组
t t t 中的元素是从左到右非递减的。
该算法是将两个排好序的数组合并到一个大数组中的算法，故被称为归并排序Merge Sort。
稳定性：
当两个元素的值相同时，由于算法流程的第
1
1
1 步，位置更靠左的元素会优先被存入到临时数组
t
t
t 中，故该算法是稳定的。
C++ 代码实现
voidMerge_sort(vector<int>&a,int l,int r){if(l == r)return;int mid =(l + r)/2;Merge_sort(a, l, mid);Merge_sort(a, mid +1, r);int i = l, j = mid +1, p =0;
vector<int>t(r - l +1);while(i <= mid && j <= r){if(a[i]<= a[j]) t[p++]= a[i++];else t[p++]= a[j++];}while(i <= mid) t[p++]= a[i++];while(j <= r) t[p++]= a[j++];for(i = l, p =0; i <= r;++i,++p)
a[i]= t[p];}
声明一个
vector类型的变量时，其格式为：
vector<int>a(size, val);其中尖括号
<>内填入
vector内每个元素所使用的的数据类型，如上所示的
a为变量名，并且可以在变量名后紧跟一个括号
()，括号内可以填入两个参数：
- 第一个参数为
vector的初始长度，可以理解为默认开一个长度为给定参数、值全部为 0 0 0 的数组（但这个数组可以删除、增加元素）；- 第二个参数为
vector内所有元素的初始值，可以不填这个参数（不填默认为 0 0 0）。- 也可以不跟括号
()，不给任何参数，这样vector就可以理解为一个长度为 0 0 0 的空数组。如上代码第
8 8 8 行，在声明vector类型的变量
t时，就给出了第一个参数。
- 代码第 2 2 2 行即为 l = r l=r l=r 时的特判，此时只有一个元素，无需再执行算法流程。
- C++ 语言中整数的除法是自动向下取整的（即抹掉小数点后的部分），故代码第 4 4 4 行直接写为
int mid = (l + r) / 2;。- 算法流程体现在代码的：- 代码第 4 ∼ 8 4 \sim 8 4∼8 为算法流程的提前准备；- 代码第 10 ∼ 13 10\sim 13 10∼13 行即为算法流程的第 1 , 2 1,2 1,2 步；- 代码第 15 , 16 15,16 15,16 行即为算法流程的第 3 3 3 步，算法的正确性中已经说明了其中只有一个
while循环能够执行；- 代码第 18 , 19 18,19 18,19 行即为算法流程的第 4 4 4 步。使用方法：
- 传入想要排序的
vector a和想要排序的范围 l , r l,r l,r 即可，函数会将a的 [ l , r ] [l,r] [l,r] 范围内的元素自动排序成非递减的。- 如果想要排序成非递增的，则将代码第 11 11 11 行的
if判断语句内的条件改为a[i]>=a[j]即可。- 需要引用的头文件和命名空间：
#include<vector>usingnamespace std;
算法的时间复杂度
若想要排序的数组
a
a
a 的元素个数为
n
n
n，则每次调用代码第
5
5
5 行的递归函数，最多会递归到
⌈
log
n
⌉
\lceil \log n\rceil
⌈logn⌉ 层。
每层都会将数组
a
a
a 赋值给临时数组
t
t
t，再赋值回数组
a
a
a，故总的时间复杂度为
O
(
n
log
n
)
O(n\log n)
O(nlogn)。
这里的
log \log log 是以 2 2 2 为底数的。
算法拓展
利用归并排序Merge Sort求逆序对数量
在算法流程中，由于数组
a
a
a 的
[
l
,
r
]
[l,r]
[l,r] 这一范围被分为
[
l
,
m
i
d
]
,
[
m
i
d
+
1
,
r
]
[l,mid],\;[mid+1,r]
[l,mid],[mid+1,r] 两个范围，故
[
l
,
r
]
[l,r]
[l,r] 范围内的逆序对被分为了三种：
- 逆序对 ( a x , a y ) (a_x,a_y) (ax,ay) 满足 l ⩽ x , y ⩽ m i d l\leqslant x,y \leqslant mid l⩽x,y⩽mid，这一部分的逆序对会在调用代码第 5 5 5 行的
Merge_sort(a, l, mid);被求出； - 逆序对 ( a x , a y ) (a_x,a_y) (ax,ay) 满足 m i d + 1 ⩽ x , y ⩽ r mid+1\leqslant x,y \leqslant r mid+1⩽x,y⩽r，和一部分逆序对会在调用代码第 5 5 5 行的
Merge_sort(a, mid + 1, r);被求出； - 逆序对 ( a x , a y ) (a_x,a_y) (ax,ay) 满足 l ⩽ x ⩽ m i d , m i d + 1 ⩽ y ⩽ r l\leqslant x \leqslant mid,; mid+1 \leqslant y \leqslant r l⩽x⩽mid,mid+1⩽y⩽r，这一部分需要通过算法流程求解出来。
在算法流程的第
2
2
2 步中，若
a
j
<
a
i
a_j<a_i
aj<ai，则说明数组
a
a
a 的
[
i
,
m
i
d
]
[i,mid]
[i,mid] 范围内的值都比
a
j
a_j
aj 大，则存在形如
(
a
x
,
a
y
)
(
i
⩽
x
⩽
m
i
d
,
y
=
j
)
(a_x,a_y)\;(i\leqslant x \leqslant mid,\;y=j)
(ax,ay)(i⩽x⩽mid,y=j) 的逆序对的个数为
m
i
d
−
i
+
1
mid-i+1
mid−i+1。
因为保证了数组
a a a 的 [ l , m i d ] , [ m i d + 1 , r ] [l,mid],\;[mid+1,r] [l,mid],[mid+1,r] 范围内的元素是非递减的。
C++ 代码实现
intMerge_sort(vector<int>&a,int l,int r){if(l == r)return;int mid =(l + r)/2, res =0;
res +=Merge_sort(a, l, mid)+Merge_sort(a, mid +1, r);int i = l, j = mid +1, p =0;
vector<int>t(r - l +1);while(i <= mid && j <= r){if(a[i]<= a[j]) t[p++]= a[i++];else{
res += mid - i +1;
t[p++]= a[j++];}}while(i <= mid) t[p++]= a[i++];while(j <= r) t[p++]= a[j++];for(i = l, p =0; i <= r;++i,++p)
a[i]= t[p];return res;}
使用方法：
- 传入想要排序的
vector a和想要计算逆序对个数的范围 l , r l,r l,r 即可，函数会返回一个整形的值，即为此范围内的逆序对个数。- 注意当数据规模较大时，逆序对个数可能会超出
int的表示范围，此时的变量res和函数的返回值的数据类型应改为long long。
快速排序Quick Sort
快速排序在算法竞赛中并不常见，也不常用，所以只是介绍一下算法。
算法流程
设当前数组
a
a
a 中需要排序的范围为
[
l
,
r
]
[l,r]
[l,r]，令
m
i
d
=
⌊
l
+
r
2
⌋
mid=\left\lfloor \frac{l+r}{2}\right \rfloor
mid=⌊2l+r⌋。
设基准值
k
=
a
[
m
i
d
]
k=a[mid]
k=a[mid]，再令
i
=
l
,
j
=
r
i=l,\;j=r
i=l,j=r，执行以下操作：
- 若 a i < k a_i<k ai<k 则 i = i + 1 i=i+1 i=i+1，直到满足 a i ⩾ k a_i \geqslant k ai⩾k 为止；
- 若 a j > k a_j>k aj>k 则 j = j − 1 j=j-1 j=j−1，直到满足 a j ⩽ k a_j \leqslant k aj⩽k 为止；
- 若 i ⩽ j i \leqslant j i⩽j，则交换 a i , a j a_i,a_j ai,aj，并令 i = i + 1 , j = j − 1 i=i+1,;j=j-1 i=i+1,j=j−1；
- 若此时 i ⩾ j i\geqslant j i⩾j，则终止如上操作，否则，继续从第 1 1 1 步开始执行；
- 对数组 a a a 中的 [ l , j ] , [ i , r ] [l,j],;[i,r] [l,j],[i,r] 这两个范围继续执行该算法流程。
特殊地，在实际操作中，可能会出现
j ⩽ l , i ⩾ r j\leqslant l,\;i\geqslant r j⩽l,i⩾r 的情况出现，即这个两个范围会出现 l ⩾ r l\geqslant r l⩾r 的情况，此时也无需在执行**算法流程**，即可停止。
则对于数组
a
a
a，需要排序的范围是
[
1
,
n
]
[1,n]
[1,n]，对此范围应用该**算法流程**，即可完成排序。
算法正确性与稳定性
正确性：
该算法将
[
l
,
r
]
[l,r]
[l,r] 划分成了两部分:
[ l , j ] [l,j] [l,j] 这一部分的值都是 ⩽ k \leqslant k ⩽k 的；[ i , r ] [i,r] [i,r] 这一部分的值都是 ⩾ k \geqslant k ⩾k 的。
因为：
- 算法流程的第 1 1 1 步保证当 [ l , i ] [l,i] [l,i] 这一侧出现 a i ⩾ k a_i \geqslant k ai⩾k 时停止，而算法流程的第 2 2 2 步保证 [ j , r ] [j,r] [j,r] 这一侧出现 a j ⩽ k a_j \leqslant k aj⩽k 时停止，交换 a i , a j a_i,a_j ai,aj 将能使 [ l , i ] , [ j , r ] [l,i],;[j,r] [l,i],[j,r] 满足如上的左右两部分的性质；
- 算法流程的第 4 4 4 步只会在两种情况下发生： 1. 当 i + 1 = j i+1=j i+1=j 并且 a i < k , a j > k a_i<k,;a_j>k ai<k,aj>k 时，执行算法流程的第 1 , 2 1,2 1,2 步之后， j + 1 = i j+1=i j+1=i 并且 a j < k , a i > k a_j<k,; a_i>k aj<k,ai>k，此时并不满足交换条件，但满足了退出条件，并且划分出来的两个区间为 [ l , j ] , [ i , r ] [l,j],;[i,r] [l,j],[i,r]；2. 当 i = j i=j i=j 时，由于 a i ⩽ k a_i \leqslant k ai⩽k 并且 a j ⩾ k a_j \geqslant k aj⩾k，所以一定有 a i = k a_i=k ai=k，此时会执行算法流程的第 3 3 3 步，于是划分出来的两个区间为 [ l , j ] , [ i , r ] [l,j],;[i,r] [l,j],[i,r]，这个区间并不会覆盖满 [ l , r ] [l,r] [l,r]，而是会把中间的值为 k k k 的元素空出来，但是这并不影响正确性，可以认为这个值为 k k k 的元素已经排在了排序好的数组 a a a 中该有的位置。
故该算法是正确的。
稳定性：
可以发现，对于值相同的元素，它们仍可能在算法流程的第
3
3
3 步时被交换位置，所以 **快速排序Quick Sort算法是不稳定的**。
C++ 代码实现
voidQuick_Sort(vector<int>&a,int l,int r){if(l == r)return;int mid =(l + r)/2, k = a[mid], i = l, j = r;while(i < j){while(a[i]< k)++i;while(a[j]> k)--j;if(i <= j){swap(a[i], a[j]);++i;--j;}}Quick_Sort(a, l, j);Quick_Sort(a, i, r);}
- 代码第 2 2 2 行即为 l ⩾ r l\geqslant r l⩾r 的特判，此时无需再执行算法流程。
- 算法流程体现在代码的：- 代码第 3 3 3 行为算法流程的提前准备；- 代码第 5 5 5 行为算法流程的第 1 1 1 步；- 代码第 6 6 6 行为算法流程的第 2 2 2 步；- 代码第 7 ∼ 10 7\sim 10 7∼10 行为算法流程的第 3 3 3 步；- 代码第 4 4 4 行为算法体现的第 4 4 4 步；- 代码第 12 12 12 行为继续执行算法流程的体现。
使用方法：
- 传入想要排序的
vector a和想要排序的范围 l , r l,r l,r 即可，函数会将a的 [ l , r ] [l,r] [l,r] 范围内的元素自动排序成非递减的。- 如果想要排序成非递增的，则需要：
- 将代码第 5 5 5 行的
while循环语句内的条件改为a[i]>k；- 将代码第 6 6 6 行的
while循环语句内的条件改为a[j]<k。- 需要引用得头文件和命名空间：
#include<vector>#include<algorithm>usingnamespace std;
算法的时间复杂度
快速排序Quick Sort最理想的状态就是每次划分的区间恰好为整个区间的一半，参考归并排序Merge Sort的时间复杂度分析，此时的时间复杂度为
O
(
n
log
n
)
O(n \log n)
O(nlogn)，其中
n
n
n 为想要排序的区间的元素个数。
但有意构造的数据可以使快速排序Quick Sort的时间复杂度到达
O
(
n
2
)
O(n^2)
O(n2)。
即有可能每次划分的区间都为
[ l , l ] , [ l + 1 , r ] [l,l],\;[l+1,r] [l,l],[l+1,r]，这样每次就只能确定一个数的正确位置，但却要因此遍历几乎整个数组，故时间复杂度会到达 O ( n 2 ) O(n^2) O(n2)。虽然算法名字是快速排序Quick Sort，但在面对一些有意构造的数据时，这种朴素的快速排序Quick Sort反而可能是最不快且不稳定的。
STL sort
调用参数
在算法竞赛中，如果只是需要排序，则一般不需要自己手写排序算法，C++ 语言的头文件：
#include<algorithm>
包含了
sort
函数，它能对支持随机访问的数组或容器类进行排序。
vector就是一种容器。
sort
函数可以给出三个参数：
sort(begin, end, cmp);
其中：
- 第一个参数为起始位置的指针，它是必须给出的；
- 第二个参数为终止位置的指针，它也是必须给出的；
- 第三个参数为比较函数，即排序后所有相邻的元素需要满足的要求，可以不给出，不给出默认为进行非递减排序。
sort函数会对指针所指向的
[begin,end)这一左闭右开区间范围内的元素进行排序。
调用示例
普通调用
设一个
vector
类型的变量
a
，则：
sort(a.begin(), a.end());
即可对变量
a
内的所有元素进行非递减排序。
对于
vector类型的变量
a，其起始位置的指针为
a.begin()，终止位置的指针为
a.end()。
严格地说，
a.end()指向的是变量
a的最后一个元素的下一个位置，所以是符合
sort函数对左闭右开区间范围进行排序的。
如果想要对变量
a的一部分，即
a[l]到
a[r]这一范围进行排序，可以写为：
sort(a.begin()+ l, a.begin()+ r +1);
设一个数组
b
，则：
sort(b + l, b + r +1);
即可对数组
b
内的
b[l]
到
b[r]
范围内的元素进行非递减排序。
自定义函数
如果想要进行非递增排序或者一些特殊的自定义排序（例如当元素为结构体类型时，如何排序是需要自行定义的），则可以写一个返回值为
bool
类型的
compare
函数。
设一个
vector
类型的变量
a
是一个以
int
数据类型变量为元素的动态数组，则：
boolcmp(int x,int y){return x > y;}sort(a.begin(), a.end(), compare);
即可对变量
a
内的所有元素进行非递增排序。
第三个参数填入
compare函数的名称
cmp，那么变量
a内的所有相邻的元素在排序完后，都会符合给出的
compare函数内的规则。
compare函数内应该穿入两个相同数据类型的变量，并且数据类型也应与需要排序的变量内的元素的数据类型相同。
compare函数在对结构体类型的数组进行排序时，会显得十分有用。
也可以在第三个参数处直接写一个 lambda 表达式 （需要 C++11 及以上版本编译器支持）。
设一个
vector
类型的变量
b
是一个以
int
数据类型变量为元素的动态数组，则：
sort(b.begin(), b.end(),[](int x,int y){return x > y;});
即可对变量
b
内的所有元素进行非递增排序。
lambda 表达式可以理解为没有名字的函数，并且可以直接写在应该填入第三个参数的位置，它更加方便。
算法原理与稳定性
sort
函数的实现原理是为非常复杂的，它运用了多种排序算法，根据数据的不同而选用不同的排序算法。
但也可以将其简单地理解为是一种改进过的快速排序Quick Sort，所以 **
sort
是不稳定的**。
如果想要使用稳定的排序算法，可以尝试使用 **
stable_sort
，它是稳定的**，使用方法与
sort
相同。
算法的时间复杂度
sort
作为改进过的快速排序Quick Sort，其时间复杂度是
O
(
n
log
n
)
O(n\log n)
O(nlogn) 的，其中
n
n
n 为想要排序的区间的元素个数，并且其时间复杂度不受有意构造的数据的影响。
STL unique
调用参数
在算法竞赛中，可能会要求对排序后的元素进行去重，如果不需要统计重复元素的个数，则可以使用
unique
函数去重，它位于 C++ 语言的头文件：
#include<algorithm>
unique
函数能对支持随机访问的数组或容器类进行去重，但前提条件是数组或容器内的元素已经排序成非递减。
unique
函数可以给出两个参数：
unique(begin, end);
其中：
- 第一个参数为起始位置的指针，它是必须给出的；
- 第二个参数为终止位置的指针，它也是必须给出的；
unique函数会对指针所指向的
[begin,end)这一左闭右开区间范围内的元素进行去重。
虽然
unique函数还可以给出第三个参数，即等价函数用于判断两个元素是否相等，但算法竞赛中一般很少涉及，在此就不介绍了。
unique
函数会返回一个指针，指向去重完毕后的最后一个元素的地址，所以在使用时，一般会再让其减去一个起始位置的指针，这样其就变成了去重后的元素的个数。
去重并不会删除这些元素，而是会将它们排在最后一个不重复元素的尾部。
调用示例
设一个
vector
类型的变量
a
，并且**其内部的
a[l]
到
a[r]
范围内的元素已经排序成非递减**，则：
int len =unique(a.begin()+ l, a.end()+ r +1)-(a.begin()+ l);
这里
len
的值即为变量
a
在
a[l]
到
a[r]
范围内所有不重复元素的个数，并且这些不重复的元素已经呈从小到大从
a[l]
开始排序过来。
设一个数组
b
，并且**其内部的
b[l]
到
b[r]
范围内的元素已经排序成非递减**，则：
int len =unique(b + l, b + r +1)-(b + l);
这里
len
的值即为数组
b
在
b[l]
到
b[r]
范围内所有不重复元素的个数，并且这些不重复的元素已经呈从小到大从
b[l]
开始排序过来。
算法的时间复杂度
unique
函数的时间复杂度是
O
(
n
)
O(n)
O(n) 的，其中的
n
n
n 为想要去重的区间所包含的元素个数。
附件
对于如上的冒泡排序Bubble Sort、归并排序Merge Sort、快速排序Quick Sort、STL sort，在此给出测试代码的框架：
#include<vector>#include<cstdio>#include<algorithm>usingnamespace std;/*
在这里补全想要调用的函数
*/intmain(){int n;scanf("%d",&n);// 读入整数 n，表示有 n 个数字需要排序
vector<int>a(n);for(int i =0; i < n;++i)scanf("%d",&a[i]);// 在这里填入想要调用的函数for(int i =0; i < n;++i)printf("%d ", a[i]);return0;}
例如，快速排序Quick Sort的可供测试的完整代码即为：
#include<vector>#include<cstdio>#include<algorithm>usingnamespace std;voidQuick_Sort(vector<int>&a,int l,int r){if(l == r)return;int mid =(l + r)/2, k = a[mid], i = l, j = r;while(i < j){while(a[i]< k)++i;while(a[j]> k)--j;if(i <= j){swap(a[i], a[j]);++i;--j;}}Quick_Sort(a, l, j);Quick_Sort(a, i, r);}intmain(){int n;scanf("%d",&n);
vector<int>a(n);for(int i =0; i < n;++i)scanf("%d",&a[i]);Quick_Sort(a,0, n -1);for(int i =0; i < n;++i)printf("%d ", a[i]);return0;}
可以测试代码正确性的网站链接：洛谷 P1177 【模板】快速排序
更多
例如，使用 STL sort 的可供测试的完整代码为：
#include<vector>#include<cstdio>#include<algorithm>usingnamespace std;boolcmp(int x,int y){return x < y;}intmain(){int n;scanf("%d",&n);
vector<int>a(n);for(int i =0; i < n;++i)scanf("%d",&a[i]);sort(a.begin(), a.end(), cmp);for(int i =0; i < n;++i)printf("%d ", a[i]);return0;}
虽然如上使用了
compare函数，但它仍是非递减排序的。
例如，对结构体进行排序的可供测试的完整代码为：
#include<vector>#include<cstdio>#include<algorithm>usingnamespace std;structnode{int x, y;};boolcmp(node i, node j){if(i.x == j.x)return i.y < j.y;elsereturn i.x < j.x;}// 先按照 x 非递减排序，若 x 相同则按照 y 非递减排序intmain(){int n;scanf("%d",&n);// 读入整数 n，表示有 n 个 node 结构体需要排序
vector<node>a(n);for(int i =0; i < n;++i)scanf("%d %d",&a[i].x,&a[i].y);// 依次读入每个 node 结构体sort(a.begin(), a.end(), cmp);for(int i =0; i < n;++i)printf("%d ", a[i]);return0;}
其他
其他排序算法，如插入排序Insertion Sort、桶排序Bucket Sort、基数排序Radix Sort、希尔排序Shell’s Sort并没有在此介绍，因为它们在算法竞赛的出现次数很少。
可能桶排序会偶尔出现，但它更多的是作为技巧而非算法的核心内容，并且实现原理与方法十分简单，在此不做介绍。
还有一种特殊的排序算法，堆排序Heap Sort，但它的侧重点并不是排序本身，而是堆这一数据结构，故此排序方法就不在此介绍了。
虽然有
sort
函数可以直接实现排序，但是冒泡排序Bubble Sort和归并排序Merge Sort并非一无是处，重要的不是它们的实现的功能，而是它们的思想。
作者：NCUST ACM协会 培训竞赛部
var1.0 完成于 2022.10.11。
版权归原作者 华北理工大学ACM协会 所有， 如有侵权，请联系我们删除。