十大排序总结

发表于 2022-04-03 更新于 2025-11-30 本文字数： 5.9k 阅读时长 ≈ 21 分钟

一、简单排序

定义：对于下标$i<j$，如果$A[i]>A[j]$，则称$(i,j)$是一对逆序对（inversion）
定理：任意$N$个不同元素组成的序列平均具有$N(N-1)/4$个逆序对。
定理：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为$Ω(N^2)$

1. 冒泡排序

时间复杂度：$O(N^2)$
最好情况下的时间复杂度，有序$O(N)$
空间复杂度：$O(1)$
稳定（比较相等时，是不做交换的）
end标记可以提前结束
链表也可用
每次交换都会消除一对逆序对
- 如果$I$是逆序对的个数，时间复杂度是$O(N+I)$

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int end = 1;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                end = 0;
            }
        }
        if (end)
            break;
    }
}

// 47838ms for 10w elements(0~10w random)
public static void BubbleSort<T>(IList<T> arr) where T : IComparable<T>
{
    for (int last = arr.Count - 1; last > 0; --last)
    {
        var end = true;
        for (int i = 0; i < last; ++i)
        {
            if (arr[i].CompareTo(arr[i+1])>0)
            {
                Swap(arr, i, i + 1);
                end = false;
            }
        }
        if (end)
            break;
    }
}

2. 插入排序

时间复杂度：$O(N^2)$
最好情况下的时间复杂度，有序$O(N)$
空间复杂度：$O(1)$
稳定（比较相等时，是不做后移覆盖的）
冒泡需要swap，而这里是连续的后移覆盖，操作数更少
每次调整牌位都会消除一对逆序对
- 如果$I$是逆序对的个数，时间复杂度是$O(N+I)$
常被高级排序拿来搭配，小规模数据的最佳搭档（通常$N<64$）

void insertSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int cur = arr[i];
        int j = i - 1;
        for (; j >= 0 && arr[j] > cur; --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = cur;
    }
}

// 13514ms for 10w elements(0~10w random)
public static void InsertSort<T>(IList<T> arr) where T : IComparable<T>
{
    for (int i = 1; i < arr.Count; ++i)
    {
        var pre = i - 1;
        var origin = arr[i];
        for (; pre >= 0; --pre)
        {
            if (arr[pre].CompareTo(origin) > 0)
                arr[pre + 1] = arr[pre];
            else
                break;
        }
        arr[pre + 1] = origin;
    }
}

2.1 插入排序思考

插牌的时候，我们无法改变移动的次数，毕竟新的牌最终的位置是确定的。但是我们可以优化比较的次数：既然新的牌到来时，前面的牌都是有序的，那就可以通过二分查找进行优化。这样虽然移动次数是$O(N^2)$但是比较次会降为$O(NlogN)$。在对10w个数据的排序测试中，二分插入排序速度比普通插入排序快了接近一倍。

注意保证插入排序的稳定性，二分时是寻找最右侧的target，即相等时，是左侧指针移动

// 7588ms for 10w elements(0~10w random)
public static void BinaryInsertSort<T>(IList<T> arr, int l, int r) where T : IComparable<T>
{
    for (int i = l + 1; i <= r; ++i)
    {
        var origin = arr[i];
        int bl = l, br = i - 1;
        while (bl <= br)
        {
            int bm = (bl + br) >> 1;
            // 相等时，是左侧指针移动
            if (arr[bm].CompareTo(origin) > 0)
                br = bm - 1;
            else
                bl = bm + 1;
        }
        for (int t = i; t > bl; --t)
            arr[t] = arr[t - 1];
        arr[bl] = origin;
    }
}

3. 选择排序

最好/最坏时间复杂度：$O(N^2)$
空间复杂度：$O(1)$
不稳定：交换打破稳定性，例如对[4a,4b,1]的排序。
- 若想选择排序稳定，需要开辟新的数组空间；或者进行大量移位操作（交换改成插入）；或者排序的是链表

算法伪代码
void Selection_Sort(ElementType A[], int N) {
    // 其实外层循环N-1次就行了
    for (int i = 0; i < N; ++i) {
        /* 从A[i]到A[N-1]中找最小元，并将其位置赋给MinPosition */
        MinPosition = ScanForMin(A, i, N-1);
        /* 将未排序部分的最小元换到有序部分的最后位置 */
        Swap(A[i], A[MinPosition]);
    }
}

