排序（Sort）_排序sort

1、 排序的基本知识

• 定义：排序就是将原本无序的序列重新排列成有序的序列。
• 排序的稳定性
  • 如果待排序表中有两个元素Ri、Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，如果使用某一排序算法排序后，Ri仍然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

2、 插入类排序

2.1 直接插入排序

基本思想：对于未排序数据，在已排序序列中从后向前扫描，找到相应位置，将位置后的已排序数据逐步向后挪位，将新元素插入到该位置。

2.2 折半插入排序

基本思想：折半插入排序将比较和移动这两个操作分离出来，也就是先利用折半查找找到插入的位置，然后一次性移动元素，再插入该元素。

2.3 希尔排序

基本思想：希尔排序本质上还是插入排序，只不过是把待排序序列分成几个子序列，再分别对这几个子序列进行直接插入排序。

1. 先以增量5来分割序列，也就是下标为0,5,10,15…的关键字分成一组，下标为1,6,11,16…分成一组,然后对这些组分别进行直接插入排序，这就完成了一轮希尔排序。
2. 缩小增量(d1=n/2，di+1= [di/2]，比如10个数据序列，第一次增量d1=10/2=5,第二次增量d2= [d1/2]= [5/2]=2,并且最后一个增量等于1),所以第二轮以增量为2进行类似的排序过程。
3. 接下来的第三轮，第四轮…都是类似的过程，直到最后一轮以增量为1。此时就是前面所说的直接插入排序。
   

• 空间复杂度：希尔排序的空间复杂度为O(1)
• 稳定性：不稳定，由于不同的增量可能就会把相等的关键字划分到两个直接插入排序中进行排序， 可能就会造成相对顺序变化。

3、 交换类排序

3.1 冒泡排序

基本思想：假设待排序表长为n，从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换它们，直到序列比较完。我们称它为一趟冒泡，结果将最小的元素交换到待排序列的第一个位置。下一趟冒泡时，前一趟确定的最小元素不再参与比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置，……，这样最多做n-1趟冒泡就能把所有元素排好序。

• 空间复杂度：交换时开辟了存储空间来存储中间变量，所以空间复杂度为O(1)
• 稳定性：当两个关键字相等，if判断条件不成立，所以不会发生数据移动。所以是稳定的。

3.2 快速排序

快速排序是一种基于分治法(Divide-and-Conquer)的排序方法。
基本思想：选择任一个元素作为枢轴(pivot)(通常选第一个元素)，将序列中比枢轴小的元素都移到枢轴前边，比枢轴大的元素都移到枢轴后边。

那么在“分块”时是如何操作呢？以从小到大排序为例

1. 取出首位作为pivot，空出位置
2. 先从右端开始遍历，当右哨兵遇到比基准小的值停下，放到空位处
   然后从左端开始遍历，当左哨兵遇到比基准大的值停下，放到空位处
3. 重复上面操作，直到左右哨兵碰面，pivot移到空位。一次排序过程结束，可见下图。
   
   快速排序的整个过程示例如下
   

• 快速排序是所有内部排序算法中平均性能最优的排序算法，适用于数据分布散乱的序列
• 稳定性：存在交换关键字，不稳定

4、 选择类排序

4.1 简单选择排序

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

注：选择排序，元素比较次数与序列初始状态无关，始终是$\frac{n(n-1)}{2}$

• 空间复杂度：需要额外的存储空间仅为交换元素时借助的中间变量，所以空间复杂度是O(1)
• 稳定性：不稳定 原因就在于交换部分会打破相对顺序

4.2 堆排序

• 什么是堆？

  • 堆是一棵完全二叉树，而且满足任何一个非叶结点的值都不大于(或不小于)其左右孩子结点的值。
    • 如果是每个结点的值都不小于它的左右孩子结点的值，则称为大顶堆。
    • 如果是每个结点的值都不大于它的左右孩子结点的值，则称为小顶堆。

• 什么是堆排序？

  • 我们知道对于一个堆来说，它的根结点是整个堆中所有结点的值的最大值(大顶堆)或者最小值(小顶堆)。所以堆排序的思想就是每次将无序序列调节成一个堆，然后从堆中选择堆顶元素的值，这个值加入有序序列，无序序列减少一个，再反复调节无序序列，直到所有关键字都加入到有序序列。

事例过程如下图：

• 堆排序的时间复杂度为O(n)+O(nlog2n)=O(nlog2n)
• 建堆时间O(n)，每次调整时间O(h)（插入新元素时，需调用向上调整的算法，比较次数最多等于树的高度减一）
• 堆排序不稳定

