Chapter 9 Sorting
第 9 章 排序
排序的稳定性
对同一关键字，每次排序时，第一永远是第一（针对于同分的情况）
内排序和外排序
内排序是在排序整个过程中，带排序的所有记录全部被放置在内存中。
外排序是由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行。
内排序算法
本章主要讨论内排序算法
时间性能
辅助空间：除了存放待排序所占用的存储空间外，执行算法所需要的其他存储空间
算法的复杂性：算法本身的复杂度
内排序分为插入排序、交换排序、选择排序和归并排序。
冒泡排序
冒泡排序（Bubble Sort）是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止
简单选择排序
简单选择排序法（Simple Selection Sort）就是通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换
直接插入排序
直接插入排序（Straight Insertion Sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录数增1的有序表
希尔排序
希尔排序（Shell Sort）
基本有序：小的关键字基本在前面，大的基本在后面，不大不小的基本在中间
跳跃分割策略：将相距某个“增量”的记录组成一个子序列，这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序
增量排序的最后一个增量值必须等于1才行
堆排序
堆是具有下列性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
或者
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
堆排序算法
将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与对数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了
堆排序复杂度分析
时间复杂度：O(nlogn)
优于冒泡排序、简单选择、直接插入的O(n2)
空间复杂度：只有一个用来交换的暂存单元
归并排序
归并排序（Merging Sort）利用归并的思想
将原始序列拆分成多个小序列，分别排序，归并成一个大一点的序列，再排序，再归并，最终完成整个序列的排序
归并排序复杂度分析
时间复杂度：O(nlogn)
空间复杂度：O(n+logn)
非递归实现归并排序
上面的归并排序大量引用了递归，造成时间和空间上的性能损耗，所以考虑将递归转化为迭代
并且在使用归并排序时，尽量考虑用非递归方法
快速排序
快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的
其中最重要的一步是：选取一段记录中的一个数，使得左边的都比它小，右边的都比它大
于是又得到了两段记录，再分别调用同样的操作，直到顺序全部正确为止
快速排序复杂度分析
时间复杂度：O(nlogn)
空间复杂度：O(logn)
快速排序优化
刚才讲的快速排序有不少可以改进的方案
优化选取枢纽：即选取的第一个元素，很难保证它是一个中间值。
故放弃固定选取的方法，改为，每次调用函数时随机选取枢纽（但会有时间开销，不予考虑）
再对 1 方案进行改进，提出三段取中（median-of-three）法，即取三个关键字先进行排序，将中间数作为枢纽，一般是取左端，右端，和中间三个数（从概率上来说，这样选取出来的数最可能为中间数）
再对 2 方案进行改进，当待排序的序列非常大时，还有一个办法是九数取中（median-of-nine），相当于用四次三段取中，即：先从数组中分三次取样，每次取三个数，三个样品中各取出中数，然后再从三个中数中取出一个中数作为枢纽
优化不必要的交换：让所有的交换尽量一次到位
优化小数组时的排序方案：避免“大炮打蚊子”现象。当数组较小时，选择用直接插入排序
优化递归操作：递归对性能有影响
实施尾递归优化
了不起的排序算法：快速算法被称为20世纪十大算法之一，我们这些玩编程的人还有什么理由不去学习它呢？
总结
排序方法
平均情况
辅助空间
稳定性
冒泡排序
O(n2)
O(1)
稳定
简单选择排序
O(n2)
O(1)
稳定
直接插入排序
O(n2)
O(1)
稳定
希尔排序
O(nlogn)~O(n2)
O(1)
不稳定
堆排序
O(nlogn)
O(1)
不稳定
归并排序
O(nlogn)
O(n)
稳定
快速排序
O(nlogn)
O(logn)~O(n)
不稳定
分类
简单算法：冒泡、简单选择、直接插入
改进算法：希尔、堆、归并、快速
但从综合各项指标来说，经过优化的快速排序是性能最好的排序算法
总的来说，对于排序方法的选择，我们应该如同田忌赛马一般选择最合适的一种。
Last updated