排序 · Zwing's blog

冒泡排序

基础版

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。

void bubbleSort(vector<int>& v)
{
    // i < v.size()-1 最后一个元素不用排
    for (int i = 0; i < v.size()-1; i++)
    {
        // 最后的 i 个元素已排好
        for (int j = 0; j < v.size()-i-1; j++)
        {
            // 不取等确保稳定性
            if (v[j] > v[j+1])
            {
                swap(v[j], v[j+1]);
            }
        }
    }
}

时间复杂度：无论最好最坏\(O(n^2)\)
空间复杂度：\(O(1)\)
稳定性：稳定

原理简单，手搓容易

改良版

考虑如果给定一个有序数组，基础版依然要进行 \(n(n-1)/2\) 次比较，因此考虑在每一轮比较中，记录最后一次交换的位置，该位置之后的元素已经有序，下一轮比较只需要比较到该位置即可。

void bubbleSort(vector<int>& v)
{
    auto n = v.size();
    auto lastSwapIdx = 0;
    // n 可以理解为未排序元素个数
    while (n > 0)
    {
        for (int j = 0; j < n-1; j++)
        {
            if (v[j] > v[j+1])
            {
                swap(v[j], v[j+1]);
                lastSwapIdx = j;
            }
        }
        // lastSwapIdx+1 及之后的元素有序
        n = lastSwapIdx;
    }
}

时间复杂度在最好的情况下可以优化到 \(O(n)\)，但最坏情况下依然是 \(O(n^2)\)
空间复杂度：\(O(1)\)
稳定性：稳定

选择排序

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
从剩余未排序元素中继续寻找最小（大）元素，然后通过交换放到已排序序列的末尾
重复第二步，直到所有元素均排序完毕

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            // 交换时可能破坏稳定性
            swap(arr[i], arr[minIndex]);
        }
    }
}

时间复杂度：铁打的\(O(n^2)\)
空间复杂度：\(O(1)\)
稳定性：不稳定

插入排序

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

void insertionSort(vector<int>& v)
{
    for (int i = 0; i < v.size(); i++)
    {
        // 待排元素
        int key = v[i];
        // 前 i-1 个元素已经排好
        int j = i - 1;
        // j>=0 确保第一个元素直接放
        // v[j] > key 不取等确保稳定性
        while (j >= 0 && v[j] > key)
        {
            // 如果当前元素比待排元素大，后移
            v[j+1] = v[j];
            j--;
        }
        // 代派元素放入正确位置
        v[j+1] = key;
    }
}

时间复杂度：
- 最好：\(O(n)\)
- 最坏：\(O(n^2)\)
- 平均：\(O(n^2)\)
空间复杂度：\(O(1)\)

插入排序常用于更快速的排序算法中小规模数据排序的优化

改良版是希尔排序，~~但因为懒而没去学…~~

归并排序

分治算法，递归将数组不断均分为两个子数组，再对有序的两个子数组进行合并

void mergeSort(vector<int>& v,int l,int r)
{
    if(l >= r)
    {
        return;
    }
    // 这种中值求法可一定程度上避免溢出
    int mid = l + (r - l) / 2;
    mergeSort(v,l,mid);
    mergeSort(v,mid+1,r);

    vector<int> left(v.begin()+l,v.begin()+mid+1);
    vector<int> right(v.begin()+mid+1,v.begin()+r+1);
    int i = 0,j = 0,k = l;
    while (i < left.size() && j < right.size())
    {
        // 优先放左子数组，确保稳定性
        if(left[i] <= right[j])
        {
            v[k++] = left[i++];
        }
        else
        {
            v[k++] = right[j++];
        }
    }
    while (i < left.size())
    {
        v[k++] = left[i++];
    }
    while (j < right.size())
    {
        v[k++] = right[j++];
    }
}

时间复杂度：\(O(nlogn)\)
空间复杂度：\(O(n)\)
稳定性：稳定

堆排序

区别于内存空间的堆，这里的堆是一种数据结构

堆是一种完全二叉树，分为大顶堆和小顶堆，大顶堆的每个节点都大于其子节点，小顶堆的每个节点都小于其子节点

堆排序只需先构建堆，然后依次取堆顶即可

粗陋版

class heap
{
    vector<int> v;

    public:
    int top()
    {
        return v[0];
    }

    void push(int x)
    {
        v.push_back(x);
        int i = v.size() - 1;
        while (i > 0)
        {
            int parent = (i - 1) / 2;
            if (v[i] < v[parent])
            {
                swap(v[i], v[parent]);
                i = parent;
            }
            else
            {
                break;
            }
        }
    }

    void pop()
    {
        swap(v[0], v[v.size() - 1]);
        v.pop_back();
        int i = 0;
        int n = v.size();
        while (true)
        {
            int left = 2 * i + 1;
            int right = left + 1;
            int smallest = i;
            if (left < n && v[left] < v[smallest])
            {
                smallest = left;
            }
            if (right < n && v[right] < v[smallest])
            {
                smallest = right;
            }

            if (smallest != i)
            {
                swap(v[i], v[smallest]);
                i = smallest;
            }
            else
            {
                break;
            }
        }
    }
};

