十种经典排序算法整理

前言

排序应该算是我最早接触的一类算法。

刚开始只会冒泡，觉得反正最后能排好就行。后来慢慢接触到插入、归并、快排，才发现“排好”只是结果，中间怎么排差别很大。有的吃数据规模，有的吃额外空间，还有几种根本不比较大小，而是拿值域和数位换时间。

平时写题当然还是直接用 std::sort。这篇主要是把常见的十种排序重新捋一遍，留一份自己以后还能看懂的笔记。简单的少说几句，容易混或者容易写错的地方多记一点。

代码使用 C++17，默认都是升序。

先看一下区别

排序	最好	平均	最坏	额外空间	稳定
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	是
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	否
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	是
希尔排序	与步长有关	与步长有关	常见实现为 O(n^2)	O(1)	否
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	是
快速排序	O(n log n)	O(n log n)	O(n^2)	平均 O(log n)	否
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	否
计数排序	O(n + k)	O(n + k)	O(n + k)	O(n + k)	是
桶排序	O(n + k)	O(n + k)	O(n^2)	O(n + k)	看桶内排序
基数排序	O(d(n + b))	O(d(n + b))	O(d(n + b))	O(n + b)	是

n 是元素数量。后三种里还会出现几个量：k 可以表示值域大小或桶数，d 是数字位数，b 是进制大小。

稳定性以前看表的时候总觉得没什么用，其实它说的是相等元素会不会换位置。比如 (90, A) 原本在 (90, B) 前面，排完以后还是这个顺序，就是稳定。只排整数时不太看得出来，一旦元素还带着别的信息，就有区别了。

下面代码默认已经有：

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

冒泡排序

每次比较相邻的两个数，顺序反了就交换。一轮走完，最大的数会跑到最右边，下一轮就可以少看一个。

5 2 4 1
2 5 4 1
2 4 5 1
2 4 1 5

第一轮结束以后，5 已经不用再动了。

void bubbleSort(vector<int>& a) {
    int n = static_cast<int>(a.size());

    for (int end = n - 1; end > 0; --end) {
        bool swapped = false;

        for (int i = 0; i < end; ++i) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
                swapped = true;
            }
        }

        if (!swapped) break;
    }
}

swapped 是个很小的优化。如果一整轮都没有交换，数组已经有序，可以直接结束。这样最好情况能到 O(n)，不过平均和最坏还是 O(n^2)。

因为相等时不交换，所以它是稳定的。实际数据一大就不太行，入门意义大于实战意义。

选择排序

选择排序和冒泡看起来差不多，区别是它每轮先把最小值的位置找出来，最后只交换一次。

void selectionSort(vector<int>& a) {
    int n = static_cast<int>(a.size());

    for (int i = 0; i < n - 1; ++i) {
        int minPos = i;

        for (int j = i + 1; j < n; ++j) {
            if (a[j] < a[minPos]) {
                minPos = j;
            }
        }

        if (minPos != i) {
            swap(a[i], a[minPos]);
        }
    }
}

它不管原数组有没有序，每轮都得把后面剩下的数看完，所以最好也是 O(n^2)。

选择排序不稳定。比如 (2, A) (2, B) (1, X)，第一次交换后会变成 (1, X) (2, B) (2, A)，两个 2 的顺序反了。

插入排序

插入排序更像平时整理手里的牌。左边先看成已经排好，每次从右边拿一个数出来，把比它大的数往后挪，再把它插进去。

void insertionSort(vector<int>& a) {
    int n = static_cast<int>(a.size());

    for (int i = 1; i < n; ++i) {
        int value = a[i];
        int j = i - 1;

        while (j >= 0 && a[j] > value) {
            a[j + 1] = a[j];
            --j;
        }

        a[j + 1] = value;
    }
}

这几个 O(n^2) 排序里，我觉得插入排序最有实际意义。数组本来就接近有序时，内层循环走不了几次，速度会接近 O(n)。一些复杂排序处理小区间时，也会切回插入排序。

这里判断写的是 a[j] > value，不是 >=。相等元素不往后挪，稳定性就保住了。

希尔排序

第一次看希尔排序时感觉它像是凭空多出来一堆步长，后来发现它就是把插入排序拉长了。

普通插入一次只能挪一格。如果一个很小的数在数组末尾，它要慢慢走到前面。希尔排序先取一个较大的 gap，让元素可以跨着移动，再逐渐把 gap 缩小，最后做一次 gap = 1 的插入排序。

void shellSort(vector<int>& a) {
    int n = static_cast<int>(a.size());

    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int value = a[i];
            int j = i;

            while (j >= gap && a[j - gap] > value) {
                a[j] = a[j - gap];
                j -= gap;
            }

            a[j] = value;
        }
    }
}

希尔排序的复杂度和步长序列关系很大，不能简单记成一个固定值。这里用的是最容易写的折半步长，最坏仍然可能到 O(n^2)。

相等元素可能在不同组里跨过彼此，所以它不稳定。

