排序 - Data Structure | Jiankychen's Blog

排序算法性能汇总：

排序算法	平均时间复杂度	最差时间复杂度	空间复杂度	稳定性
选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	数组不稳定、链表稳定
冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
快速排序	$O(n \log{n})$	$O(n^2)$	$O(\log{n})$	不稳定
堆排序	$O(n \log{n})$	$O(n \log{n})$	$O(1)$	不稳定
归并排序	$O(n \log{n})$	$O(n \log{n})$	$O(n)$	稳定
希尔排序	$O(n \log{n})$	$O(n^2)$	$O(1)$	不稳定
计数排序	$O(n + m)$	$O(n + m)$	$O(n + m)$	稳定
桶排序	$O(n)$	$O(n)$	$O(n)$	取决桶内排序算法
基数排序	$O(kn)$	$O(n^2)$	$O(n)$	稳定

稳定的排序算法：在排序前的序列中，有超过一个相同的元素，排序后这两个元素的相对位置依然保持不变

参考：https://dowalle.gitbook.io/algo/algorithm/2-suan-fa-ji-chu/1-pai-xu

为便于表述以及理解，作出以下声明:

各排序算法均以 " 将包含 n 个元素的数组按从小到大顺序排列 " 为例
第 i 个元素 的 i 的范围是 [1, n]
第 i 位元素 的 i 的范围是 [0, n - 1]

另，排序算法可以针对 字符串 进行排序，字典序 就是字符串的大小顺序

# 选择排序

选择：选出序列中的最小值，放到序列的首位

// 选择：寻找最小值
int min_pos = 0;
for (int j = 1; j < n; j++) {
    if (a[j] < a[min_pos]) {   // 如果当前元素小于之前维护的最小值
        min_pos = j;           // 更改最小值出现的位置
    }
}

选择排序 的算法思想：

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
以此类推，直到所有元素均排序完毕

代码实现：

void SelectionSort(vector<int>& a) {   // 选择排序
    int n = a.size();
    for (int i = 0; i < n - 1; i++) {      // 枚举应该归位的第 i 位元素
        int min_pos = i;                   // 将最小值位置设置为当前范围 i ~ n - 1 的首位
        for (int j = i + 1; j < n; j++) {  // 将第 i 位元素和剩下的元素相比较
            if (a[j] < a[min_pos]) {       // 如果当前元素小于之前维护的最小值
                min_pos = j;               // 更改最小值出现的位置
            }
        }
        swap(a[i], a[min_pos]);            // 将最小值与第 i 位元素交换
    }
}

时间复杂度：

最优、平均和最坏时间复杂度均为 $O(n^2)$

空间复杂度： $O(1)$

稳定性：由于 swap 操作的存在，选择排序是一种 不稳定 的排序算法

# 冒泡排序

在算法的执行过程中，较小的元素像是气泡般慢慢浮到数列的顶端，故叫做冒泡排序

冒泡：两个数比较大小，较大的数下沉，较小的数冒起来

// 冒泡：连续交换过程
for (int i = 0; i < n - 1; i++)    // 枚举两两交换的前一个元素序号
    if (a[i] > a[i + 1])
        swap(a[i], a[i + 1]);      // 如果前一个元素大于后一个，就进行交换

冒泡排序 的算法思想：

针对 $i \in [0, n - 2]$ ，通过冒泡将前 n - i 个元素的最大值移动到第 n - i - 1 位，此时还剩前 n - i - 1 个元素（即，第 0 位到第 n - i - 2 位）未排序

注：也可以进行第 i = n - 1 阶段结束

代码实现：

void BubbleSort(vector<int>& a) { // 冒泡排序，引用传递
    int n = a.size();
    for (int i = 0; i < n - 1; i++) { // 在第 i 个阶段，未排序的序列长度从 n - i 变成 n - i - 1 （注：i 的最大值可以设置成 n - 1，也可以设置成 n - 2）
        // 将第 0 位到第 n - i - 1 位元素的最大值，移到 n - i - 1 的位置
        for (int j = 0; j < n - i - 1; j++) // j 是冒泡操作中的前一个元素的下标，j 的最大值为 n - i - 2，对应 j + 1 最大值为 n - i - 1
            if (a[j] > a[j + 1])
                swap(a[j], a[j + 1]);
    }
}

时间复杂度：

最优情况 $O(n)$ ，序列完全有序时，冒泡排序只需遍历一遍数组
最坏情况 $O(n^2)$ ，冒泡排序要执行 $(n - 1) n / 2$ 次交换操作
平均时间复杂度 $O(n^2)$

空间复杂度： $O(1)$

稳定性：冒泡排序是一种稳定的排序算法

# 插入排序