void heapSort(vector<int>& v) {
    heap h;
    for (int i : v)
    {
        h.push(i);
    }
    for (int & i : v)
    {
        i = h.top();
        h.pop();
    }
}

时间复杂度：\(O(nlogn)\)
空间复杂度：\(O(n)\)
稳定性：不稳定

手搓堆时涉及到0-based和1-based的转换，容易出错。但好在STL中有priority_queue，以pair形式存储元素，并使用懒删除可以通过很多算法题

标准版

void heapify(vector<int>& v, int i, int size)
{
    // 往子节点递归
    int largest = i;
    int left = 2 * i + 1;
    int right = left + 1;
    if (left < size && v[left] > v[largest])
    {
        largest = left;
    }
    if (right < size && v[right] > v[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
        swap(v[i], v[largest]);
        heapify(v, largest, size);
    }
}

void heapSort(vector<int>& v) {
    int n = v.size();
    // 从最下面的非叶子节点开始往上构建堆
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        heapify(v, i, n);
    }
    for (int i = n - 1; i > 0; i--)
    {
        // 模拟 pop，数组从后往前存放堆顶
        swap(v[0], v[i]);
        heapify(v, 0, i);
    }
}

时间复杂度：\(O(nlogn)\)
空间复杂度：优化至 \(O(1)\)
稳定性：不稳定

快速排序

快速排序的核心是划分，即找到一个基准值，将数组划分为两部分，左边的元素都小于等于基准值，右边的元素都大于等于基准值，然后递归对左右两部分进行划分

基础版

int partition(vector<int> &v, int l, int r)
{
    // i 比基准小的索引
    int i = l;
    for (int j = l; j < r; j++)
    {
        // 取最后一位为基准
        if (v[j] <= v[r])
        {
            swap(v[j], v[i++]); // 往前放
        }
    }
    // v[r] 的位置
    swap(v[i], v[r]);
    return i;
}

void quickSort(vector<int>& v,int l,int r)
{
    if (l < r)
    {
        int pi = partition(v, l, r);
        // pi 的位置坐定了
        quickSort(v, l, pi - 1);
        quickSort(v, pi + 1, r);
    }
}

时间复杂度：
- 最好/平均: \(O(nlogn)\)
- 最坏: \(O(n^2)\)
空间复杂度：快速排序的空间消耗主要来自递归调用时的栈空间
- 最好/平均: \(O(logn)\)
- 最坏: \(O(n)\)
稳定性：不稳定

改良版

方向一：减少递归开销

设定阈值，当数组长度小于阈值时，使用插入排序

void quickSort(vector<int>& v,int l,int r)
{
    if (l < r)
    {
        if (r - l + 1 <= 10)
        {
            insertionSort(v, l, r);
        }
        else
        {
            // 其他代码
        }
    }
}

方向二：基准的选择

如果基准选择不当，最坏情况会退化到 \(O(n^2)\)，因此需要选择合适的基准

随机选择

int partition(vector<int> &v, int l, int r)
{
    int random = rand() % (r-l+1);
    swap(v[l+random],v[r]);
    // 其他代码
}

期望时间复杂度为 \(O(nlogn)\)，极难退化，接近理论上的平均情况

鲁棒性极好，无法被输入数据针对

但调用随机数生成函数，计算开销略高

三数取中

int partition(vector<int> &v, int l, int r)
{
    int mid = l + (r - l) / 2;
    if (v[l] > v[mid]) swap(v[l], v[mid]);
    if (v[l] > v[r]) swap(v[l], v[r]);
    if (v[mid] > v[r]) swap(v[mid], v[r]);
    // 此时 v[l] <= v[mid] <= v[r]
    swap(v[mid], v[r]);
    // 其他代码
}

非常适用于通用场景，通常能提供比随机选择略好的平均性能

当然，还可以将随机取数与三数取中结合，这里不再赘述

方向三：区域划分

对于大规模数据输入时，比二分区域更高效的是三分区域

单基准三分

注意到每次选定的基准在排序后位置固定了，故可以尝试扩充此单个位置为一个区间，当数据中存在大量相等数据时可显著提升效率

pair<int,int> partition(vector<int> &v, int l, int r)
{
    // 基准选择代码
    int i = l; // 左指针
    int j = r - 1; // 右指针
    int current = l;
    while (current <= j)
    {
        if (v[current] < v[r])
        {
            // 之前的数据必然 <= pivot，故 current++
            swap(v[current++], v[i++]);
        }
        else if (v[current] > v[r])
        {
            // 交换来的数据未知，current 不动
            swap(v[current], v[j--]);
        }
        else
        {
            current++;
        }
    }
    swap(v[current], v[r]);
    return {i,current};
}

在quickSort中更新递归区间

auto[equalLeft, equalRight] = partition(v, l, r);
quickSort(v, l, equalLeft - 1);
quickSort(v, equalRight + 1, r);

双基准三分