归并排序

归并开始有明显的分治味道了。

先把区间从中间拆成两半，分别排好，再把两个有序区间合起来。拆本身没什么，重点是合并：两个区间都有序，只要各放一个指针，每次取较小的那个就行。

void mergeRange(vector<int>& a, vector<int>& tmp,
                int left, int mid, int right) {
    int i = left;
    int j = mid + 1;
    int p = left;

    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            tmp[p++] = a[i++];
        } else {
            tmp[p++] = a[j++];
        }
    }

    while (i <= mid) tmp[p++] = a[i++];
    while (j <= right) tmp[p++] = a[j++];

    for (int k = left; k <= right; ++k) {
        a[k] = tmp[k];
    }
}

void mergeSort(vector<int>& a, vector<int>& tmp,
               int left, int right) {
    if (left >= right) return;

    int mid = left + (right - left) / 2;
    mergeSort(a, tmp, left, mid);
    mergeSort(a, tmp, mid + 1, right);
    mergeRange(a, tmp, left, mid, right);
}

void mergeSort(vector<int>& a) {
    if (a.empty()) return;

    vector<int> tmp(a.size());
    mergeSort(a, tmp, 0, static_cast<int>(a.size()) - 1);
}

每层合并总共处理 n 个元素，一共有 log n 层，因此无论原数组长什么样，复杂度都是 O(n log n)。

它的缺点也很直接：需要一个 O(n) 的辅助数组。合并时相等元素优先取左边，所以这份写法是稳定的。

快速排序

快排也是分治，不过顺序和归并反过来。它先选一个基准值 pivot，把小的放左边，大的放右边，然后递归处理两边，不需要最后再合并。

void quickSort(vector<int>& a, int left, int right) {
    if (left >= right) return;

    int i = left;
    int j = right;
    int pivot = a[left + (right - left) / 2];

    while (i <= j) {
        while (a[i] < pivot) ++i;
        while (a[j] > pivot) --j;

        if (i <= j) {
            swap(a[i], a[j]);
            ++i;
            --j;
        }
    }

    if (left < j) quickSort(a, left, j);
    if (i < right) quickSort(a, i, right);
}

void quickSort(vector<int>& a) {
    if (!a.empty()) {
        quickSort(a, 0, static_cast<int>(a.size()) - 1);
    }
}

分得比较均匀时是 O(n log n)。如果每次划分都很偏，递归会越来越深，最坏退化成 O(n^2)。实际实现通常会随机选基准、三数取中，或者递归太深时换别的算法。

这里还有个容易写炸的地方：遇到很多等于 pivot 的数时，交换以后 i 和 j 仍然要继续移动，不然可能卡在原地。

快排交换跨度比较大，不稳定。不过它平均性能和缓存表现都不错，通用内存排序里一直很常见。

堆排序

堆排序的思路不难，但几个孩子下标我隔一段时间就会忘。

大根堆里，父节点不小于两个孩子，所以堆顶一定是当前最大值。先把整个数组调整成大根堆，再不断把堆顶和末尾交换，缩小堆的范围，重新向下调整。

void heapify(vector<int>& a, int heapSize, int root) {
    while (true) {
        int largest = root;
        int left = root * 2 + 1;
        int right = root * 2 + 2;

        if (left < heapSize && a[left] > a[largest]) {
            largest = left;
        }

        if (right < heapSize && a[right] > a[largest]) {
            largest = right;
        }

        if (largest == root) return;

        swap(a[root], a[largest]);
        root = largest;
    }
}

void heapSort(vector<int>& a) {
    int n = static_cast<int>(a.size());

    for (int i = n / 2 - 1; i >= 0; --i) {
        heapify(a, n, i);
    }

    for (int end = n - 1; end > 0; --end) {
        swap(a[0], a[end]);
        heapify(a, end, 0);
    }
}

从最后一个非叶子节点开始建堆，整个建堆过程是 O(n)。后面取 n 次堆顶，每次调整 O(log n)，总复杂度为 O(n log n)。

堆排序原地，而且最坏复杂度也有保证。缺点是下标访问比较跳，实际常数通常没有快排好看，稳定性也没有。

计数排序

从这里开始就不是比较排序了。

计数排序不关心两个数谁大谁小，而是统计每个值出现了几次。比如 [3, 1, 2, 3]，统计出来就是：

数值：1 2 3
次数：1 1 2

下面这份写法支持负数。前缀和表示每个值在结果数组中的结束位置，再从后往前放回去，就能保持稳定。

vector<int> countingSort(const vector<int>& a) {
    if (a.empty()) return {};

    auto [minIt, maxIt] = minmax_element(a.begin(), a.end());
    int minValue = *minIt;
    int maxValue = *maxIt;
    long long range = static_cast<long long>(maxValue) - minValue + 1;

    vector<int> cnt(static_cast<size_t>(range), 0);

    for (int value : a) {
        size_t pos = static_cast<size_t>(
            static_cast<long long>(value) - minValue
        );
        ++cnt[pos];
    }

    for (size_t i = 1; i < cnt.size(); ++i) {
        cnt[i] += cnt[i - 1];
    }

    vector<int> ans(a.size());

    for (size_t i = a.size(); i-- > 0;) {
        size_t pos = static_cast<size_t>(
            static_cast<long long>(a[i]) - minValue
        );
        ans[static_cast<size_t>(--cnt[pos])] = a[i];
    }

    return ans;
}

