排序

排序算法性能汇总：

排序算法	平均时间复杂度	最差时间复杂度	空间复杂度	稳定性
选择排序	$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)$

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

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

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

# 桶排序（重要）

# 基数排序

参考资料：

排序

# 选择排序

# 冒泡排序

# 插入排序

# 快速排序（重要）

# sort 函数

# 堆排序

# 归并排序（重要）

# stable_sort 函数

# 希尔排序

# 计数排序

# 桶排序（重要）

# 基数排序

数据结构简介

递推与递归