# **1 基本概念**
## **1.1 介绍**
在计算机科学中，**排序算法**是能将一个序列（例如数组）依照特定**排序方式**进行排列的一种算法。最常用到的排序方式是**数值顺序**和**字典顺序**。排序算法在一些算法（例如**二分查找**）中是重要的，元数据经过排序算法的处理后这些算法才能正确的运转。基本上，排序算法的输出必须遵守下面两个原则：
1. 输出结果为递增的序列。
2. 输出结果为元输入序列的一种排列。
## **1.2 算法分析**
排序算法通常有以下算法分析指标：
- **时间复杂度**（最差、平均和最好性能），是衡量算法时间效率的一个指标。设定排序对象（数组）的大小（长度）为$n$，一般而言，好的性能是$O(n\log n)$，坏的性能是$O(n^2)$。对于一个排序理想的性能是$O(n)$，但平均而言不可能达到。**基于比较的排序算法**对大多数元数据而言至少需要$O(n\log n)$。使用具有强大计算能力的计算机，能令时间复杂度趋近于$O(n)$（但不等于$O(n)$）。
- **空间复杂度**，也就是内存的使用量。
- **稳定性**，稳定排序算法会让原本有相等关键字值的元素维持相对次序。也就是说如果一个排序算法是稳定的，当有两个相等关键字值的元素$R$和$S$，且在原本的序列中$R$出现在$S$之前，在排序过后的序列中$R$也将会是在$S$之前。
## **1.3 稳定性**
稳定性并不会影响排序的最终结果，但是当排序对象中有相等关键字值时会产生一些问题。现在提供一个数组，我们用一个有序数对$(key,i)$表示数组中的一个元素的值和它相应在数组中的位置（下标），排序（依据元素的值从小到大）后可能会有两种情况：
```
(5,1) (4,2) (5,3) (6,2)
```
一个让值相等的元素维持在元数组中相对的次序，另一个则没有：
```
(4,2) (5,1) (5,3) (6,3)
(4,2) (5,3) (5,1) (6,3)
```
不稳定排序算法可能会改变值相等的元素在元序列中的相对次序，但是稳定排序算法从来不会这样。不稳定的排序算法可以被特别地实现为稳定，实现的一个方式是使用第二关键字（下标）。然而，这种次序通常牵涉到额外的空间负担，因为需要存储下标这一信息。
## **1.4 说明**
下面的排序对象都为数组，且默认数组大小为n。
# **2 基于比较的排序算法**
## **2.1 朴素做法-选择排序**
对于排序，能想到的最简单的思路应该是这样：**每次从数组中找出最大的值**，**然后拿出该值**。写起来不难，请看代码。
```cpp
//有缺陷
for (int i=0;i<n;i++) //数组下标从0~n-1
{
int minn=INT_MAX,min_i; //INT_MAX是一个宏，被替换为int类型最大值
for (int j=0;j<n;j++)
if (array[j]<minn)
{
minn=array[j];
min_i=j;
}
cout<<array[min_i]<<' ';
array[min_i]=INT_MAX;
}
//注意，array可能会与std::array重名
```
程序运行的非常成功，但为什么说有缺陷呢？来说一下程序存在的问题：
1. 此程序在排序过程中**立即**输出内容，无法操作排序之后的内容。如果需要操作排序之后的内容，我们需要额外开一个空间，把每次找出来的最大值装进去，需要$O(n)$额外空间。
2. 排序完成总共需要$n\times n$次操作，为$O(n^2)$的时间复杂度。
3. 操作稍微**复杂**了些。
所以我们需要一个更好的做法：**遍历数组，将所有当前元素与其后面的元素比较**，**如果后面的元素比它小就交换它们的位置**。
```cpp
for (int i=0;i<n;i++)
for (int j=i+1;j<n;j++) //第n-1位元素后面无可比较的元素
if (array[i]>array[j]) swap(array[i],array[j]); //交换
```
改进后，每遍内循环结束后第$i$位的元素比第$i+1\sim n-1$位的元素都小，如此遍历$n-1$次后就得到了排序完的数组。操作次数减少到了$\frac{n\times (n-1)}{2}$次，但仍是$O(n^2)$的时间复杂度，不过好在的是它不需要额外的空间。这样的排序方法，称为**选择排序**。由于选择排序的**跨越**式交换，所以选择排序是不稳定的排序算法。
## **2.2 相邻交换-冒泡排序**
由选择排序的比较思想延伸，我们可以有这样的一个做法：**对数组进行遍历**，**每次比较当前元素与紧邻在它后面的元素**，**如果当前元素大于紧邻在它后面的元素，那就交换它们的位置**。每遍内循环结束后末尾的元素都比其前面的元素大，这样循环$n-1$次就可以把数组排序好，请看代码。
```cpp
for (int i=n-1;i;i--)
for (int j=0;j<i;j++)
if (array[j]>array[j+1]) swap(array[j],array[j+1]); //交换
```
因越小的元素会经由交换慢慢“浮”到数组的前端，所以这样的排序方法就得名**冒泡排序**。冒泡排序的时间复杂度为$O(n^2)$，且它不需要额外的空间。由于冒泡排序的**相邻**式交换，所以冒泡排序是稳定的排序算法。
## **2.3 扑克牌-插入排序**
斗地主大家应该都玩过，在正式开局前我们都需要先把自己的牌理一下，也就是排好顺序。牌是一张一张摸来的，所以只需要保证手上的牌一直都是有序的就可以了。这样的排序叫作**插入排序**。
对于我们的扑克牌$[5,3,7,4]$:
- 首先拿起第一张牌，手上的牌$[5]$。
- 拿起第二张牌，插在$5$的左边，手上的牌$[3,5]$
- 拿起第三张牌，插在$5$的右边，手上的牌$[3,5,7]$
- 拿起第三张牌，插在$3$和$5$的中间，手上的牌$[3,4,5,7]$，此时排好序。
转换到代码的操作：
1. 定义数组$sorted$。
2. 从元数组的第$1$个元素开始遍历，将其装入$sorted$。
3. 遍历元数组的下一个元素$x$，在$sorted$中找到第一个值大于$x$的元素，记录其位置$p$。
4. 把$sorted$数组从位置$p$开始的元素全部后移一位，并赋值$sorted[p]=x$。
5. 重复操作$3-4$直到遍历完所有元数组中的元素。
请看代码。
```cpp
int cnt=0; //记录sorted数组中元素的个数
for (int i=0;i<n;i++)
{
int p,x=array[i];
for (p=0;p<cnt;p++)
if (sorted[p]>x) break;
for (int j=cnt-1;j>=p;j--) //避免数据丢失
sorted[j+1]=sorted[j];
sorted[p]=x;
cnt++;
}
```
在后移元素时选择了从后往前遍历将每个元素向后移动，这避免了移动造成后面一个元素的数据丢失。插入排序存在**最好情况**和**最坏情况**。假设我们要求的是按照数值升序来排序，那么最好情况就是数组元素是降序排列，在这种情况下，需要进行的比较操作共有$n-1$次；最坏情况就是，数组元素是升序排列，那么此时需要进行的比较共有$\frac{n(n-1)}{2}$次。平均来说插入排序的时间复杂度为$O(n^2)$。上面的示例代码中额外定义了数组temp，所以这种写法需要额外O(n)的空间，当然还有不需要额外空间的写法，请自行尝试。在`C++STL`的`sort`算法和`stdlib`的`qsort`算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）。
## **2.4 分治思想-归并排序**
**归并排序**，是创建在归并操作上的一个排序算法。归并排序的基本原理是**分治**：
- **分割**：递归地把当前数组平均分割成两半直到当前数组长度为$1$。
- **归并**：在保持数组元素有序的条件下将上一步得到的子数组合并到一起。
请看代码。
```cpp
void mergesort(int l,int r)
{
if (l==r) return; //空区间或者只有一个元素的区间
int mid=(l+r)/2;
mergesort(l,mid);
mergesort(mid+1,r);
int i=l,j=mid+1,k=l;
while (i<=mid&&j<=r)
{
if (array[i]<array[j]) temp[k++]=array[i++];
else temp[k++]=array[j++];
}
while (i<=mid) temp[k++]=array[i++];
while (j<=r) temp[k++]=array[j++];
for (int i=l;i<=r;i++)
array[i]=temp[i];
}
```
归并排序是一个时间复杂度稳定在$O(nlogn)$的排序算法（最差、平均和最好性能），并且它是一个稳定的排序算法。它的缺点在于它需要$O(n)$的额外空间。
## **2.5 标头-快速排序**
假设你正在帮一群人以身高升序排队，你可以这样来帮他们排好队：
1. 随机选一个人作为标头。
2. 比他矮的人都到他左边，比他高的人都到他右边。
3. 对他左边，右边的人重复$1\sim 2$的操作直到他左右边的人数少于等于$1$个。
这样的排序叫作**快速排序**，请看代码。
```cpp
//有缺陷
void quicksort(int l,int r)
{
if (l>=r) return; //空区间或者只有一个元素的区间
int flag=array[l];
int p=l,q=r;
for (int i=l;i<=r;i++)
{
if (array[i]<flag) temp[p++]=array[i];
if (array[i]>flag) temp[q--]=array[i];
}
//现在，[l,p-1]全是比flag小的，[q+1,r]全是比flag大的
for (int i=l;i<=p-1;i++)
array[i]=temp[i];
for (int i=p;i<=q;i++) //与flag值相同的元素
array[i]=flag;
for (int i=q+1;i<=r;i++)
array[i]=temp[i];
quicksort(l,p-1);
quicksort(q+1,r);
}
```
程序运行的非常成功，但为什么说有缺陷呢？
设定一个数组$[1,2,3,4,5,6,7,8]$，进行快速排序的操作：
1. 操作后$[1][2,3,4,5,6,7,8]$。
2. 再操作后$[1][2][3,4,5,6,7,8]$。
3. 再操作后$[1][2][3][4,5,6,7,8]$。
4. 再继续操作......
在这个例子中，每遍操作只排好了一个元素，时间复杂度达到了$O(n^2)$！可以发现对于这个例子，快速排序做了许多的无用功，并且这个数组本身就是排好序了的！分析后发现问题应该出现在$flag$上，我们每次选取的$flag$的值都是数组区间$[l,r]$里的$array[l]$，这就表明，如果数组元素是升序排列，那么每次选取的$flag$的值都是数组区间$[l,r]$里的最小值。那么应该如何选取flag的值？
可能你会想到取数组区间$[l,r]$里的$array[(l+r)/2]$的值？但是这样也不能保证完全正确，特殊的数据同样会让你的时间复杂度达到$O(n^2)$。正确的做法是取随机数：
```cpp
int flag=array[rand()%(r-l+1)+l]; //rand%(r-l+1)+l表示随机取[l,r]的一个数
```
如果每次都能取到数组区间里的值的中位数，那么排序算法的时间复杂度为$O(nlogn)$，$flag$取数组区间$[l,r]$的一个随机元素的值，时间复杂度是有保证的，平均时间复杂度为$O(nlogn)$。这是一个不稳定的排序算法。
上述排序算法需要$O(n)$的额外空间。然而，还有一种不需要额外空间的快速排序，称为快速排序的**原地分割**版本。这种版本以**二分**为基本思想。请看代码。
```cpp
void quicksort(int l,int r)
{
int flag=array[(l+r)/2]; //找中间的数进行2分
int i=l,j=r;
do
{
while(array[i]<flag)
i++; //找左半部分大于中间数的
while(array[j]>flag)
j--; //找右半部分小于中间数的
if(i<=j)
{
swap(array[i++],array[j--]);
//左指针右移,右指针左移
}
}while(i<=j);
if(l<j) quicksort(l,j);
if(i<r) quicksort(i,r);
}
```
因为是跨越式交换，所以这个版本的快速排序算法也是不稳定的排序算法。但是它的优势很明显：不需要额外的空间。
事实上，快速排序通常明显比其他算法更快，因为它的**内部循环**可以在大部分的架构上很有效率地达成，因此得名。
## **2.6 总结**
下面对以上算法做一个简要的比较：
|名称|平均时间复杂度|额外空间复杂度|稳定性|
|:-:|:-:|:-:|:-:|
|选择排序|$O(n^2)$|$O(1)$|×|
|冒泡排序|$O(n^2)$|$O(1)$|√|
|插入排序|$O(n^2)$|$O(1)$或$O(n)$|√|
|归并排序|$O(nlogn)$|$O(n)$|√|
|快速排序|$O(nlogn)$|$O(1)$或$O(n)$|×|
上述的排序方法都是**基于比较的排序方法**，**基于比较的排序方法**，**最好只能达到**$O(nlogn)$**的时间复杂度**。
# **3 不基于比较的排序算法**
## **3.1 计数排序**
**计数排序**是一个线性时间的排序算法。计数排序使用一个额外的数组$count$，其中第$i$个元素是元数组$array$中值等于$i$的元素的个数。然后根据数组$count$来将元数组$array$中的元素排到正确的位置。
转化到代码的操作：
1. 统计元数组$array$中每个值为$i$的元素出现的次数，存入数组$count$的第$i$项。
2. 求数组$count$的前缀和。（从$count$中的第一个元素开始，每一项和前一项相加）
3. 反向填充目标数组$array_sorted$，将每个元素$i$放在目标数组的第$count[i]$项，每放一个元素就将$count[i]-1$
请看代码。
```cpp
int array[6]={5,7,8,1,3,10};
int main()
{
for (int i=0;i<6;i++)
count[array[i]]++;
for (int i=1;i<=10;i++) //数据范围是1~10
count[i]+=count[i-1];
for (int i=6;i;i--)
array_sorted[--count[array[i-1]]]=array[i-1];
}
```
由于用来计数的数组$count$的长度取决于元数组中数据的范围，这使得计数排序对于数据范围很大的数组，需要大量时间和内存。计数排序的时间复杂度为$O(n+k)$，其中n表示元数组的大小，k表示原数组中元素的数据范围。计数排序需要额外$O(n+k)$的空间。计数排序是一个稳定的排序算法。
## **3.2 桶排序**
**桶排序**也是一个线性时间的排序算法，桶排序工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
转换到代码的操作：
1. 定义一些容器（数组）作为空桶子。
2. 遍历元数组，把每个元素放到对应的桶子里。
3. 对每个不是空的桶子进行排序。
4. 把这些排序完的桶子里的元素放回到元数组中。
你可能会觉得桶排序有那么点像归并排序（以递归方式重复桶排时），但其实并不是，我们所使用的桶之间是相互独立，且有先后次序的，所以并不需要进行合并操作。根据桶的性质，显然使用`vector`来作为桶最为合适，请看代码。
```cpp
int array[6]={5,7,8,1,5,3};
vector<int> tank[11]; //弄了10个桶（编号1~10）
int mapping(int n) //映射函数
{
return n;
}
int main()
{
for (int i=0;i<6;i++)
tank[mapping(array[i])].push_back(array[i]);
int cnt=0;
for (int i=1;i<=10;i++)
{
if (tank[i].size()>0)
for (auto j:tank[i])
array[cnt++]=j;
}
}
```
显然，用二维数组作桶也是可以的，但是二维数组需要开一个比较大的固定空间。映射函数的用处在这里并没有体现出来，但是可以说，映射函数是桶排序的一个核心部件，只有通过映射函数，我们才能把元素和桶连接起来。
桶排序的应用场景十分严苛。首先，数据应该分布比较均匀。较坏的情况下，数据可能全部都被分到同一个桶里，这时我们设置的桶并没有把数据切割开来；其次，要比较容易设计桶。桶排序的平均时间复杂度为$O(n+k)$，需要额外$O(nk)$（使用`vector`作为桶时可以趋近于$O(n)$）的空间，它是一个稳定的排序算法。
## **3.3 基数排序**
**基数排序**是一个用于**整数排序**的排序算法。其原理是将整数按位数切割成不同的数字，然后按每个数位分别比较数字大小。由于整数也可以表达字符串和特定格式的浮点数，所以基数排序也不是只能使用于整数。
转换到代码的操作：
1. 统一元数组中元素的数位大小，数位较少的元素前面补零。
2. 从数位最低位开始，依据数位数字大小进行排序。这样从最低位到最高位都排序一遍后，数组就排好了序（反过来从最高位到最低位也可以）。
请看代码。
```cpp
int array[6]={50,17,82,31,5,32};
vector<int> tank[11];
int mapping(int n,int x)
{
while (x!=1)
{
n/=10;
x--;
}
return n%10;
}
int main()
{
for (int i=1;i<3;i++) //表示数位
{
for (int j=0;j<6;j++)
tank[mapping(array[j],i)].push_back(array[j]);
int cnt=0;
for (int j=0;j<10;j++)
{
if (tank[j].size()>0)
for (auto k:tank[j])
{
array[cnt++]=k;
tank[j].pop_back();
}
}
}
}
```
基数排序的时间复杂度为$O(nk)$，其中$n$是原数组的大小，$k$是数位大小。注意这个时间复杂度不一定优于$O(nlogn)$，但是在大多数情况下，$k$都比$logn$要小。基数排序需要额外$O(n+k)$空间，它是稳定的排序算法。
## **3.4 总结**
下面对以上算法做一个简要的比较：
|名称|平均时间复杂度|额外空间复杂度|稳定性|
|:-:|:-:|:-:|:-:|
|计数排序|$O(n+k)$|$O(n+k)$|√|
|桶排序|$O(n+k)$|$O(nk)$|√|
|基数排序|$O(nk)$|$O(n+k)$|√|
# **4 进阶排序算法使用**
## **4.1 C++STL 排序有关算法**
C++的`algorithm`库提供了排序有关的算法函数，其中比较常用的就是`sort`函数，`sort`函数实际上是一个混合使用排序的函数，根据数据规模来确定一个最快的排序方法。
如何使用`sort`函数？现在有一个数组array，从下标0开始存了n个数据，则应如下使用：
```cpp
sort(array,array+n);
```
可以看出使用方法应为`sort(排序起始地址,排序结束地址的后一个地址)`，你也可以想象成是一个左闭右开区间。
`sort`可以对各种类型的数组或者C++STL容器进行排序。当没有给定第三个参数（`cmp`函数或functor对象）时，`sort`函数默认进行升序排序，前提是这些数据类型定义了`<`运算符（即这些数据类型可以作为<运算符的运算对象）。如果没有，可以给定`cmp`函数或functor对象作为`sort`函数的第三个参数或者在自定义的数据类型内重载<运算符。除此之外，给定`cmp`函数或functor对象和重载<运算符还可以用来实现其他排序方式，例如降序排序和多关键字排序，下面是一个降序排序的例子，请看代码。
```cpp
//降序排序一个int类型的数组
bool cmp(int x,int y)
{
return x>y;
}
```
简要说明一下，`cmp`函数的返回类型为$bool$，形参类型为数据的类型。怎么用`cmp`函数实现不同排序方式呢，可以暂且把`sort`看作为冒泡排序，那么当`cmp`返回$1$时，不进行交换；当返回$0$时，进行一次交换。根据冒泡排序的性质就可以快速写好`cmp`函数。
除了`sort`函数外，还有`stable_sort`函数和`partial_sort`函数，它们分别代表稳定排序函数和部分排序函数，用法与`sort`函数相同，但时间复杂度有所区别。
## **4.2 多关键字排序**
当排序的数组中有值相等的元素时，它们之间的顺序可能是确定的（对于稳定的排序算法）也可能是不确定的（对于不稳定排序的算法）。在生活中我们往往需要对这些值相等的元素再排定一个顺序，这时我们可以通过增加第二排序方式来确定第一排序方式下相同元素的顺序。我们把排序方式所依附的索引称为**关键字**，例如成绩的总分和单科分数。对结构体数组的排序就是典型的多关键字排序，因为结构里有许多不同类型的变量。把变量作为关键字，依据不同的关键字优先级对结构体数组进行排序。
不使用`sort`函数，在排序算法的赋值操作中将结构体中的所有内容都进行赋值即可；使用`sort`函数，我们就需要修改`cmp`函数。请看代码。
```cpp
struct node
{
int key_first,key_second; //第一关键字和第二关键字
}array[100005];
bool cmp(node a,node b)
{
if (a.key_first!=b.key_first)
return a.key_first<b.key_first; //当第一关键字不相等时
else return a.key_second>b.key_second; //当第一关键字相等时
}
int main()
{
int n;
cin>>n;
for (int i=0;i<n;i++)
cin>>array[i].key_first>>array[i].key_second;
sort(array,array+n,cmp);
}
```
# **5 排序算法思想延申**
## **5.1 车厢重组**
- <a href="https://www.luogu.com.cn/problem/P1116" target="_blank">车厢重组</a>
题目中有两点很清楚：“相邻两节车厢的位置交换”和“从小到大排列”，这就很容易想到时冒泡排序。
对于相邻交换（有一定判断条件）使得数组有序（对于题目所要求的顺序），计算交换次数的问题我们可以使用冒泡排序。请看代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[10005];
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin>>n;
int cnt=0;
for (int i=0;i<n;i++)
cin>>a[i];
for (int i=0;i<n-1;i++)
for (int j=0;j<n-i-1;j++)
if (a[j+1]<a[j]) {swap(a[j+1],a[j]); cnt++;}
cout<<cnt<<'\n';
return 0;
}
```
## **5.2 逆序计数**
- **逆序对**：如果存在正整数$i,j$使得$1\leq i < j \leq n$而且$A[i]＞$A[j]，则$(A[i],A[j])$这一个有序对称为$A$的一个逆序对。
逆序对数是一个很经典的问题，它可以通过树状数组来求得。除了树状数组的做法外，我们还可以通过归并排序来求逆序对数。
在归并排序的合并步骤中，合并的两个子数组是一左一右的，也就是左边的子数组中的元素的位置都在右边的子数组中的元素的位置的前面，并且每个子数组中的元素都已经是排好序了的，根据这样的性质就可以用归并排序来求得逆序对数，请看代码。
```cpp
int a[100005],p[100005];
long long ans; //逆序对数范围在1~n(n-1)/2内，一般会超出int类型的范围
void msort(int l,int r)
{
if(l>=r) return;
int mid=l+r>>1;
msort(l,mid);
msort(mid+1,r);
int i=l,j=mid+1,k=l;
while(i<=mid&&j<=r)
if(a[i]<=a[j])
p[k++]=a[i++];//先赋值再+1
else
{p[k++]=a[j++]; ans+=(long long)mid-i+1;} //如果左边子数组当前元素大于右边子数组当前元素，因为左边子数组是排好序的，所以左边子数组当前元素后面的所有元素都与右边子数组当前元素形成逆序对
while(i<=mid) p[k]=a[i],k++,i++;
while(j<=r) p[k]=a[j],k++,j++;
for(int i=l;i<=r;i++)
a[i]=p[i];
}
```
## **5.3 二路归并**
<a href="https://www.luogu.com.cn/problem/P1309" target="_blank">瑞士轮</a>
题目意思很清楚，我们需要先知道初始的选手排名情况并分配选手进行比赛，比赛后再获取选手排名情况并分配选手进行比赛，一直重复直到比赛结束。我们需要记录的信息有三个：选手实力值，分数和编号，这是一个多关键字排序，所以想到使用`sort`函数完成排序。但会发现这种做法的操作次数是$R \times 2Nlog(2N)$，对于题目的数据，已经超过$1e8$的级别了，所以使用`sort`十分危险。可以发现每轮比赛结束后胜利者和失败者两类人的顺序是排好序的，那这就有点联想到归并排序的归并操作了，所以我们不需要在每轮比赛后都排序，我们只需要在每轮比赛结束后把胜利者和失败者两类人都分配到对应的子数组中，然后对子数组进行归并操作即可。具体思路如下：
1. 用`sort`函数先排序一次。（还未比赛之前）
2. 模拟比赛，在每轮比赛结束后把胜利者和失败者两类人都分配到对应的子数组中。
3. 合并胜利者和失败者两类人所属的子数组。
4. 重复操作$2-3$直到完成$R$轮比赛。
请看代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node
{
int sc,w,id; //分数，实力，编号
}a[200005],b[100005],c[100005];
bool cmp(node a,node b)
{
if (a.sc!=b.sc) return a.sc>b.sc;
else return a.id<b.id;
}
void mergesort(int n)
{
int i=1,j=1,k=1;
while (i<=n&&j<=n)
{
if (b[i].sc!=c[j].sc) //总分比较
{
if (b[i].sc>c[j].sc)
{
a[k].sc=b[i].sc;
a[k].id=b[i].id;
a[k].w=b[i].w;
i++;
}
else
{
a[k].sc=c[j].sc;
a[k].id=c[j].id;
a[k].w=c[j].w;
j++;
}
}
else if (b[i].id<=c[j].id)
{
a[k].sc=b[i].sc;
a[k].id=b[i].id;
a[k].w=b[i].w;
i++;
}
else
{
a[k].sc=c[j].sc;
a[k].id=c[j].id;
a[k].w=c[j].w;
j++;
}
k++;
}
while (i<=n)
{
a[k].sc=b[i].sc;
a[k].id=b[i].id;
a[k].w=b[i].w;
i++; k++;
}
while (j<=n)
{
a[k].sc=c[j].sc;
a[k].id=c[j].id;
a[k].w=c[j].w;
j++; k++;
}
}
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,r,q;
cin>>n>>r>>q;
for (int i=1;i<=2*n;i++)
{cin>>a[i].sc; a[i].id=i;}
for (int i=1;i<=2*n;i++)
cin>>a[i].w;
sort(a+1,a+1+2*n,cmp);
while (r--)
{
for (int i=1,j=1;i<=2*n;i+=2,j++)
{
if (a[i].w>=a[i+1].w) //第一位赢第二位
{
b[j].sc=a[i].sc+1;
b[j].w=a[i].w;
b[j].id=a[i].id;
c[j].sc=a[i+1].sc;
c[j].w=a[i+1].w;
c[j].id=a[i+1].id;
}
else //第一位输第二位
{
c[j].sc=a[i].sc;
c[j].w=a[i].w;
c[j].id=a[i].id;
b[j].sc=a[i+1].sc+1;
b[j].w=a[i+1].w;
b[j].id=a[i+1].id;
}
}
mergesort(n);
}
cout<<a[q].id<<'\n';
return 0;
}
```
## **5.4 k小数**
- <a href="https://www.luogu.com.cn/problem/P1923" target=_blank>求第k小的数</a>
第一眼看上去可以直接用`sort`函数排序然后输出数组第k个数，但是可以看一下数据的大小：$5000000$。计算一下总的时间：$5000000\times log(5000000)=33,494,850$，超过了$1e8$的级别了，非常危险的时间了，所以我们需要一个更快的方法。
如果是第k小的数，那么在排序好的数组中小于它的元素的都在它左边，大于它的元素都在它右边。这就很类似于快速排序的**标头**，那么可以从快速排序来考虑求第k小的数。每次快速排序选定一个标头flag，然后会将小于flag的元素放在左边，大于flag的元素放在右边，放完后判断flag是否满足为第k小的数，满足则直接输出，否则判断下一次在哪一区间进行选定flag，此时我们使用的是快速排序的二分思想，所以从快速排序的原地分割版本出发。请看代码。
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[5000005];
void find_kth(int l,int r,int k)
{
int flag=a[(l+r)/2]; //找中间的数进行2分
int i=l,j=r;
do
{
while(a[i]<flag)
i++; //找左半部分大于中间数的
while(a[j]>flag)
j--; //找右半部分小于中间数的
if(i<=j)
{
swap(a[i++],a[j--]);
//左指针右移,右指针左移
}
}while(i<=j);
if(k<=j) find_kth(l,j,k);
else if(i<=k) find_kth(i,r,k);
else
{
cout<<a[k+1];
exit(0);
}
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,k;
cin>>n>>k;
for (int i=1;i<=n;i++)
cin>>a[i];
find_kth(1,n,k);
return 0;
}
```
C++的`algorithm`库也提供了求第k小的数有关的算法函数`nth_element`，用法如下：
```cpp
nth_element(array,array+n,array+k);
```
可以看出使用方法应为nth_element(数组起始地址,数组结束地址的后一个地址,需要确定位置地址)。在调用函数后，第三个参数地址处的值会变更为排序后对应的地址处的值，在这个地址前面的值会比这个地址后面的值小，但地址前面的值和地址后面的值并不一定是排好序的。