复杂度是 O(n + k)，k 是值域大小。这个算法最怕的不是数多，而是值域离谱。

如果只有十个数，最小值是 -10^9，最大值是 10^9，为了它们开几十亿个位置，内存直接就没了。所以看到整数也不能无脑上计数排序，先看最大值和最小值差多少。

桶排序

桶排序和计数排序名字有点像，但做法不是一回事。

它先把值域切成几段，每段是一个桶。元素落进对应的桶以后，桶内各自排序，最后按桶的顺序拼起来。

vector<int> bucketSort(const vector<int>& a, int width = 10) {
    if (a.empty()) return {};
    if (width <= 0) throw invalid_argument("width must be positive");

    auto [minIt, maxIt] = minmax_element(a.begin(), a.end());
    int minValue = *minIt;
    int maxValue = *maxIt;

    long long bucketCount =
        (static_cast<long long>(maxValue) - minValue) / width + 1;
    vector<vector<int>> buckets(static_cast<size_t>(bucketCount));

    for (int value : a) {
        size_t id = static_cast<size_t>(
            (static_cast<long long>(value) - minValue) / width
        );
        buckets[id].push_back(value);
    }

    vector<int> ans;
    ans.reserve(a.size());

    for (auto& bucket : buckets) {
        // 桶内使用插入排序
        for (size_t i = 1; i < bucket.size(); ++i) {
            int value = bucket[i];
            size_t j = i;

            while (j > 0 && bucket[j - 1] > value) {
                bucket[j] = bucket[j - 1];
                --j;
            }

            bucket[j] = value;
        }

        ans.insert(ans.end(), bucket.begin(), bucket.end());
    }

    return ans;
}

数据分得均匀时，每个桶里的元素都不多，速度可以接近线性。如果所有数都挤进同一个桶，那就完全看桶内排序了，这份实现会退化到 O(n^2)。

所以桶的数量不是越多越好。桶太少会挤，太多又浪费空间。它比较吃数据分布，适合在能估计范围的时候用。

基数排序

基数排序第一次看有点奇怪：它不比较完整数字，而是先按个位排，再按十位、百位一直往上排。

原数组：170 45 75 90
按个位：170 90 45 75
按十位：170 45 75 90
按百位：45 75 90 170

每一轮必须使用稳定排序，不然上一轮排好的低位顺序会被打乱。这里每一位都用一次计数排序。

void countDigit(vector<int>& a, long long exp) {
    array<int, 10> cnt{};
    vector<int> ans(a.size());

    for (int value : a) {
        int digit = static_cast<int>((value / exp) % 10);
        ++cnt[digit];
    }

    for (int i = 1; i < 10; ++i) {
        cnt[i] += cnt[i - 1];
    }

    for (size_t i = a.size(); i-- > 0;) {
        int digit = static_cast<int>((a[i] / exp) % 10);
        ans[static_cast<size_t>(--cnt[digit])] = a[i];
    }

    a.swap(ans);
}

void radixSort(vector<int>& a) {
    if (a.empty()) return;

    if (any_of(a.begin(), a.end(), [](int value) {
            return value < 0;
        })) {
        throw invalid_argument("this template only accepts non-negative integers");
    }

    int maxValue = *max_element(a.begin(), a.end());

    for (long long exp = 1; maxValue / exp > 0; exp *= 10) {
        countDigit(a, exp);
    }
}

这份模板只处理非负整数。负数可以拆出来单独排，不过还要留意 INT_MIN 直接取绝对值会溢出，所以这里没有硬塞进同一份代码。

最大数字有 d 位时，总复杂度是 O(d(n + b))。十进制下 b = 10，位数有限时确实很快。

最后怎么选

把十种放在一起以后，大概是这样：

• 冒泡和选择主要负责入门。
• 插入很适合小数组或者接近有序的数据。
• 希尔比普通插入快不少，但性能和步长绑得很紧。
• 归并稳定，复杂度也稳，就是要多开一块空间。
• 快排平均很快，最坏会退化，基准和划分写法都很重要。
• 堆排原地，最坏也是 O(n log n)，实际常数通常不占优势。
• 计数排序看值域。
• 桶排序看分布。
• 基数排序看位数，而且每一轮必须稳定。

实际写题该用 std::sort 还是用 std::sort。手写这些主要还是为了弄清它们到底利用了什么信息，以及题目给出特殊限制时，脑子里不至于只剩下一种做法。

参考

• 菜鸟教程：十大经典排序算法
• hustcc/JS-Sorting-Algorithm