第9章内部排序9.1排序的基本概念2.内部排序与外部排序;根据排序时数据所占用存储器的不同，可将排序分为两类:一类是整个排序过程完全在内存中进行，称为内部排序；另一类是由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，称为外部排序。假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri领先于Rj(即i<j)，经过排序后得到的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，当相同关键字的领先关系在排序过程中发生变化，则称所用的排序方法是不稳定的。无论是稳定的还是不稳定的排序方法，均能排好序。在应用排序的某些场合，如选举和比赛等，对排序的稳定性是有特殊要求的。证明一种排序方法是稳定的，要从算法本身的步骤中加以证明。证明排序方法是不稳定的，只需给出一个反例说明。在排序过程中，一般进行两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置移动到另一个位置。其中操作（1）对于大多数排序方法来说是必要的，而操作（2）则可以通过采用适当的存储方式予以避免。对于待排序的记录序列，有三种常见的存储表示方法:·向量结构：将待排序的记录存放在一组地址连续的存储单元中。由于在这种存储方式中，记录之间的次序关系由其存储位置来决定，所以排序过程中一定要移动记录才行。·链表结构：采用链表结构时，记录之间逻辑上的相邻性是靠指针来维持的，这样在排序时，就不用移动记录元素，而只需要修改指针。这种排序方式被称为链表排序。·记录向量与地址向量结合：将待排序记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址向量。这样在排序过程中不移动记录本身，而修改地址向量中记录的“地址”，排序结束后，再按照地址向量中的值调整记录的存储位置。这种排序方式被称为地址排序。为了讨论方便，假设待排记录的关键字均为整数，均从数组中下标为1的位置开始存储，下标为0的位置存储监视哨，或空闲不用。typedefintKeyType;typedefstruct{KeyTypekey;OtherTypeother-data;}RecordType;9.2插入类排序9.2.1直接插入排序图9.1直接插入排序示例假设待排序记录存放在r[1..n]之中，为了提高效率，我们附设一个监视哨r[0]，使得r[0]始终存放待插入的记录。监视哨的作用有两个：一是备份待插入的记录，以便前面关键字较大的记录后移；二是防止越界，具体算法描述如下：该算法的要点是：①使用监视哨r[0]临时保存待插入的记录；②从后往前查找应插入的位置；③查找与移动在同一循环中完成。直接插入排序算法分析：从空间角度来看，它只需要一个辅助空间r[0]。从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。对于一趟插入排序，算法中的while循环的次数主要取决于待插记录与前i-1个记录的关键字的关系上。最好情况为（顺序）：r[i].key>r[i-1].key，while循环只执行1次，且不移动记录；最坏情况为（逆序）：r[i].key<r[1].key，则while循环中关键字比较次数和移动记录的次数为i-1。对整个排序过程而言，最好情况是待排序记录本身已按关键字有序排列，此时总的比较次数为n-1次，移动记录的次数也达到最小值2（n-1）(每一次只对待插记录r[i]移动两次)；最坏情况是待排序记录按关键字逆序排列，此时总的比较次数达到最大值为(n+2)(n-1)/2，即，记录移动的次数也达到最大值(n+4)(n-1)/2，即。执行的时间耗费主要取决于数据的分布情况。若待排序记录是随机的，即待排序记录可能出现的各种排列的概率相同，则可以取上述最小值和最大值的平均值，约为n2/4。因此，直接插入排序的时间复杂度为T(n)=O(n2)，空间复杂度为S(n)=O(1)。说明排序算法的稳定性必须从算法本身加以证明。直接插入排序方法是稳定的排序方法。在直接插入排序算法中，由于待插入元素的比较是从后向前进行的，循环while(x.key<r[j].key)的判断条件就保证了后面出现的关键字不可能插入到与前面相同的关键字之前。直接插入排序算法简便，比较适用于待排序记录数目较少且基本有序的情况。当待排记录数目较大时，直接插入排序的性能就不好，为此我们可以对直接插入排序做进一步的改进。在直接插入排序法的基础上，从减少“比较关键字”和“移动记录”两种操作的次数着手来进行改进。9.2.2折半插入排序采用折半插入排序法，可减少关键字的比较次数。每插入一个元素，需要比较的次数最大为折半判定树的深度，如插入第i个元素时，设i=2j,则需进行log2i次比较，因此插入n-1个元素的平均关键字的比较次数为O(nlog2