§9 排序

§9.1 排序的基本概念

在排序过程中，若整个表都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为 内排序。根据内排序算法是否 基于关键字的比较，将内排序算法分为 基于比较的排序算法 和不基于比较的排序算法。

基数排序是典型的不基于比较的排序算法。
基于比较的排序算法中，主要进行比较、移动这两种基本操作，这类排序算法的性能由算法的 时间和空间 确定的，而时间是由比较和移动的次数之和确定的，例如，两个记录的一次交换一般需要三次移动。

若排序过程中要进行 数据的内、外存交换，则称之为 外排序。

如果待排序的表中，存在有多个关键字相同的记录，经过排序后这些具有 相同关键字 的记录之间的 相对次序保持不变，称这种排序方法是稳定的。希尔、快排、选择排序是不稳定的（重要）。

§9.2 插入排序

§9.2.1 直接插入

每一趟将一个待排序的元素，按大小 插入到已经排序中 的适当位置上。

时间 $\Omega(n)-\Theta(n^{2})-\mathrm{O}(n^{2})$ ，空间 $\Omega(1)-\Theta(1)-\mathrm{O}(1)$ ，稳定。

§9.2.2 折半插入

优化了个寂寞，其瓶颈主要是顺序表的移动。

时间 $\Omega(n)-\Theta(n^{2})-\mathrm{O}(n^{2})$ ，空间 $\Omega(1)-\Theta(1)-\mathrm{O}(1)$ ，稳定。

§9.2.3 希尔排序（不太重要）

基于插入排序，将待排序数组 分割成多个子序列，这些子序列的元素间隔一定步长，然后 对每个子序列进行插入排序，随着 步长的逐渐减小，最终整个数组变为有序。

时间 $\Omega(n\log n)-\Theta(n^{1.3})-\mathrm{O}(n^{2})$ ，空间 $\Omega(1)-\Theta(1)-\mathrm{O}(1)$ ，不稳定。

§9.3 交换排序

§9.3.1 冒泡排序

倒序遍历，如果相邻两项不是有序的，就交换之，重复多轮。

时间 $\Omega(n)-\Theta(n^{2})-\mathrm{O}(n^{2})$ ，空间 $\Omega(1)-\Theta(1)-\mathrm{O}(1)$ ，稳定。

§9.3.2 快速排序

选择一个基准元素，通过一趟排序将待排序的数组分割成独立的两部分，其中一部分的所有元素都不大于另一部分的所有元素，然后递归地对这两部分继续进行快速排序，直至整个数组有序。快速排序在被排序的数组随机分布下最容易发挥其长处。

时间 $\Omega(n\log n)-\Theta(n\log n)-\mathrm{O}(n^{2})$ ，空间 $\Omega(\log n)-\Theta(\log n)-\mathrm{O}(\log n)$ ，不稳定。

提醒：未经任何优化的快排，最坏时间是 $\mathrm{O}(n^{2})$ 。std 中的快排是优化过的，保证上界严格不超过 $\mathrm{O}(n\log n)$ 。

§9.4 选择排序

§9.4.1 简单选择排序

每步从待排序的记录中选出关键字最小的记录，按顺序放在已排序的记录序列的最后，直到全部排完为止。

时间 $\Omega(n^{2})-\Theta(n^{2})-\mathrm{O}(n^{2})$ ，空间 $\Omega(1)-\Theta(1)-\mathrm{O}(1)$ ，不稳定。

§9.4.2 堆排序（不太重要）

大概思路掌握就行，具体细节不重要，~~其实作者也没看懂~~

基于比较，利用堆这种数据结构的特性，首先将待排序数组构建成一个 大根堆，使得每个父节点的值都大于或等于其子节点的值；然后通过反复 移除堆顶元素（最大值），将其与数组末尾元素交换，并重新调整堆以保持大根堆的性质，直到堆中只剩下一个元素，此时整个数组已经按照升序排列完成。

时间 $\Omega(n\log n)-\Theta(n\log n)-\mathrm{O}(n\log n)$ ，空间 $\Omega(1)-\Theta(1)-\mathrm{O}(1)$ ，不稳定。

§9.5 归并排序

多次将两个或两个以上的有序表合并成一个新的有序表，最简单的归并是直接将两个有序的子表合并成一个有序的表——二路归并排序。

时间 $\Omega(n\log n)-\Theta(n\log n)-\mathrm{O}(n\log n)$ ，空间 $\Omega(n)-\Theta(n)-\mathrm{O}(n)$ ，稳定。

个人认为是最优雅的排序算法。放个代码：

ll merge_sort(vector<int>& a) {
	auto solve = [&](this auto&& self, int L, int R) -> ll {
		if (R - L <= 1) return 0ll;
		int m = L + R >> 1;
		ll res = self(L, m) + self(m, R);
		vector<int> b;
		int l = L, r = m;
		while (l < m && r < R) {
			if (a[l] <= a[r]) b.push_back(a[l++]);
			else b.push_back(a[r++]), res += m - l;
		}
		while (l < m) b.push_back(a[l++]);
		while (r < R) b.push_back(a[r++]);
		copy(b.begin(), b.end(), a.begin() + L);
		return res;
	};
	return solve(0, a.size());
}