对于一个有序序列，如果想在其中新加入一个元素，就应通过 插入操作 找出正确的插入位置，并且将插入位置空出来，然后插入新元素

插入：将第 i 个元素插入到前 i - 1 个元素的有序序列中，形成长度为 i 的有序序列

假设数组 a 的第 0 位到第 i - 1 位已经有序，插入操作的关键在于搜索插入位置，即：找出一条分界线 j ，使得 a[j - 1] <= a[i] 且 a[j] > a[i] 成立

// 插入：找出插入位置，并将该位置及以后的元素向右移动一位
int j = i - 1, x = a[i];    // 初始化分界线的位置，并将 a[i] 用临时变量保存防止被修改
for (; (j >= 0) && (a[j] > x); j--) { // 满足循环条件，分界线的位置应向左移
    a[j + 1] = a[j];
}
// 循环结束，找出分界线位置，插入 x
a[j + 1] = x;

LeetCode 35. 搜索插入位置

插入排序 的算法流程为：

待排序序列的第 0 位元素作为初始的有序序列
针对 $i \in [1, n - 1]$ ，依次将第 i 位元素插入到有序序列中

代码实现：

void InsertSort(vector<int>& a) { // 插入排序
    int n = a.size();
    for (int i = 1; i < n; i++) { // 从左到右遍历，将元素依次插入有序序列中
        int j, x = a[i];
        for (j = i - 1; (j >= 0) && (a[j] > x); j--) {   
            // 满足循环条件，相当于分界线应向左移
            a[j + 1] = a[j];                                 
        }
        // 找到分界线位置，插入元素 x
        a[j + 1] = x;
    }
}

时间复杂度：

最优时间复杂度为 $O(n)$
平均和最坏时间复杂度均为 $O(n^2)$

空间复杂度： $O(1)$

稳定性：插入排序是一种稳定的排序算法

# 快速排序（重要）

快速排序（Quicksort），又称分区交换排序（partition-exchange sort），简称快排

快速排序 基本思想：

选择基准：从数列中取出一个数作为基准数 pivot
partition 过程：将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
再对左右区间重复第 2 步，直到各区间只有一个数

选择基准的方式：
固定位置：取序列的第一个或最后一个元素作为基准（基本的快速排序算法，不利于处理有序或部分有序的数组）
随机选取基准：取待排序列中任意一个元素作为基准（对于绝大多数输入数据，可以达到 $O(n \log{n})$ 的期望时间复杂度）
三数取中（median-of-three）：取第一个、最后一个和中心位置上的三个元素的中位数作为基准（可以避免极端数据（如升序序列或降序序列）带来的退化）

代码实现：

void QuickSort(vector<int>& a, int l, int r) { // 将序列分成左右两个子序列，并对子序列分别排序
                                        // l 和 r 分别代表当前排序子段在原序列中左右端点的位置

    int pivot = a[r];   // 设置最右边的数为基准
    int pos = l - 1;    // 分界线 pos 及其左边的元素一定小于 pivot
    
    // partition: 划分子序列，并确定分界线新位置 pos
    // partition 包含 swap 操作，故而不是稳定的排序算法
    for (int j = l; j < r; j++)
        if (a[j] < pivot) 
            swap(a[j], a[++pos]);
    swap(a[r], a[++pos]); // 将 pivot 放到分界线位置
    
    // 对左子段和右子段分别进行排序
    if (l < pos - 1)
        QuickSort(a, l, pos - 1); // 如果左边子段长度大于 1，排序
    if (pos + 1 < r)
        QuickSort(a, pos + 1, r); // 如果右边子段长度大于 1，排序
}

时间复杂度：

最优 $O(n \log{n})$ ，每一次选择的分界值都是序列的中位数
最坏 $O(n^2)$ ，每一次选择的分界值都是序列的最值
平均 $O(n \log{n})$

空间复杂度： $O(\log{n})$ ，递归调用时使用栈帧空间

稳定性：快速排序是一种 不稳定 的排序算法

三种快速排序以及快速排序的优化

# sort 函数

C++ 标准模板库（STL）定义了 排序函数 sort ，可以用于排序操作（对 快速排序 的优化实现）

sort 函数的头文件

#include<algorithm>

sort 函数 有三个参数：头指针 、尾后指针 和 比较函数

如果已经针对排序对象定义了小于号（即，定义了小于号何时成立），比较函数可省略

例如，针对数组排序：

int a[10] = {2, 3, 1, 5, 4};
int n = 5;
sort(a.begin(), a.end());  //sort函数的两个参数，头指针和尾后指针
for (int i = 0; i < n; ++i) 
    cout << a[i] << " ";
cout << endl;

如果想按照其他标准进行排序，可以定义一个比较函数。例如，按 从大到小排序 ：

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

