Basic Programming：基础排序算法

基础算法说明，不涉及算法的书写实现，只整理算法的操作思想，以及复杂度比较。

排序

排序的稳定性只对 结构类型数据 的排序有意义。

1. 插入排序

基本思想：每步将一个待排序的对象，按其有关键码大小，插入到前面已经排好序的一组对象的适当位置上，知道对象全部插入为止。

基本操作：有序插入。在有序序列中插入一个元素，保持序列有序，有序长度不断增加。

1.1 直接插入排序：采用顺序查找法查找插入位置。

直接插入排序，可以使用 “哨兵”。

原始数据越接近有序，排序速度越快。最坏情况下（数据逆序排序）。

实现排序的基本操作有两个，“比较” 序列中两个关键字的大小， “移动”。如果要提高查找速度，减少元素的比较次数和移动次数。

1.2 折半插入排序：二分法

减少了比较次数，不能减少移动次数。平均性能优于直接插入。

1.3 希尔排序：缩小增量，多遍插入排序

特点：
- 一次移动，移动位置较大，跳跃式的接近排序后的最终位置。
- 最后一次只需要少量移动。
- 增量序列必须是递减的，最后一个必须是1.
- 增量序列必须是互质的。

如何选择最佳 d 序列，目前尚未解决；最后一个增量必须是1，无除了1之外的公因子；不宜在链式存储结构上实现。

2. 交换排序

基于交换思想的排序。

2.1 冒泡排序

冒泡排序比较简单，但是效率较低。
n 个记录，总共需要 n-1 趟。第 m 趟需要比较 n-m 次。

2.2 快速排序

基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中的部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。

具体实现：选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。中间数（枢轴） 可以是第一个数、最后一个数、最中间一个数、任选一个数等。

快速排序不是原地排序。由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度（即使不用递归，也需要使用用户栈）。
在平均情况下：需要 O(logn) 的栈空间。
最坏情况下：栈空间可达 O(n)。

快速排序是一种不稳定的排序。快排不适用于对基本有序或原本有序的记录序列进行排序（越乱越快）。

3. 选择排序

3.1 简单选择排序

基本思想：在待排序的数据中选出最大（小）的元素放在其最终的位置。

基本实现

首先通过 n-1 次关键字比较，从 n 个记录中找出关键字 最小 的记录，将它与第一个记录交换。
再通过 n-2 次比较，从剩余的 n-1 个记录中找出关键字 次小 的记录，将它与第二个记录交换。
重复以上操作，共进行 n-1 趟排序后，排序结束。

时间复杂度

移动次数
- 最好情况：已经排好序，移动次数为 0
- 最坏情况：逆序，每次都需要交换，移动次数为 3(n-1)
比较次数：无论待排序序列是什么状态，选择排序所需进行的 “比较” 次数都相同。

算法稳定性：简单选择排序是不稳定排序。

3.2 堆排序

堆的定义：若 n 个元素的序列 { ${a_1, a_2, ..., a_n}$ } 满足 $a_i <= a_{2i}$ ， $a_i <= a_{2i+1}$ 或者 $a_i >= a_{2i}$ ， $a_i >= a_{2i+1}$ 。则分别称该序列 { ${a_1, a_2, ..., a_n}$ } 为 小根堆 和 大根堆。

从堆的定义可以看出，堆实质是满足如下性质的 完全二叉树 ：二叉树任一非叶子结点均小于（大于）它的孩子结点。

堆排序：若在输出堆顶的最小值（最大值）后，使得剩余 n-1 个元素的序列重又建成一个堆，则得到 n 个元素的次小值（次大值）……如此反复，便得到一个有序序列，这个过程称之为 堆排序。

实现堆排序需解决两个问题：

如何由一个无序序列建成一个堆？
单节点的二叉树是堆。
如何在输出堆顶元素后，调整剩余元素为一个新的堆？

对一个无序序列反复 “筛选” 就可以得到一个堆，即：从一个无序序列建堆的过程就是一个反复 “筛选” 的过程。

