1 基本概念

1.1 介绍

排序算法是指能将一个序列（例如数组）依照特定排序方式进行排列的一类算法。排序算法的用途很广泛，一些算法（例如二分查找）也需要在序列经过排序算法的处理后才能正确的运转。

1.2 算法分析

排序算法通常有以下分析指标：

• 时间复杂度（最差、平均和最好）：是衡量算法时间效率的一个指标，采用大O表示法。假设问题规模（序列大小）为 n，则时间复杂度从低到高依次为O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)

• 空间复杂度：是衡量算法内存使用量的一个指标，也采用大O表示法。注意空间复杂度主要表示的是除问题规模以外的额外空间使用量。

• 稳定性：是用来描述算法的排序特性。稳定的排序算法会让原序列中一些相等关键字值的元素维持相对次序。

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)

不稳定的排序算法可能会改变相等关键字值的元素的相对次序，但是稳定的排序算法从来不会这样。不稳定的排序算法可以被特别地实现为稳定的，实现的一个方式是使用第二关键字。然而，这会引起额外的空间使用，因为需要存储第二关键字的信息。

2 基于比较的排序算法

2.1 朴素做法-选择排序

最容易想到的排序思路应该是这样：依次从剩余序列中找出最小值并显示。这实现起来很容易，请看代码。

//从小到大排序
//有缺陷
for (int i=0;i<n;i++)    //有多少个元素就多少轮
{
    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;    //防止重复选取
}

代码能够成功运行并得到想要的结果，但存在缺陷，来分析一下：

1. 该段代码的结果是直接输出的，无法使用排序之后的序列。

2. 需要使用INT_MAX宏，即需确定一个上限值，不够通用。

所以需要改进一下，值得高兴的是，这种改动十分简单：通过比较大小并交换元素使对应位置上的元素为对应的排序，第一轮确定第一小的元素，第二轮确定第二小的元素，依次类推。

for (int i=0;i<n;i++)
    for (int j=i+1;j<n;j++)
        if (array[i]>array[j]) swap(array[i],array[j]);    //交换

通过这样，每轮比较出的最小元素就在对应的位置上，经过序列大小的轮次后就变成了有序的数组。

这样的排序方法，称为选择排序。比较次数为\frac{n*(n-1)}{2}​次，交换次数为0\sim\frac{n*(n-1)}{2}次，可得时间复杂度为O(n^2)。不需要额外的空间，所以空间复杂度为O(1)。选择排序进行的交换是跨越式交换，即不是相邻元素的交换，这样的交换方式使得选择排序是不稳定的排序算法。

2.2 相邻交换-冒泡排序

由选择排序的比较思想延申，我们可以有一个不一样的比较做法：对数组进行遍历，每次比较当前元素与其相邻的后面的元素，如果当前元素大于其相邻的后面的元素，就交换它们的位置。一遍循环结束后最后一个元素必定是比其前面的元素都大，这样只要让后面的循环依次减小范围，循环n-1次就可以把数组排序好，请看代码。

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)，但就平均而言，冒泡排序的时间复杂度为O(n^2)。冒泡排序不需要额外的空间，并且由于冒泡排序的相邻式交换，所以冒泡排序是稳定的排序算法。冒泡排序也可以进行反向的实现（让较大的元素经由交换慢慢“沉”到数组的尾端）。

2.3 扑克牌-插入排序

斗地主大家应该都玩过，在斗地主正式开局前一般都会把自己的牌先理一下，也就是排好顺序。发牌一般不是一次性发完的，我们每拿到牌就理一下，保证自己手上的牌是有序的。假设牌是一张一张发的，这样理牌的方式就叫作插入排序。

举一个例子，对于发牌的序列[5,3,7,4]:

• 第一张发来的是[5]，空手拿，手牌变成[5]。

• 第二张发来的是[3]，应该要插在[5]的左边，手牌变成[3,5]。

• 第三张发来的是[7]，应该要插在[5]的右边，手牌变成[3,5,7]。

• 第三张发来的是[4]，应该要插在[5]的左边，手牌变成[3,4,5,7]。

转换到代码的流程：

1. 定义存放结果的数组result，遍历原数组，对除第一个元素以外的每个元素执行2，3的操作。

