数据结构排序要点.ppt

* 最简单的归并排序方法与内排序中的二路归并类似。假设一具有n个记录的文件，先把该文件看作是由n个长度为1的顺串组成，然后在此基础上进行两两归并。经过log2n趟归并后，当文件中只含有一个长度为n的顺串时，整个文件的排序就完成了。在每一躺排序过程中都需要进行记录的内、外存交换。 外部排序的基本方法 * 还有一种常用的外部排序方法是多路归并排序。由于在外部排序过程中，数据的内外存交换所需的时间比记录的内部归并所需的时间大得多，所以可以通过减少数据内外存交换的次数来提高外部排序的效率。为了不增加内部归并时所需进行关键字比较的次数，在具体实现时通常不用选择排序的方法，而用“败者树”来实现。 外部排序的基本方法 * 排序小结 本章重点掌握内排序。不仅要掌握各种内 排序的基本思想（过程），而且要掌握各种内 排序方法的时间复杂度、辅助存储空间及稳定 性，尤其要会根据具体情况和要求选择相应的 内排序方法。 各种内部排序方法的比较和选择如下： * 各种内部排序方法的比较 平均时间性能 最好时间性能 最坏时间性能 辅助空间 稳定性 直接插入排序 O(n2) O(n) O(n2) O(1) √ 希尔排序 O(n1.3) O(nlog2n) O(n2) O(1) ? 冒泡排序 O(n2) O(n ) O(n2) O(1) √ 快速排序 O(nlog2n) O(nlog2n) O(n2) O(log2n) ? 简单选择排序 O(n2) O(n2) O(n2) O(1) ? 堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) ? 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) √ 基数排序 O(d(n+rd)) O(d(n+rd)) O(d(n+rd)) O(rd) √ ? * 1）从平均时间而言：快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序。 2）从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较简单，将其认为是简单算法，都包含在上图中的“简单排序”中。对于希尔排序、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序。 3）从稳定性看：直接插入排序、冒泡排序和归并排序是稳定的；而希尔排序、直接选择排序、快速排序和堆排序是不稳定排序。 4）从待排序的记录数n的大小看，n较小时，宜采用简单排序；而n较大时宜采用改进排序。 各种内部排序方法性能比较 * （1）当待排序记录数n 较大时，若要求排序稳定，则采用归并排序。 （2）当待排序记录数n 较大，关键字分布随机，而且不要求稳定时，可采用快速排序； （3）当待排序记录数n 较大，关键字会出现正、逆序情形，可采用堆排序（或归并排序）。 （4）当待排序记录数n 较小，记录已接近有序或随机分布时，又要求排序稳定，可采用直接插入排序。 （5）当待排序记录数n 较小，且对稳定性不作要求时，可采用直接选择排序。 选择排序的方法 * * * 0 1 2 3 4 49 13 65 97 76 7 80 A B 0 1 2 3 4 5 6 7 C i j k 7 9.5 2-路归并排序 二路归并排序的基本思想:将两个有序表合并成一个有序表。