// 29051ms for 10w elements(0~10w random)
public static void SelectSort<T>(IList<T> arr) where T : IComparable<T>
{
    for (int i = 0; i < arr.Count - 1; ++i)
    {
        var minPosition = i;
        for (int j = i; j < arr.Count; ++j)
        {
            if (arr[j].CompareTo(arr[minPosition]) < 0)
                minPosition = j;
        }
        if (i != minPosition)
            Swap(arr, i, minPosition);
    }
}

二、高级排序

4. 希尔排序（由插入排序进化而来）

定义增量序列$D_M>D_{M-1}>…>D_1 = 1$，对每个$D_k$进行$D_k$间隔排序$(k = M, M-1, …, 1)$。值得注意的是：“$D_k$间隔”有序的序列，在执行“$D_{k-1}$间隔”排序后，仍然保持“$D_k$间隔”有序。这是希尔排序的前提！
增量元素的设计很重要，增量元素不互质，会导致小增量可能根本不起作用。

Hibbard增量序列：$D_k = 2^k - 1$，相邻元素互质，最坏情况复杂度是$Θ(N^{\frac{3}{2}})$
时间复杂度：$O(N^{\frac{4}{3}})$~$O(N^{\frac{3}{2}})$复杂度非常难以估算
空间复杂度：$O(1)$
不稳定（与插入排序不同了，因为希尔是跳跃交换的）
下面两个C++实现都一样，唯一区别就是插入排序外循环里面i增加的形式，第一种分开实现，第二种合并了

4.1 实现1（Ugly）

void shellSort(vector<int>& arr) {
    int n = arr.size();
    // 选择的增量序列是（2^k-1），可以跟随数组大小生成，但是为了简化算法代码，突出主题，在此固定长度了
    static vector<int> incre = { 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1 };
    for (int u = 0; u <incre.size(); ++u) { // 增量循环
        int width = incre[u];
        if (width > n) continue;
        for (int v = 0; v < width; ++v) { // 当前增量循环
            for (int i = width + v; i < n; i += width) { // 插入排序外循环
                int cur = arr[i];
                int j = i - width;
                for (; j >= 0 && arr[j] > cur; j -= width) // 插入排序内循环
                    arr[j + width] = arr[j];
                arr[j + width] = cur;
            }
        }
    }
}

4.2 实现2（浙大陈姥姥代码）

void shellSort(vector<int>& arr) {
    int n = arr.size();
    // 选择的增量序列是（2^k-1），可以跟随数组大小生成，但是为了简化算法代码，突出主题，在此固定长度了
    static vector<int> incre = { 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1 };
    for (int u = 0; u < incre.size(); ++u) { // 增量循环
        int width = incre[u];
        for (int i = width; i < n; ++i) { // 插入排序外循环
            int cur = arr[i];
            int j = i - width;
            for (; j >= 0 && arr[j] > cur; j -= width) // 插入排序内循环
                arr[j + width] = arr[j];
            arr[j + width] = cur;
        }
    }
}

4.3 C#实现（Good）

// 44ms for 10w elements(0~10w random)
public static int PowerOfTwoFloor(int n)
{
    n |= (n >> 1);
    n |= (n >> 2);
    n |= (n >> 4);
    n |= (n >> 8);
    n |= (n >> 16);
    return (n >> 1) + 1;
}

public static void ShellSort<T>(IList<T> arr) where T : IComparable<T>
{
    int power = PowerOfTwoFloor(arr.Count);
    for (int delta = power - 1; delta >= 1; delta = power - 1)
    {
        // 第一张牌后，后续是++
        for (int cur = delta; cur < arr.Count; ++cur)
        {
            var temp = arr[cur];
            var pre = cur - delta;
            // 往前探时，是delta跨步
            for (; pre >= 0; pre -= delta)
            {
                if (arr[pre].CompareTo(temp) > 0)
                    arr[pre + delta] = arr[pre];
                else
                    break;
            }
            arr[pre + delta] = temp;
        }
        power >>= 1;
    }
}

5. 堆排序（由选择排序进化而来）

时间复杂度：$O(NlogN)$
空间复杂度：$O(1)$
不稳定（继承自选择排序）

5.1 C++实现