// 比较函数，函数的参数是当前比较的两个数组中的元素
bool cmp(int x, int y) { // x 和 y 分别为排序数组中的两个元素
    return (x > y);  // 当函数返回值为 true 时，x 应该排在 y 的前面
}

int main() {
    sort(a.begin(), a.end(), cmp); // 比较函数作为第三个参数传入 sort 函数
    for (int i = 0; i < n; ++i)
        cout << a[i] << " ";
    cout << endl;
    return 0;
}

参考：sort 排序算法介绍及示例

# 堆排序

# 归并排序（重要）

归并排序（merge sort）是一种采用了 分治思想 的排序算法

归并：合并两个有序的序列

// 归并操作：按升序合并数组 a 中两个有序的子序列，子序列的区间分别为 [1, (l + r) / 2] 和 [(l + r) / 2 + 1, r]

vector<int> temp(a.size(),0);      // 辅助数组 temp

void Merge (vector<int> &a, vector<int> &temp, int l, int r) {
    int mid = l + ((r - l) >> 1);
    int i = l, j = mid + 1;         // 指针 i 和 j 分别指向两个子序列的首个元素
    for (int k = l; k <= r; k++) {  // 遍历原序列
        // 如果 j 已经移至子段的尾后，或者， i 指向的元素比 j 指向的元素小
        // 将 i 指向的元素填充到原序列的 k 位置，并将 i 右移
        if ((j > r) || (i <= mid && a[i] < a[j]))
            temp[k] = a[i++];
        // 否则，将 j 指向的元素填充到原序列的 k 位置，并将 j 右移
        else
            temp[k] = a[j++];
    }

    // 拷贝结果至 a
    for (int k = l; k <= r; k++)
        a[k] = temp[k];
}

// 注：在函数外一次性创建 辅助数组 temp ，这样可以避免在每次递归调用时创建数组，以减少内存分配的耗时

归并排序 分为三个步骤：

将序列划分为两部分
递归地对两个子序列分别进行归并排序
合并两个子序列

代码实现：

vector<int> temp(500,0);      // 辅助数组 temp ，根据实际需要另行确定 temp 的维度

// 归并排序
void MergeSort(vector<int> &a, vector<int> &temp, int l, int r) { // 用来把 a 数组 [l, r] 这一区间的元素排序
    // 子段为空或者长度为 1 ，递归结束
    if (l >= r) return;
    
    // 将序列均分成两部分（左右长度相差最多为1）
    int mid = l + ((r - l) >> 1);
    MergeSort(a, temp, l, mid);     // 对 [l, mid] 子段进行归并排序
    MergeSort(a, temp, mid + 1, r); // 对 [mid + 1, r] 子段进行归并排序
    
    // 归并操作（结果存储在辅助数组 temp 中）
    int i = l, j = mid + 1;         // 指针 i 和 j 分别指向两个子序列的首个元素
    for (int k = l; k <= r; k++) {  // 遍历原序列
        // 如果 j 已经移至子段的尾后，或者， i 指向的元素比 j 指向的元素小
        // 将 i 指向的元素填充到原序列的 k 位置，并将 i 右移
        if ((j > r) || (i <= mid && a[i] < a[j]))
            temp[k] = a[i++];
        // 否则，将 j 指向的元素填充到原序列的 k 位置，并将 j 右移
        else
            temp[k] = a[j++];
    }

    // 拷贝结果至 a
    for (int k = l; k <= r; k++)
        a[k] = temp[k];
}

时间复杂度：

最优、平均和最坏时间复杂度均为 $O(n \log{n})$ ，因为算法始终有 $\log{n}$ 层，而合并子序列的复杂度为 $O(n)$

空间复杂度： $O(n)$ ，借助了辅助数组（所以是一种非原地排序算法）

稳定性：归并排序是一种稳定的排序算法

# stable_sort 函数

C++ 标准模板库（STL）中也有对 归并排序 的优化实现，函数名为 stable_sort ，也在 algorithm 头文件中，使用方法与 sort 一样，通过传入 头指针 、 尾后指针 和 比较函数 来对数组中的对象进行排序

// 头文件
#include <algorithm>

// 比较函数
bool cmp(int x, int y) { // 函数的参数是当前比较的两个数组中的元素
    return (x > y);      // 当函数返回值为 true 时，x 应该排在 y 的前面
}

// 调用
stable_sort(a, a + n, cmp);

# 希尔排序

# 计数排序

计数排序 基于一个假设：待排序的 所有数均为整数，且落在一个很小的区间内 ，例如 0 到 100 之间

计数排序 统计待排序序列中每一个值 i 出现的次数，然后从小到大枚举所有 i ，按照出现次数输出对应数量的 i