2. 寻找元素应该插入在result数组的位置。

3. 在result数组中将该位置后面的元素往后移一位，腾出位置，然后将该元素放入。

请看代码。

int a[6]={5,4,2,6,3,1};

for (int i=1;i<6;i++)
{
    int j,temp=a[i];
    for (j=i;j;j--)
        if (temp<a[j-1])
            a[j]=a[j-1];    //避免数据丢失
        else
            break;
    a[j]=temp;
}

选择了从后往前遍历并移动元素，这是为了避免移动造成元素的丢失。插入排序存在最好情况和最坏情况。假设我们要求的是按照升序来排，那么最好情况就是数组元素初始就是升序有序的，在这种情况下，需要进行n-1次比较，不需要移动；最坏情况是数组元素初始是倒序有序的，那么此时需要进行\frac{n(n-1)}{2}次比较，\frac{n(n-1)}{2}次移动。平均来说插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)。在C++STL的sort函数和stdlib的qsort函数中，都将插入排序作为快速排序的补充，用于少量元素的排序。插入排序是稳定的。

2.4 分治和归并-归并排序

归并排序是创建在分治和归并操作上的一个排序算法，其基本原理如下：

• 分治：递归地把当前数组平分为两半直到当前数组长度为1（数组长度为1必定有序）。

• 归并：在保持数组元素有序的条件下将上一步得到的有序数组两两合并到一起。

请看代码。

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

归并排序采用二分，其递归树高度为\log_{2}{n}，每一层上都会对序列的每个元素进行处理，所以其时间复杂度是稳定在O(n\log n)的，不受数组初始状态影响。并且由于没有跨越式交换，所以它是一个稳定的排序算法。归并排序的缺点在于它需要使用一个辅助数组，这使得空间复杂度达到了O(n)。

2.5 标头-快速排序

在军训的时候，教官在第一列队的时候都会让我们以最高的那个人为标头从高到低排列，其实以标头进行排序也是一个很好的思路，你可以用标头来这样排序：

1. 随机选一个人作为标头。

2. 比他矮的人都到他左边，比他高的人都到他右边。

3. 对他左边，右边的人重复1，2的操作直到有序。

这样的排序称为快速排序，请看代码。

//有缺陷
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. 依此类推......

在这个例子中，递归树的高度将达到n，而每层最多要处理所有的元素，所以时间复杂度达到了O(n^2)！可以发现对于这个例子，快速排序做了许多的无用功，并且这个数组本身就是有序的！问题应该出现在flag的设定上，其设定选取数组区间[l,r]最左端的值，恰好对于这个例子，每轮数组区间[l,r]最左端的值都是最小值，标头的左右两半非常不平衡（元素都在右边了），事实上，要让快速排序达到理想的性能，每次flag取到的值应当是中间大小的值（左右两半平衡）。

可能你会想到取数组区间[l,r]中间位置的值？但是这样同样会有不平衡的情况，正确的做法是取随机数：

int flag=array[rand()%(r-l+1)+l];    //随机取l~r中的一个数

如果每次都能取到数组区间的中位数元素，那么排序算法的时间复杂度为O(n\log n)，而flag取数组区间[l,r]的一个随机元素，时间复杂度是有保证的，平均时间复杂度为O(n\log n)。由于元素是类似归并排序的放置而不是跨越式交换，故这种情况下的快速排序是稳定的。

上述排序算法实现的空间复杂度是O(n)，因为使用了辅助数组。然而，还有一种不需要辅助数组的快速排序，称为快速排序的原地分割版本，通过元素交换实现。请看代码。

void quicksort(int l,int r)
{
    int flag=array[rand()%(r-l+1)+l];    //随机取l~r中的一个数
    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);
}

因为是跨越式交换，所以这个版本的快速排序算法是不稳定的。该实现的空间复杂度为O(\log n)。

2.6 总结

下面对以上算法做一个简要的比较：

上述的排序方法都是基于比较的排序方法，基于比较的排序方法，最好只能达到O(n\log n)的时间复杂度。

3 不基于比较的排序算法

3.1 计数排序

计数排序是一个线性时间的排序算法。计数排序使用一个额外的数组count，其中第i个元素表示原数组中值等于i的元素的个数，这样就能实现排序。简单描述一下流程：