void downMethod(vector<int>& arr, int f, int sz) {
    int s = f * 2 + 1;
    int cur = arr[f];
    while(s < sz){
        if (s + 1 < sz && arr[s] < arr[s + 1]) // 兄弟值大，让位
            ++s;
        if (arr[s] <= cur) break; // 父亲值大，镇压
        arr[f] = arr[s]; // 儿子值大，禅位
        f = s; // 下一代的父亲
        s = f * 2 + 1; // 下一代的儿子
    }
    arr[f] = cur;
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    // 数组形成堆
    for (int p = (n - 2) / 2; p >= 0; --p)
        downMethod(arr, p, n);
    // 堆首尾交换进行排序
    for (int p = n-1; p > 0; --p) {
        swap(arr[0], arr[p]);
        downMethod(arr, 0, p);
    }
}

5.2 C#实现（借助现有堆）

5.2.1 官方库（会有额外存储开销）

// 45ms for 10w elements(0~10w random)
public static void HeapSort<T>(IList<T> arr) where T : IComparable<T>
{
    var pq = new PriorityQueue<T, T>(arr.Select(e => (e, e)));
    int index = 0;
    while (pq.Count > 0)
    {
        var max = pq.Dequeue();
        arr[index++] = max;
    }
}

5.2.2 自己实现的堆（直接原地建堆）

// 39ms for 10w elements(0~10w random)
public static void HeapSort<T>(IList<T> arr) where T : IComparable<T>
{
    var pq = new MyPriorityQueue<T>(arr);
    var count = arr.Count;
    for (int i = 0; i < count - 1; ++i)
    {
        var max = pq.Pop();
        // 此时count - 1 - i及后面的元素已经不在堆里！
        // 因此可以放心改变
        arr[count - 1 - i] = max;
    }
}

5.2.3 通过下滤操作实现（原地建堆+原地下滤）

下滤操作用于排序时，一定要考虑到当前数组的实际大小

// 29ms for 10w elements(0~10w random)
public static void PriorityQueueDown<T>(IList<T> arr, int parent, int count) where T : IComparable<T>
{
    var temp = arr[parent];
    for (int child = (parent << 1) + 1; child < count; child = (parent << 1) + 1)
    {
        if (child + 1 < count && arr[child + 1].CompareTo(arr[child]) > 0)
            ++child;
        if (arr[child].CompareTo(temp) > 0)
            arr[parent] = arr[child];
        else
            break;
        parent = child;
    }
    arr[parent] = temp;
}

public static void HeapSort<T>(IList<T> arr) where T : IComparable<T>
{
    int count = arr.Count;
    for (int subRoot = (arr.Count - 2) >> 1; subRoot >= 0; --subRoot)
        PriorityQueueDown(arr, subRoot, count);
    for (int left = arr.Count - 1; left > 0; --left)
    {
        Swap(arr, 0, left);
        PriorityQueueDown(arr, 0, left);
    }
}

6. 归并排序

时间复杂度：$O(NlogN)$
空间复杂度：$O(N)$
稳定

6.1 递归版本

// [l, m] [m+1, r]
void mergeTwoArray(vector<int>& arr, vector<int>& trr, int l, int m, int r) {
    int i = l, j = m + 1, k = l;
    while (i <= m || j <= r) { // k <= r 一样
        int a = i <= m ? arr[i] : INT_MAX;
        int b = j <= r ? arr[j] : INT_MAX;
        if (a < b) ++i; // 每次i和j只能有一个增加
        else ++j;
        trr[k++] = a < b ? a : b;
    }
    while (l <= r) { // 拷贝回去
        arr[l] = trr[l];
        ++l;
    }
}

void mergeRecursion(vector<int>& arr, vector<int>& trr, int l, int r) {
    if (l == r) return;
    int m = l + ((r - l) >> 1);
    mergeRecursion(arr, trr, l, m);
    mergeRecursion(arr, trr, m + 1, r);
    mergeTwoArray(arr, trr, l, m, r);
}

void mergeSort(vector<int>& arr) {
    int n = arr.size();
    vector<int> trr(arr); // 避免频繁创建子数组
    mergeRecursion(arr, trr, 0, n - 1);
}

6.2 非递归版本