5、 归并排序

基本思想：也是采用分治策略。假定待排序表含有n个记录，则可以看成是n个有序的子表，每个子表长度为1，然后两两归并，得到 ⌈n/2⌉个长度为2或1的有序表；再两两归并，……如此重复，直到合并成一个长度为n的有序表为止，这种排序方法称为2-路归并排序。

例如：49 38 65 97 76 13 27

1. 首先将整个序列的每个关键字看成一个单独的有序的子序列
2. 两两归并，49和38归并成{38 49} ，65和97归并成{65 97}，76和13归并成{13 76}，27没有归并对象
3. 两两归并，{38 49}和{65 97}归并成{38 49 65 97}，{13,76}和27归并成{13 27 76}
4. 两两归并，{38 49 65 97}和{13 27 76}归并成{13 27 38 49 65 76 97}
   

• 时间复杂度：O(nlog2n)
• 空间复杂度:因为需要将这个待排序序列转存到一个数组，所以需要额外开辟大小为n的存储空间，即空间复杂度为O(n)
• 稳定性：稳定

6、 基数排序

基数排序又称为“桶子法”，从低位开始将待排序的数按照这一位的值放到相应的编号为0~9的桶中。等到低位排完得到一个子序列，再将这个序列按照次低位的大小进入相应的桶中，一直排到最高位为止，数组排序完成。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序。

例子：53, 3, 542, 748, 14, 214, 154, 63, 616

• 补充位数：053, 003, 542, 748, 014, 214, 154, 063, 616

• 桶实际是一个队列，先进先出(从桶的上面进，下面出)

• 关键字数量为n,关键字的位数为d,比如748 d=3，r为关键字的基的个数，就是组成关键字的数据的种类，比如十进制数字一共有0至9一共10个数字，即r=10
  

• 空间复杂度：需要辅助存储空间r个队列，所以空间复杂度为O( r )

• 时间复杂度：需要进行关键字位数d次"分配"和"收集"，一次"分配"需要将n个关键字放进各个队列中，一次"收集"需要将r个桶都收集一遍。所以一次"分配"和一次"收集"时间复杂度为O(n+r)。d次就需要O(d(n+r))的时间复杂度。

• 稳定性：由于是队列，先进先出的性质，所以在分配的时候是按照先后顺序分配，也就是稳定的，所以收集的时候也是保持稳定的。即基数排序是稳定的排序算法。

7、 内部排序归纳总结

7.1 复杂度比较

7.2 如何选择排序

1. 当n较小（n<50），选用直接插入排序或简单选择排序，或者冒泡排序
   简单选择排序的比较次数与序列初始状态无关（归并排序也是）
2. n为中等规模（或者较大规模），使用希尔排序
3. n很大时，选用快排、堆排序、归并排序或基数排序
    ①数据分布随机→快排（在实际应用中最优）
    ②取一大堆数据中的 k 个最大（最小）元素→堆排序
    ③记录的关键字位数较少且可以分解时→基数排序

7.3 稳定性

$$稳定性\{\begin{array}{rcl}稳定& & 插入排序、冒泡排序、归并排序和基数排序\\ & & \\ 不稳定& & 简单选择排序、快速排序、希尔排序和堆排序\end{array}$$

8、 外部排序

8.1 定义

需要将待排序的记录存储在外存上，排序时再把数据一部分一部分的调入内存进行排序。在排序过程中需要多次进行内存和外存之间的交换，对外存文件中的记录进行排序后的结果仍然被放到原有文件中。

• 如何得到初始的归并段
  • 置换选择排序：解决排序段放入内存的问题
• 如何减少多个归并段的归并次数
  • 最佳归并树：最少的归并次数（I/O次数）
• 如何每次m路归并快速得到最小的关键字
  • 败者树：减少比较次数
• 概要: 内存容量无法容纳大量数据

---

考研tips:
能够手动模拟各个排序算法的过程，根据要求选择合适排序算法
掌握排序算法思想，特征（初态的影响、时空复杂度、稳定性、适用性）

---

参考博客：

1. 《比较排序算法》Dennis Gao
2. Java实现堆排序和图解 Fuzz_
3. 动画图解：十大经典排序算法动画与解析，看我就够了！

---

小狼的相关博文：

1. 算法（Algorithm）与数据结构（Data Structure）——索引
2. 计算机408考试纲要