1. 定义存放结果的数组result，遍历原数组，统计个数到数组count。

2. 求数组count的前缀和。

3. 反向填充数组result。

请看代码。

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=0;i<6;i++)
        result[--count[array[i]]]=array[i];
}

由于用来计数的数组count的长度取决于原数组中元素的范围，这使得计数排序对于范围很大的数组，需要大量的内存。计数排序的时间复杂度为O(n+k)，空间复杂度为O(n+k)，其中n表示元数组的大小，k表示原数组中元素的范围。对于同一个数i，反向填充时--count[array[i]]可以保证相对位置不变，故计数排序是稳定的。

3.2 基数排序

基数排序本身是一个用于整数排序的排序算法。其原理是按数位低到高（或者高到低）每轮按照同一个数位的大小进行整理（类似于计数排序）并按大小重新排列。由于整数也可以表达字符串和特定格式的浮点数，所以基数排序也不是只能用于整数。

转换到代码的流程：

1. 对齐原数组中元素的数位，数位较少的元素前面补零。

2. 从数位最低位（或者最高位）开始，依据数位数字大小进行整理，然后重新排列数字。这样从最低位到最高位都执行一遍后，数组就有序了。

请看代码。

int array[6]={50,17,82,31,5,32};
vector<int> tank[10];    //10个数字

int sorted(int n,int x)    //整理，n是数字，x是数位
{
    while (x--)
        n/=10;
    return n%10;
}

int main()
{
    for (int i=0;i<2;i++)    //从低到高位
    {
        for (int j=0;j<6;j++)
            tank[sorted(array[j],i)].push_back(array[j]);

        for (int j=0,cnt=0;j<10;j++)    //重新排列数字
        {
            if (tank[j].size()>0)
            {
                for (auto k:tank[j])
                    array[cnt++]=k;
                tank[j].clear();
            }
        }
    }
}

基数排序的时间复杂度为O(nR)，空间复杂度为O(n+R)，其中n是原数组的大小，R是数位数。注意这个时间复杂度不一定优于O(n\log n)，但是在大多数情况下，R都比\log n要小。它是稳定的排序算法。

3.3 总结

下面对以上算法做一个简要的比较：

4 进阶排序算法使用

4.1 C++STL sort

C++的algorithm库提供了排序有关的算法函数，其中比较常用的就是sort函数，sort函数实际上是一个混合使用排序（插入、快速排序等）的函数，根据数据规模来确定一个最快的排序方法。

如何使用sort函数？现在有一个数组array，从下标0开始存了n个数据，则应该这样使用：

sort(array,array+n);

可以看出使用方法是sort(排序起始地址,排序结束地址的后一个地址)，相当于是一个左闭右开区间。

sort可以对各种类型的数组或者C++ STL容器进行排序。当没有给定第三个参数（cmp函数或functor对象）时，sort函数默认进行升序排序，前提是数组或容器的元素的数据类型定义了<运算符（即该类型可以作为<运算符的运算对象）。如果没有，可以给定cmp函数或functor对象作为sort函数的第三个参数或者重载该数据类型的<运算符，除此之外这些还可以用来实现降序排序和多关键字的排序。下面给出降序排序的cmp函数，请看代码。

//降序排序一个int类型的数组
bool cmp(int x,int y)
{
    return x>y;
}

现在来说明一下上述的原理。cmp函数的返回类型为bool，形参类型为元素的类型，cmp函数的返回值决定了顺序。来形象的解释一下，首先x和y之间的顺序一定是x在前面而y在后面，如果返回true，那么x和y的相对顺序不会改变（例如x>y成立），如果返回false，他们之间的相对顺序会对调（例如x>y不成立），那这样看来，就会使得最终结果是倒序。也就是让大的到前面来，小的到后面去。

除了sort函数外，还有stable_sort函数和partial_sort函数，它们分别代表稳定排序函数和部分排序函数，用法与sort函数相同，但时间和空间复杂度有所区别，这里不做介绍。

4.2 多关键字排序