选择两个基准 p1 <= p2，将区域划分为 < p1 p1 <= ... <= p2 > p2三个区域，再递归排序这三个区域

~~实现略复杂，因为懒，所以…~~

如果有兴趣可以参考 Java7 的 Arrays.sort 实现

C++ STL 排序简介

sort

高度优化的工业级实现

内省排序 (Introsort)：

开始时使用快速排序
当递归深度超过 2*log(n) 时切换到堆排序，避免最坏情况
对小数组使用插入排序
不稳定

stable_sort

主体采用归并排序
对小数组使用插入排序
若内存不足，采用原地归并排序（效率略低）

partial_sort

对指定区间 \([first, last)\) 进行处理，使前 k 个元素 \([first, middle)\) 为整个区间中最小的 k 个元素，且这 k 个元素已排序

基于堆排序的变种：
- 对前 k 个元素构建最大堆
- 遍历剩余元素 \([k, last)\)：若元素小于堆顶，则替换堆顶并重新调整堆
- 遍历结束后，前 k 个元素构成的最大堆包含了整个区间中最小的 k 个元素，最后对这 k 个元素执行堆排序转为升序
不稳定

除此外还能有更快的算法吗？

以下介绍在特定场景下突破 \(O(nlogn)\) 的排序算法 —— 非比较型排序

计数排序

对于一个值域在 \([0, k)\) 之间的整数序列，统计各个值的出现次数，然后按顺序输出

计数排序也是一种桶排序，但每个桶只存储一个值，桶排序在此不展开叙述

注意，这个 \(k\) 不能太大，否则空间复杂度会很高

简陋版

只能排纯粹自然数数组，且不稳定

void countingSort(vector<int>& v, int k)
{
    vector<int> count(k, 0);
    for (int i = 0; i < v.size(); i++)
    {
        count[v[i]]++;
    }
    int index = 0;
    for (int i = 0; i < k; i++)
    {
        while (count[i]--)
        {
            v[index++] = i;
        }
    }
}

标准版

即使出现排序对象是非自然数，也可在一定程度上建立起非自然数与自然数之间的映射关系

且通过从后往前遍历，可以确保稳定性

void countingSort(vector<obj>& v, int k)
{
    int n = v.size();
    vector<int> count(k, 0);
    for (int i = 0; i < n; i++)
    {
        count[objToNum(v[i])]++;
    }
    // 计算前缀和
    for (int i = 1; i < k; i++)
    {
        count[i] += count[i-1];
    }
    vector<obj> tmp(v.size());
    for (int i = n - 1; i >= 0; i--)
    {
        // 0-based 索引需先自减
        tmp[--count[objToNum(v[i])]] = v[i];
    }
    v = tmp;
}

时间复杂度：\(O(n+k)\)
空间复杂度：\(O(n+k)\)
稳定性：稳定

基数排序

是计数排序的延伸，将待排对象按位拆分，再从低位到高位依次进行计数排序

void radixSort(vector<obj>& v, int k)
{
    int n = v.size();
    // 临时数组声明在循环体外可减小开销
    vector<obj> tmp(n);
    // 从后往前排及计数排序的稳定性确保了最终排序的正确性和稳定性
    for (int pos = v[0].size() - 1; pos >= 0; pos--)
    {
        // 按位进行计数排序
        vector<int> count(k, 0);
        for (int i = 0; i < n; i++)
        {
            count[objToNum(v[i][pos])]++;
        }
        for (int i = 1; i < k; i++)
        {
            count[i] += count[i-1];
        }
        for (int i = n - 1; i >= 0; i--)
        {
            tmp[--count[objToNum(v[i][pos])]] = v[i];
        }
        v = tmp;
    }
}

时间复杂度：\(O(nk)\)
空间复杂度：\(O(n+k)\)
稳定性：稳定

给定一个数组，查找其中第 k 大的元素。

当然可以排序后直接返回下标，时间复杂度是 O(nlogn)，有无更优的算法？

基于快速排序的选择算法

注意到快速排序的划分操作，每次划分后，都能确定基准的最终位置。

如果基准的位置正好是 k，那么基准就是第 k 大的元素；如果基准的位置大于 k，那么第 k 大的元素在基准的左边；如果基准的位置小于 k，那么第 k 大的元素在基准的右边。

因此，我们可以使用快速排序的划分操作来选择第 k 大的元素。

随机化选择基准

int partition(vector<int> &v, int l, int r)
{
    int random = rand() % (r - l + 1) + l;
    swap(v[r], v[random]);
    int i = l;
    for (int j = l; j < r; j++)
    {
        if (v[j] <= v[r])
        {
            swap(v[j], v[i++]);
        }
    }
    swap(v[i], v[r]);
    return i;
}

int randSelect(vector<int> &v, int l, int r,int q)
{
    if (l == r)
    {
        return v[l];
    }

    int i = partition(v, l, r);
    if (i == q)
    {
        return v[q];
    }
    else if (i > q)
    {
        return randSelect(v, l, i - 1, q);
    }
    else
    {
        return randSelect(v, i + 1, r, q);
    }
}

中位数

// todo?

基于堆的选择算法