// [l, m] [m+1, r]
void mergeTwoArray(vector<int>& arr, vector<int>& trr, int l, int m, int r) {
    int i = l, j = m + 1, k = l;
    while (i <= m || j <= r) { // k <= r 一样
        int a = i <= m ? arr[i] : INT_MAX;
        int b = j <= r ? arr[j] : INT_MAX;
        if (a < b) ++i; // 每次i和j只能有一个增加
        else ++j;
        trr[k++] = a < b ? a : b;
    }
    // 不用拷贝回去...
}

void mergeSort(vector<int>& arr) {
    int n = arr.size();
    int range = 1; // 半径
    vector<int> trr(arr); // 避免频繁创建子数组
    while (range < n) {
        for (int i = 0; i < n; i += range*2) { // arr -> trr
            int m = i + range - 1;
            if (m >= n - 1) m = n - 1; // 不能break
            int r = i + range * 2 - 1;
            if (r >= n - 1) r = n - 1;
            mergeTwoArray(arr, trr, i, m, r); // arr->trr
        }
        range <<= 1;
        for (int i = 0; i < n; i += range*2) { // trr -> arr
            int m = i + range - 1;
            if (m >= n - 1) m = n - 1; // 不能break
            int r = i + range * 2 - 1;
            if (r >= n - 1) r = n - 1;
            mergeTwoArray(trr, arr, i, m, r); // trr->arr
        }
        range <<= 1;
    }
}

6.3 C#实现

// 28ms for 10w elements(0~10w random)
public static void MergeSort<T>(IList<T> arr) where T : IComparable<T>
{
    List<T> tempList = new(arr);
    //DoMergeSortRecursive(arr, tempList, 0, arr.Count - 1);
    DoMergeSortIterative(arr, tempList);
}

private static void DoMergeSortRecursive<T>(IList<T> arr, IList<T> tempList, int l, int r) where T : IComparable<T>
{
    if (l >= r)
        return;
    int m = (l + r) >> 1;
    DoMergeSortRecursive(arr, tempList, l, m);
    DoMergeSortRecursive(arr, tempList, m + 1, r);
    Merge(arr, tempList, l, m + 1, r);
    for (int i = l; i <= r; i++)
        arr[i] = tempList[i];
}

// 公用merge
private static void Merge<T>(IList<T> arr, IList<T> tempList, int lStart, int rStart, int rEnd) where T : IComparable<T>
{
    var lEnd = rStart - 1;
    var indexT = lStart;
    while (lStart <= lEnd && rStart <= rEnd)
    {
        if (arr[lStart].CompareTo(arr[rStart]) <= 0) tempList[indexT++] = arr[lStart++];
        else tempList[indexT++] = arr[rStart++];
    }
    while (lStart <= lEnd) tempList[indexT++] = arr[lStart++];
    while (rStart <= rEnd) tempList[indexT++] = arr[rStart++];
}

// 这一步最是精髓
private static void DoMergeSortIterative<T>(IList<T> arr, IList<T> tempList) where T : IComparable<T>
{
    int mergeSize = 1;
    while (mergeSize < arr.Count)
    {
        DoMergeOnce(arr, tempList, mergeSize);
        mergeSize <<= 1;
        DoMergeOnce(tempList, arr, mergeSize);
        mergeSize <<= 1;
    }
}

private static void DoMergeOnce<T>(IList<T> arr, IList<T> tempList, int mergeSize) where T : IComparable<T>
{
    int lStart = 0;
    for (; lStart + mergeSize < arr.Count; lStart += mergeSize << 1)
    {
        int rStart = lStart + mergeSize;
        int rEnd = Math.Min(rStart + mergeSize - 1, arr.Count - 1);
        Merge(arr, tempList, lStart, rStart, rEnd);
    }
    if (lStart < arr.Count)
        Merge(arr, tempList, lStart, arr.Count, arr.Count - 1);
}

6.4 归并排序思考

归并时，一定要对等长的数据进行归并吗，比如[1,2,3,6,10]和[4,5,7,9,12,14,17]。第一个序列的最后一个位（最大值）在第二个序列里应该排序到12前面；第二个序列的第一位（最小值）在第一个序列里应该排序到3后面。所以实际归并的序列应该是...[6,10]和[4,5,7,9]...，那针对这次归并，我其实只需要大小为2的临时数组寄放最短的序列，然后归并到原数组。当然，普通的归并排序，是事先创建好的一整块同大小的内存，以防止频繁重复的申请内存，所以实际的内存看来是省不下来的，但是数据搬运和比较的次数是有望减少的。

