软件设计师 http://www.educity.cn/jiaocheng/zg7.html
1.4 排序
所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。当待排序记录的关键字均不相同时，排序结果是唯一的，否则排序结果不唯一。
在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
1.4.1 插入排序
插入排序的基本思想是，每步将一个待排序的记录按其排序码值的大小，插到前面已经排好的文件中的适当位置，直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。
1.直接插入排序
直接插入排序的过程是，在插入第i个记录时，R1,R2,…，Ri-1已经排好序，将第i个记录的排序码ki依次和R1,R2,…，Ri-1的排序码逐个进行比较，找到适当的位置。 使用直接插入排序，对于具有n个记录的文件，要进行n–1趟排序。各种状态下的时间复杂度如表1-1所示。
表1-2 直接插入排序有关数据
说明：初始文件按关键字递增排序，简称\正序\初始文件按关键字递减排序，简称\反序\
软件设计师 http://www.educity.cn/jiaocheng/zg7.html
2.希尔排序
希尔（Shell）排序的基本思想是，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2 一般取d1=n/2,di+1=di/2.如果结果为偶数，则加1,保证di为奇数。 例如，要对关键码{72,28,51,17,96,62,87,33,45,24}进行排序，这里n=10,首先取d1=n/2=5.则排序过程如图1-12所示。 图1-15 希尔排序的过程 希尔排序是不稳定的，希尔排序的执行时间依赖于增量序列，有人在大量实验的基础上指出，当n在某个特定范围内时，希尔排序的平均时间复杂度为O（n1.3）。 1.4.2 选择排序 选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列的后面，直到全部排完。选择排序中主要使用直接选择排序和堆排序。 1.直接选择排序 直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第1个记 软件设计师 http://www.educity.cn/jiaocheng/zg7.html 录交换，然后在其余的记录内选出排序码最小的记录，与第2个记录交换……依次类推，直到所有记录排完为止。 无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n–i次比较，因此，总的比较次数为n（n–1）/2=O（n2）。当初始文件为正序时，移动次数为0;文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3（n–1）。直接选择排序的平均时间复杂度为O（n2）。直接选择排序是不稳定的。 2.堆排序 堆排序是一种树形选择排序，是对直接选择排序的有效改进。n个关键字序列Kl,K2,…，Kn称为堆，当且仅当该序列满足（Ki≤K2i且Ki≤K2i+1）或（Ki≥K2i且Ki≥K2i+1），（1≤i≤ ）。根结点（堆顶）的关键字是堆里所有结点关键字中最小者，称为小根堆；根 结点的关键字是堆里所有结点关键字中最大者，称为大根堆。 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树，即树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。 堆排序的关键步骤有两个，一是如何建立初始堆；二是当堆的根结点与堆的最后一个结点交换后，如何对少了一个结点后的结点序列做调整，使之重新成为堆。 下面，我们通过一个例子来具体说明建立初始堆和调整堆的过程。假设关键字序列为{42,13,24,91,23,16,05,88},则第一次建立的二叉树如图1-16（a）所示。 ①从i = [n/2]开始比较父结点和子结点的关系，如果不满足堆的定义，就进行调整。我们假设需要建立大根堆，本题n=8,所以从第4个元素（91）开始调整。 因为91大于其子结点88,所以不需要调整； 软件设计师 http://www.educity.cn/jiaocheng/zg7.html 再看第3个元素（24），同样，因为24大于其子结点16和05,也不需要调整； 再看第2个元素（13），13小于其子结点23和91,需要把13和91交换（把父结点与关键值最大的那个子结点交换）。这时，13比其子结点88要小，又需要交换。结果如图1-16（b）所示。 图1-16 建立堆的过程 再看第1个元素（42），因为42小于其左子结点91,需要交换。 这时，42还小于其左子结点88,又需要交换42和88的值。建堆过程结束，所建立的初始堆如图1-17（a）所示。 ②在初始堆的基础上，把第一个元素（91）和最后一个元素（13）交换，输出91.这时，如图1-17（b）所示。 图1-17 初始堆及调整1 ③在图1-17（b）的基础上，因13小于其左右子结点88和24,则和88交换，交换后， 软件设计师 http://www.educity.cn/jiaocheng/zg7.html 13还小于其左右子结点42和23,则和42再交换，如图1-18（a）所示。 ④图1-18（a）又是一个n–1个元素的堆，把第一个元素（88）和最后一个元素（05）交换，输出88.这时，如图1-18（b）所示。 ⑤在图1-18（b）的基础上，因05小于其左右子结点42和24,则和42交换，交换后，05还小于其左右子结点13和23,则和23再交换，如图1-19（a）所示。 ⑥图1-19（a）又是一个n–2个元素的堆，把第一个元素（42）和最后一个元素（16）交换，输出42.这时，如图1-19（b）所示。 图1-18 调整堆的过程之1 图1-19 调整堆的过程之2 ⑦在图1-19（b）的基础上，因16小于其左右子结点23和24,则和24交换。如图1-20（a）所示。