8.1 基本概念

自然排序：输入数据越有序，排序的速度越快的排序方法。
内存排序：排序时只用到内存没有用到外存
串行排序：单个处理器，而非多个同时进行
比较排序：用比较的方法

8.2 插入排序

8.2.1 直接插入排序

8.2.2 二分插入排序

8.2.3 希尔排序：不稳定

8.3 交换排序

8.3.1 冒泡排序

  • n个记录，总共需要n-1趟
    第m趟需要比较n-m次

小改进，如果某一趟没有发生交换，说明已经排序完毕。

8.3.2 快速排序

升级快速排序：不用单独开辟存放子表的空间，但是因为递归需要建立栈
①每一趟的子表的形成是采用从两头向中间交替式逼近法;
②由于每趟中对各子表的操作都相似，可采用递归算法。

  • 划分元素的选取是影响时间性能的关键
    输入数据次序越乱，所选划分元素值的随机性越好，排序速度越快，快速排序不是自然排序方法。
    改变划分元素的选取方法，至多只能改变算法平均情况的下的时间性能，无法改变最坏情况下的时间性能。即最坏情况下，快速排序的时间复杂性总是O(n2)

8.4 选择排序

如何从无序数列生成堆呢？
单结点的二叉树是堆;
在完全二叉树中所有以叶子结点（序号i > n/2）为根的子树是堆。这样，我们只需依次将以序号为n/2,n/2 - 1，…1的结点为根的子树均调整为堆即可。

因为堆顶始终是最小（大）值，所以每次都输出根节点，然后进行调整。不断输出的根节点就可以组成一个有序序列。

堆排序方法对初始序列没有依赖性，初始有序无序所花时间空间没有多少变化

8.5 归并排序

8.6 基数排序

选取多个关键字，优先级低的先分配收集，优先级最高的最后进行分配收集。

有趣的例子：对打乱的扑克牌进行排序
先根据花色进行分配收集，后根据点数进行分配收集。最后得到点数从小到大并且同一点数的牌都按相同花色顺序排列。

综合比较