7. 快速排序

时间复杂度：$O(NlogN)$
空间复杂度：栈上$O(logN)$
不稳定
注意1：遇到l和r指向相等时，需要交换，不然遇到全1的数组，退化为n^2
注意2：快排在数据范围较小时（r-l<threshold）直接使用插入排序可有效优化速度

7.1 实现1（朴素版）

void quickRecursion(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int oldl = l, oldr = r;
    // 选 [枢纽]
    int pivot = arr[l];
    // 排序
    ++r;
    while (l < r) {
        while (l < r && arr[--r] > pivot); // 右侧先动是安全的
        while (l < r && arr[++l] < pivot); // 左侧后动
        if (l < r) swap(arr[l], arr[r]);
    }
    swap(arr[oldl], arr[l]);
    quickRecursion(arr, oldl, r - 1);
    quickRecursion(arr, r + 1, oldr);
}

void quickSort(vector<int>& arr) {
    int n = arr.size();
    quickRecursion(arr, 0, n - 1);
}

7.2 实现2（改进朴素版）

int pivot = arr[l];
// 改为
int randomPos = l + rand()%(r-l+1);
swap(arr[l], arr[randomPos]);
int pivot = arr[l];

7.3 实现3（中间值枢纽）

// 三数选中间数并将最小值放在l，最大值放在r，中间值(pivot)放在l+1
// 陈姥姥代码里是放在r-1的，这样肯定正确因为m肯定<r
// 我为了兼容朴素版的大部分代码，选择放在l+1，这样由于m可能等于l，所以需要多一次特殊点判断
int median3(vector<int>& arr, int l, int r) {
    int m = l + ((r - l) >> 1);
    if (arr[l] > arr[m])
        swap(arr[l], arr[m]);
    if (arr[l] > arr[r])
        swap(arr[l], arr[r]);
    if (arr[m] > arr[r])
        swap(arr[m], arr[r]);
    if (l == m) return arr[l]; // 特殊点
    swap(arr[m], arr[l + 1]);
    return arr[l + 1];
}

void quickRecursion(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int oldl = l, oldr = r;
    // 选 [枢纽]
    int pivot = median3(arr, l, r);

    // 排序
    ++l; // 注意：两端收缩了一位
    while (l < r) {
        while (l < r && arr[--r] > pivot); // 右侧先动是安全的
        while (l < r && arr[++l] < pivot); // 左侧后动
        if (l < r) swap(arr[l], arr[r]);
    }
    swap(arr[oldl + 1], arr[l]); // 注意：pivot枢纽放在了l+1位置
    quickRecursion(arr, oldl, r - 1);
    quickRecursion(arr, r + 1, oldr);
}

void quickSort(vector<int>& arr) {
    int n = arr.size();
    quickRecursion(arr, 0, n - 1);
}

7.4 实现4（有限制）

虽然代码看起来很简洁，但是有如下问题：

极端情况会退化为n^2算法
正因如此，在我的实验中，对3w个分布0~99的数字排序，会栈溢出（异常结束，main函数return 非0）。其实前面的方法里，移动i和j时如果>改为>=、<改为<=也会出现这种问题哦。因此在数据分布较窄时，这种方法无疑是低效的
快速排序中，任何通过单边移动的方法，在面对窄数据时，都会向$O(N^2)$退化。而即便是两边从中间移动，如果比较相等时不停下交换，也会在面对窄数据时，退化成$O(N^2)$