计数排序不适合按字母顺序排序人名
计数排序不是比较排序，排序的速度快于任何比较排序算法

计数排序 的基本流程：

找出待排序数组中的最大值 MaxValue ，创建一个长为 MaxValule + 1 的数组 cnt ，数组 cnt 元素初始值均为 0
统计待排序数组中每种值 i 元素的出现次数，存入 cnt[i]
创建结果数组 ans ，长度与待排序数组一致
遍历 cnt 数组，找出值大于 0 的元素 cnt[i] ，并将该元素索引 i 填充到数组 ans 中（从左向右填充），每填充一次， cnt[i] 值减 1 ，直到该值不大于 0 ，然后依次处理 cnt 数组的后续元素

代码实现：

void CountSort(vector<int> &nums) { // 计数排序的简单实现
    // 确保容器非空
    int n = nums.size();
    if (n == 0) return;

    // 找出待排序数组的最大值 MaxValue
    int MaxValue = nums[0];
    for (int i = 1; i < n; i++)
        MaxValue = max(MaxValue, nums[i]);
    
    // 统计每一种值出现的次数
    vector<int> cnt(MaxValue + 1, 0);
    for (int i = 0; i < n; ++i)
        ++cnt[nums[i]];
    
    // 维护最终有序序列
    vector<int> ans(n,0);
    for (int i = 0, j = 0; i <= MaxValue; i++) // 枚举每一种值 i ，指针 j 指向填充的位置
        for (int k = 1; k <= cnt[i]; k++)      // 这里采用 k 自增来记录填充个数，是为了保证排序算法的稳定性
            ans[j++] = i;                      // 根据出现次数填充相应数量的 i

    // // 不同于上述填充方法，以下填充过程无法保证稳定性
    // vector<int> ans(n,0);
    // for (int i = 0, j = 0; i <= MaxValue; i++) {
    //     while (cnt[i] > 0) {
    //         ans[j++] = i;
    //         cnt[i]--;
    //     }
    // }

    // 拷贝结果
    for (int i = 0; i < n; i++)
        nums[i] = ans[i];
}

然而，这里统计的数字范围为 [0, MaxValue] ，可能存在空间浪费的问题

事实上，可以找出数组元素的最小值 MinValue ，仅统计 [MinValue, MaxValue] 区间内的数字。即，用 cnt[0] 记录值 MinValue 的出现次数，用 cnt[MaxValue - MinValue] 记录值 MaxValue 的出现次数

void CountSort(vector<int> &nums) { // 计数排序的优化版
    // 确保容器非空
    int n = nums.size();
    if (n == 0) return;

    // 找出待排序数组的最大值 MaxValue 和最小值 MinValue
    int MaxValue = nums[0];
    int MinValue = nums[0];
    for (int i = 1; i < n; i++) {
        MaxValue = max(MaxValue, nums[i]);
        MinValue = min(MinValue, nums[i]);
    }
    
    // 统计每一种值出现的次数
    int length = MaxValue - MinValue + 1;
    vector<int> cnt(length, 0);                // 初始化为 0
    for (int i = 0; i < n; i++)
        ++cnt[nums[i- MinValue]];
    
    // 维护最终有序序列
    vector<int> ans(n,0);
    for (int i = 0, j = 0; i < length; i++)    // 指针 j 指向填充的位置
        for (int k = 1; k <= cnt[i]; k++)      // 根据出现次数填充相应数量的 i
            ans[j++] = i + MinValue;
    // 拷贝结果
    for (int i = 0; i < n; i++)
        nums[i] = ans[i];
}

时间复杂度： $O(n + m)$ ，其中， n 为待排序数组 nums 的长度， m 为数组 nums 中的元素值的种类数（即，数组 cnt 的长度）

所有基于比较的排序算法，其最优时间复杂度为 $\Omega (n \log{n})$
计数排序不是基于比较的排序，可以达到比 $\Omega (n \log{n})$ 更好的时间复杂度

空间复杂度： $O(n + m)$

稳定性：计数排序是稳定的排序算法

计数排序 的基本思想还可以拓展成 桶排序 和 基数排序 。使用 桶排序 和 基数排序 ，可以对更大范围内的、甚至不是整数的序列进行排序

参考：一文弄懂计数排序算法！

# 桶排序（重要）

# 基数排序

参考资料：

CodeSheep
OI Wiki
algo
青舟智学

排序

# 选择排序

# 冒泡排序

# 插入排序

# 快速排序（重要）

# sort 函数

# 堆排序

# 归并排序（重要）

# stable_sort 函数

# 希尔排序

# 计数排序

# 桶排序（重要）

# 基数排序

数据结构简介

递推与递归