初始化所需时间不超过O(n)
排序阶段（不含初始化）
- 一次重新堆化所需时间不超过O(logn)
- n-1 次循环所需时间不超过O(nlogn)

堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复 “筛选” 上。堆排序在最坏情况下，其时间复杂度也为 $O(nlog_2n)$ ，这是堆排序的最大优点。无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于 “最好” 或 “最坏” 的状态。

4. 归并排序

基本思想：将两个或两个以上的有序子序列 “归并” 为一个有序序列。

4.1 2-路归并排序

在内部排序中，通常采用的是 2-路归并排序。即：将两个位置相邻的有序子序列 R[l…m] 和 R[m+1…n] 归并为一个有序序列 R[l…n]。

时间效率：O(nlog2n)
空间效率：O(n) 因为需要一个与原始序列同样大小的辅助空间。

归并排序是一个稳定的算法。

5. 基数排序

基本思想：分配+收集

也叫桶排序或箱排序，设置若干个箱子，将关键字为 k 的记录放入第 k 个箱子，然后再按序号将非空的连接。

基数排序：数字是有范围的，均有 0-9 这十个数字组成，则只需设置十个箱子，相继按个、十、百…进行排序。

例如 {614, 738, 921, 485, 637, 101, 215, 530, 790, 306}

6. 外部排序

7. 各种排序方法比较

排序方法	最好时间复杂度	最坏时间复杂度	平均时间复杂度	空间复杂度	稳定性
直接插入排序	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^{1.3}$ )	O(1)	不稳定
冒泡排序	O( $n$ )	O( $n^2$ )	O( $n^2$ )	O(1)	不稳定
快速排序	O( $nlogn$ )	O( $n^2$ )	O( $nlogn$ )	O( $nlogn$ )	不稳定
直接选择排序	O( $n^2$ )	O( $n^2$ )	O( $n^2$ )	O(1)	不稳定
堆排序	O( $nlogn$ )	O( $logn$ )	O( $nlogn$ )	O( $n^2$ )	不稳定
归并排序	O( $nlogn$ )	O( $nlogn$ )	O( $nlogn$ )	O(n)	稳定
基数排序	O( $n+m$ )	O( $k*(n+m)$ )	O( $k*(n+m)$ )	O(n+m)	稳定

7.1 时间性能

按平均的时间性能来分，有三类排序方法
- 时间复杂度为 O(nlogn) 的方法有：
  快速排序、堆排序和归并排序，其中以快速排序为最好。
- 时间复杂度为 O(n^2) 的有：
  直接插入排序、冒泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤其如此。
- 时间复杂度为 O(n) 的排序方法只有：基数排序
当待排记录序列按关键字顺序有序时，直接插入排序和冒泡排序能达到O(n)的时间复杂度；而对于快速排序而言，这是最不好的情况，此时的时间性能退化为 $O(n^2)$ ，因此是应该尽量避免的情况。
简单选择排序、堆排序、归并排序的时间性能不随记录序列中关键字的分布而改变。

7.2 空间性能

指的是排序过程中所需的辅助空间大小

所有的简单排序方法（包括：直接插入、冒泡和简单选择）和堆排序的空间复杂度为 $O(1)$ 。
快速排序为 $O(logn)$ ，为栈所需的辅助空间。
归并排序所需辅助空间最多，其空间复杂度为 $O(n)$ 。
链式基数排序需附设队列首尾指针，则空间复杂度为 $O(rd)$ 。

7.3 稳定性

稳定的排序方法是指：对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。

当对多关键字的记录序列进行 LSD 方法排序时，必须采用稳定的排序算法。
对于不稳定的排序方法，只要能举出一个实例说明即可。
快速排序和堆排序是不稳定的排序方法。

关于排序方法的时间复杂度的下限

以上的几种排序方法，除基数排序外，其它方法都是基于 “比较关键字” 进行排序的排序方法，可以证明，这类排序法可能达到的最快的时间复杂度为 $O(nlogn)$ 。基数排序不是基于 “比较关键字” 的排序方法，所以它不受这个限制。

可以用一棵判定树来描述这类基于 “比较关键字” 进行排序的排序方法。