void quickRecursion(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    // 选 [枢纽] 可改进随机化但效果还是差
    int pivot = arr[l];

    // 排序
    int j = l;
    for (int i = l + 1; i <= r; ++i) {
        if (arr[i] < pivot) {
            ++j;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[j], arr[l]);

    quickRecursion(arr, l, j - 1);
    quickRecursion(arr, j + 1, r);
}

void quickSort(vector<int>& arr) {
    int n = arr.size();
    quickRecursion(arr, 0, n - 1);
}

7.5 C#实现

// 快速排序
public static void QuickSort<T>(IList<T> arr) where T : IComparable<T>
{
    DoQuickSort_1(arr, 0, arr.Count - 1);
}

// 23ms for 10w elements(0~10w random)
// 21ms for 10w elements(0~100 random)
// 快速排序（自己随便实现的）
private static void DoQuickSort_1<T>(IList<T> arr, int l, int r) where T : IComparable<T>
{
    if (r - l < 16)
    {
        InsertSort(arr, l, r);
        return;
    }
    var pivot = arr[l];
    int indexL = l + 1, indexR = r;
    while (indexL < indexR)
    {
        bool moved = false;
        while (indexL < indexR && arr[indexL].CompareTo(pivot) < 0)
        {
            ++indexL;
            moved = true;
        }
        while (indexL < indexR && arr[indexR].CompareTo(pivot) > 0)
        {
            --indexR;
            moved = true;
        }
        Swap(arr, indexL, indexR);
        if (!moved)
        {
            ++indexL;
            --indexR;
        }
    }
    if (arr[indexL].CompareTo(pivot) >= 0)
        --indexL;
    Swap(arr, l, indexL);
    DoQuickSort_1(arr, l, indexL - 1);
    DoQuickSort_1(arr, indexL + 1, r);
}

// 18ms for 10w elements(0~10w random)
// 15ms for 10w elements(0~100 random)
// 快速排序（基础版）
private static void DoQuickSort_Scratch<T>(IList<T> arr, int l, int r) where T : IComparable<T>
{
    if (r - l < 16)
    {
        InsertSort(arr, l, r);
        return;
    }
    var pivot = arr[l];
    int indexL = l, indexR = r + 1;
    while (true)
    {
        // 因为左侧有哨兵，必须右侧先移动
        while (arr[--indexR].CompareTo(pivot) > 0) ; // 左侧枢纽作为哨兵，所以这里不需要判断指针大小
        while (indexL < indexR && arr[++indexL].CompareTo(pivot) < 0) ; // 右侧由于没有哨兵，所以需要判断指针大小
        if (indexL < indexR)
            Swap(arr, indexL, indexR);
        else
            break;
    }
    Swap(arr, l, indexL);
    DoQuickSort_Scratch(arr, l, indexL - 1);
    DoQuickSort_Scratch(arr, indexL + 1, r);
}

// 17ms for 10w elements(0~10w random)
// 14ms for 10w elements(0~100 random)
// 枢纽三选一中位数
private static void DoQuickSort_Three<T>(IList<T> arr, int l, int r) where T : IComparable<T>
{
    // 必须进行截断，否则只有两个元素，下面的代码indexR必会越界
    if (r - l < 16)
    {
        InsertSort(arr, l, r);
        return;
    }
    int m = (l + r) >> 1;
    if (arr[l].CompareTo(arr[m]) > 0)
        Swap(arr, l, m);
    if (arr[m].CompareTo(arr[r]) > 0)
        Swap(arr, m, r);
    if (arr[l].CompareTo(arr[m]) > 0)
        Swap(arr, l, m);
    Swap(arr, m, r - 1); // 锚点暂存右边第二位，这样即使只有两个元素，也是完全正确的
    var pivot = arr[r - 1];
    int indexL = l, indexR = r - 1;
    while (true)
    {
        // 下面的顺序无所谓
        while (arr[++indexL].CompareTo(pivot) < 0) ; // 左右侧都有哨兵，可以消去判断指针大小的语句
        while (arr[--indexR].CompareTo(pivot) > 0) ; // 左右侧都有哨兵，可以消去判断指针大小的语句
        if (indexL < indexR)
            Swap(arr, indexL, indexR);
        else
            break;
    }
    // 需要将数换回来，由于锚点在右侧，所以需要一个大于等于锚点的值，indexL满足；indexR是小于等于锚点的值，不满足
    Swap(arr, indexL, r - 1);
    DoQuickSort_Three(arr, l, indexL - 1);
    DoQuickSort_Three(arr, indexL + 1, r);
}

三、特殊排序

8. 计数排序（累加和的策略很巧妙）

时间复杂度：$O(B+N)$，B是数据范围一般较小，可认为是$O(N)$
空间复杂度：栈上$O(B+N)$ -> $O(N)$
稳定（实现的不好则不稳定，比如从前往后填）

void countingSort(vector<int>& arr) {
    int n = arr.size();
    int maxV = INT_MIN;
    for (auto& e : arr) maxV = maxV > e ? maxV : e;
    vector<int> counting(maxV + 1); // 计数数组
    vector<int> trr(arr); // 留作中转拷贝
    for (auto& e : arr) ++counting[e]; // 计数
    for (int i = 1; i < counting.size(); ++i) // 累加计数
        counting[i] = counting[i - 1] + counting[i];
    for (int i = n - 1; i >= 0; --i) { // 从后向前填：稳定的排序
        int pos = --counting[arr[i]];
        trr[pos] = arr[i];
    }
    for (int i = 0; i < n; ++i) // 拷回去
        arr[i] = trr[i];
}

9. 基数排序

时间复杂度：$O(Rs * N)$，Rs是数据最大值的位数一般较小，可认为是$O(N)$
空间复杂度：栈上$O(10 + N)$ -> $O(N)$
稳定（对MSD来说实现的不好则不稳定，比如从前往后填）
经常利用计数排序实现

9.1 LSD基数排序

最低位优先(Least Significant Digit first, LSD)，先排低位；再排高位
由于每一位介于0~9，所以对每一个基位排序时都可看做是分为10个桶的桶排序

// 获得一个int的某一位的数字
// 例如13247 r=0 -> 7 | r=1 -> 4 | r=2 -> 2 | r=3 -> 3 | r=4 -> 1 | r = 5 -> 0 
int getRadix(int num, int r) {
    static int radices[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
    num %= radices[r + 1];
    return num / radices[r];
}

void radixSortLSD(vector<int>& arr) {
    int n = arr.size();
    int maxV = INT_MIN;
    for (auto& e : arr) maxV = maxV > e ? maxV : e;
    int radixNum = 0;
    while (maxV) {
        ++radixNum;
        maxV /= 10;
    }
    vector<int> trr(arr); // 留作中转拷贝
    for (int r = 0; r < radixNum; ++r) {
        vector<int> counting(10); // 计数数组
        for (auto& e : arr) ++counting[getRadix(e, r)]; // 计数
        for (int i = 1; i < counting.size(); ++i) // 累加计数
            counting[i] = counting[i - 1] + counting[i];
        for (int i = n - 1; i >= 0; --i) {
            int pos = --counting[getRadix(arr[i], r)];
            trr[pos] = arr[i];
        }
        for (int i = 0; i < n; ++i) // 拷回去
            arr[i] = trr[i];
    }
}

// 17ms for 10w elements(0~10w random)
// 8ms for 10w elements(0~100 random)
// 基数排序（十六进制）
public static void RadixSort(IList<int> arr)
{
    List<List<int>> buckets = Enumerable.Range(0, 16).Select(_ => new List<int>()).ToList();
    uint mask = 0x0f;
    int shiftCount = 0;
    while (mask > 0)
    {
        foreach (var item in arr)
        {
            var index = (int)((item & mask) >> shiftCount);
            buckets[index].Add(item);
        }

        if (buckets[0].Count == arr.Count)
            break;

        var iterator = buckets.SelectMany(e => e);
        var i = 0;
        foreach (var item in iterator)
            arr[i++] = item;
        foreach (var bucket in buckets)
            bucket.Clear();
        mask <<= 4;
        shiftCount += 4;
    }
}

// 12ms for 10w elements(0~10w random)
// 6ms for 10w elements(0~100 random)
// 基数排序（十六进制）（计数优化）
public static void RadixCountSort(IList<int> arr)
{
    List<int> tempList = new(arr);
    uint mask = 0xf;
    int shiftCount = 0;
    while (mask > 0)
    {
        List<int> counting = Enumerable.Repeat(0, 16).ToList();
        foreach (var item in arr)
        {
            var index = (int)((item & mask) >> shiftCount);
            ++counting[index];
        }
        if (counting[0] == arr.Count)
            break;
        for (int i = 1; i < counting.Count; ++i)
            counting[i] += counting[i - 1];

        // 错误！因为arr继承自上一次低基排序的顺序
        // counting的计数又是默认从后往前
        // 因此，对本次基数的排序必须也是从后往前，这样才能保持低基的顺序不会被打乱
        // 它不是稳定不稳定的问题，而是排序会完全错误
        //foreach (var item in arr)
        //{
        //    var index = (int)((item & mask) >> shiftCount);
        //    tempList[--counting[index]] = item;
        //}

        // 必须是从后往前
        for (int i = arr.Count - 1; i >= 0; --i)
        {
            var index = (int)((arr[i] & mask) >> shiftCount);
            tempList[--counting[index]] = arr[i];
        }

        for (int i = 0; i < arr.Count; ++i)
            arr[i] = tempList[i];
        shiftCount += 4;
        mask <<= 4;
    }
}

9.2 MSD基数排序

最高位优先(Most Significant Digit first, MSD)，先排高位；再排低位
MSD一般采用递归写法：按高位分组，形成连续区段，然后在区段内递归处理低一位
与之前的计数策略不同，这里进行写入临时数组时，如果不采用从后往前的策略，虽然不至于排序错误，但是会使得排序不稳定

// 13ms for 10w elements(0~10w random)
// 6ms for 10w elements(0~100 random)
public static void MSD(IList<int> arr)
{
    List<int> trr = new(arr);
    var maxItem = int.MinValue;
    foreach (var item in trr)
        maxItem = Math.Max(maxItem, item);
    int shiftCount = 0;
    uint mask = 0x0000000f;
    while (maxItem > mask)
    {
        shiftCount += 4;
        maxItem >>= 4;
    }
    mask <<= shiftCount; // 得到最大的遮罩
    DoMSD(arr, trr, 0, arr.Count - 1, mask);
}

// 获得遮罩的额外位移次数
private static int ShiftCount(uint mask)
{
    var single = mask & -mask; // 可以快速获取二进制最低位的1
    int shiftCount = 0;
    while (single > 0)
    {
        ++shiftCount;
        single >>= 1;
    }
    return shiftCount - 1;
}

private static void DoMSD(IList<int> arr, IList<int> trr, int l, int r, uint mask)
{
    if (l >= r || mask == 0)
        return;

    var counting = Enumerable.Repeat(0, 16).ToList();
    var shiftCount = ShiftCount(mask);
    // l~r计数
    for (int i = l; i <= r; ++i)
    {
        var index = (int)((arr[i] & mask) >> shiftCount);
        ++counting[index];

    }
    for (int i = 1; i < counting.Count; ++i)
        counting[i] += counting[i - 1];

    /*
    * 从前往后，虽然不至于像LSD那样直接排序错误，但是会导致排序不稳定。之所以不会排序错误，
    * 是因为MSD是先序遍历的递归，每一层处理时只负责分组，不会包含次级排序的信息
    */
    //for (int i = l; i <= r; ++i)
    //{
    //    var index = (int)((arr[i] & mask) >> shiftCount);
    //    trr[--counting[index] + l] = arr[i]; // + l的偏移别忘了
    //}

    // 还是得从后往前进行
    for (int i = r; i >= l; --i)
    {
        var index = (int)((arr[i] & mask) >> shiftCount);
        trr[--counting[index] + l] = arr[i]; // + l的偏移别忘了
    }

    for (int i = l; i <= r; ++i)
        arr[i] = trr[i];
    for (int i = 0; i < 16; ++i)
    {
        if (i < 15)
            DoMSD(arr, trr, l + counting[i], l + counting[i + 1] - 1, mask >> 4);
        else
            DoMSD(arr, trr, l + counting[i], r, mask >> 4);
    }
}

10. 桶排序（更像是一种思路，而非特定的算法）

桶排序的时间复杂度和空间复杂度以及是不是稳定都看你采取的子排序算法
桶排序一般用于数据分布均匀的
桶排序用于遏制N^2、NlogN等复杂度的算法因数据量太大而带来的速度问题

void insertSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int cur = arr[i];
        int j = i - 1;
        for (; j >= 0 && arr[j] > cur; --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = cur;
    }
}

void bucketSort(vector<int>& arr) {
    int n = arr.size();
    int maxV = INT_MIN;
    for (auto& e : arr) maxV = maxV > e ? maxV : e;
    ++maxV;
    int bckNum = 10; // 分十个桶
    vector<vector<int>> buckets(bckNum, vector<int>());
    for (auto& e : arr) {
        int pos = e * 10 / maxV;
        buckets[pos].push_back(e); // 放进桶里
    }
    for (auto& b : buckets) { // 随意选取排序算法
        insertSort(b);
    }
    int k = 0;
    for (int i = 0; i < buckets.size(); ++i)
        for (int j = 0; j < buckets[i].size(); ++j)
            arr[k++] = buckets[i][j]; // 从桶里面拿出来
}

参考文献

浙江大学《数据结构》陈越何钦铭