在生活中的数据往往是有多个维度的，在排序时需要考虑多个维度之间的顺序，我们把这些维度称为关键字，在进行排序时，首先要指定第一关键字，这是排序时的首选依据，对于第一关键字相等的数据，还可以指定第二关键字，依此类推。

要实现多关键字排序，只需要在比较和赋值部分进行修改（注意不基于比较的排序算法需要进行另外的修改）。以使用sort函数为例，需要这样修改cmp函数，请看代码。

struct node
{
    int key_first,key_second;    //第一关键字和第二关键字
}array[10];

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 车厢重组

题目中有两点很清楚：相邻两节车厢的位置交换和从小到大排列，这就很容易想到是冒泡排序的模拟。

对于相邻交换（有一定判断条件）使得数组有序（对于题目所要求的顺序），计算交换次数的问题我们可以使用冒泡排序来模拟。请看代码。

#include<bits/stdc++.h>
using namespace std;

int a[10005];

int main()
{
    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 逆序计数

逆序对数是一个很经典的问题，它可以通过树状数组来求得。当然除了树状数组的外，归并排序同样是可以求逆序对数的，下面来看看。

在归并排序的归并步骤中，归并的两个子数组都是一左一右的，也就是说左边子数组中的元素的位置都在右边子数组中的元素的位置的前面，并且每个子数组中的元素都已经是有序的，根据这样的性质在合并过程中进行判断就可以求逆序对数，请看代码。

int a[100005],p[100005];
long long ans;    //逆序对数范围在1~n(n-1)/2内，一般会超出int类型的范围

void mergesort(int l,int r)
{
    if(l>=r) return;

    int mid=l+r>>1;
    mergesort(l,mid);
    mergesort(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 二路归并

题目意思很清楚，我们需要先知道初始的选手排名情况以分配选手进行比赛，比赛后更新选手排名情况继续分配选手进行比赛，一直重复直到比赛结束。需要记录的信息有三个：选手实力值，分数和编号，这是一个多关键字排序，所以想到使用sort函数，但你会发现这种做法会导致超时，因为总的操作次数大概是O(2NR\log 2N)，对于题目中的数据范围来说已经超过10^8的级别了。

怎么去改进？可以发现，每轮比赛结束后胜利者和失败者这两类人的顺序是正好有序的，怎么将两个有序的变成一个有序的，那这就自然联想到归并排序了，所以并不需要在每轮比赛后都进行整体的排序，只需要在每轮比赛结束后把胜利者和失败者两类人都放到对应的子数组中，然后对子数组进行归并即可。具体思路如下：

1. 用sort函数先排序一次（还未比赛之前）。

2. 模拟比赛，在每轮比赛结束后把胜利者和失败者两类人都放到到对应的子数组中。

3. 归并胜利者和失败者两个子数组。

4. 重复操作2，3直到完成比赛。

请看代码。

#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()
{
    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小数

第一眼看上去感觉是可以直接用sort函数排序然后输出数组的第k个元素，但看一下数据的大小：5\times 10^6。计算一下总的时间：5\times 10^6\times\log_2(5\times 10^6)\approx 1.1\times 10^8，已经是非常危险的时间。所以需要一个更快的方法。

题目只要求求第k小的数，第k小的数坐落在数组的某一个位置，但可以清楚的是在排序好的数组中小于它的元素的都在它左边，大于它的元素都在它右边，这不就是我们在快速排序中讲到的标头吗。其实只需要找到这个标头就行，需要对快速排序进行调整。快速排序的每轮都会选定一个标头flag，然后会将小于flag的元素放在左边，大于flag的元素放在右边，而这个flag其实一轮过后就确定了它的最终位置。那么就可以在一轮结束后查看flag的位置是否在第k位，是的话这就是题目所求，不是的话就选择左右的部分继续排序。由于每轮进一步减少了排序的范围，所以可以节省大量的时间，请看代码。

#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，用法如下：

nth_element(array,array+n,array+k);

可以看出使用方法应为nth_element(数组起始地址,数组结束地址的后一个地址,需要确定位置地址)。在调用函数后，第三个参数地址处的值会变更为第k小的数的值，在这个地址前面的值会比这个地址后面的值小，但地址前面的值和地址后面的值并不一定是排好序的。

更新日志：
2024.8.6 - 文章全面更新