8.7 本 章 小 结

 

8.7  本 章 小 结

本章的基本内容是：各种排序的基本思路和算法。

（1）直接插入排序、直接选择排序和冒泡排序是3种简单型的排序方法，其时间复杂度均为O(n²)，空间复杂度均为O(1)，但直接插入排序又优于直接选择排序，而直接选择排序又优于冒泡排序。

（2）快速排序和归并排序是改进型的排序方法，时间复杂度均为O(log₂n)，空间复杂度分别为O(log₂n)和O(n)。通常快速排序优于归并排序。

（3）希尔排序也是一种改进型的排序方法，其时间复杂度大约为O(n^1.3)左右，空间复杂度为O(1)。

（4）直接插入排序、冒泡排序、归并排序是稳定的排序方法，而希尔排序、直接选择排序、快速排序是不稳定的排序方法。

（5）快速排序的最好情况是每次能划分出左右两个均匀的子序列，最坏情况是划分出来的两个子序列有一个为空。

（6）归并排序是将两个有序子序列合并为一个有序序列，合并后，序列的个数不断减少，序列的长度不断增加，直至剩下一个有序序列，才得到排序结果，但排序中必须占用等量的辅助空间。

（7）排序有内排序和外排序之分，直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序一般适合于内排序，而归并排序既适合于内排序，也适合于外排序。

（8）各种不同的排序方法一般可根据不同的条件及环境分别选择，排序记录少，可以选择时间复杂度为O(n²)的排序方法；如果复杂，可选取时间复杂度为O(log₂n)的排序方法。

8.8  练  习  题

1．选择题

（1）在文件局部有序或文件较小的情况下，最佳的排序方法是      。

A．直接插入排序                             B．直接选择排序

C．冒泡排序                                    D．归并排序

（2）具有24个记录的序列，采用冒泡排序最少的比较次数为      。

A．1                           B．23                          C．24            D．529

（3）用某种排序方法对序列{25,84,21,47,15,27,68,35,20}进行排序，记录序列的变化情况如下：

258421471527683520

201521254727683584

152021253527476884

152021252735476884

则采用的排序方法是      。

A．直接选择排序                                    B．冒泡排序

C．快速排序                                           D．二路归并排序

（4）在排序过程中，键值比较的次数与初始序列的排序无关的是      。

A．直接插入排序和快速排序                   B．直接插入排序和归并排序

C．直接选择排序和归并排序                   D．快速排序和归并排序

（5）      方法是从排序序列中依次取出元素与已经排序序列中的元素进行比较，将其放入已经排序序列的正确位置上。

A．归并排序        B．插入排序               C．快速排序        D．选择排序

（6）      是从未排序序列中挑选元素，并将其依次放入已经排序序列的一端。

A．归并排序        B．插入排序               C．快速排序        D．选择排序

（7）      方法是对序列中的元素通过适当的位置变换将有关元素一次性地放置在其最终位置上。

A．归并排序        B．插入排序               C．快速排序        D．基数排序

（8）将上万个无序并且互不相等的正数存储在顺序存储结构中，采取      方法能够最快地找到其中最大的正整数。

A．快速排序        B．插入排序               C．选择排序        D．归并排序

（9）以下4种排序方法，要求附加内存空间最大的是      。

A．插入排序        B．选择排序               C．快速排序        D．归并排序

（10）以下不稳定的排序方法是      。

A．直接插入排序                                  B．冒泡排序

C．直接选择排序                                          D．二路归并排序

（11）以下稳定的排序方法是      。

A．快速排序                                         B．冒泡排序              

C．直接选择排序                                          D．堆排序

（12）快速排序方法在      情况下最不利于发挥其长处。

A．要排序的数据量太大                        B．要排序的数据中含有多个相同值

C．要排序的数据已基本有序                 D．要排序的数据个数为奇数

（13）设有1 000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用      方法。

A．冒泡排序             B．快速排序        C．堆排序            D．基数排序

（14）一级记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法以第一个记录为基准得到的一次划分结果为      。

A．38，40，46，56，79，84                 B．40，38，46，79，56，84

C．40，38，46，56，79，84                 D．40，38，46，84，56，79

（15）一组记录的关键码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为      。

A．79，46，56，38，40，84                 B．84，79，56，38，40，46

C．84，79，56，46，40，38                 D．84，56，79，40，46，38

（16）若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24）从小到大进行排序，共要进行      次比较。

A．33                 B．45                   C．70                          D．91

（17）一组记录的关键字为（32，41，15，39，77，12，48，30，52），其中含有3个长度为3的有序表，按归并排序的方法对该序列进行一趟归并后的结果为      。

A．15，32，41，12，39，77，30，48，52

B．12，15，32，39，41，77，30，48，52

C．12，15，32，39，41，77，48，30，52  

D．12，15，30，32，39，41，48，52，77

2．填空题

（1）在对一组记录54，38，96，23，15，72，60，45，83进行直接插入排序时，当把第7个记录“60”插入到有序表时，为寻找插入位置需比较         次。

（2）在利用快速排序方法对54，38，96，23，15，72，60，45，83进行快速排序时，递归调用而使用的栈所能达到的最大深度为         ，共需递归调用的次数为         ，其中第二次递归调用是对         一组记录进行快速排序。

（3）在堆排序、快速排序和归并排序中，若只从存储空间考虑，则应首先选取        

方法，其次选取         方法，最后选取         方法；若只从排序结果的稳定性考虑，则应选取         方法；若只从平均情况下排序最快考虑，则应选取         方法；若从最坏情况下排序最快并且要节省内存考虑，则应选取         方法。

（4）在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有         。

（5）在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是         ，需要内存量最多的是         。

（6）在堆排序和快速排序中，若原始记录接近正序或反序，则选用         ，若原始记录无序，则选用         。

（7）在插入排序和选择排序中，若初始数据基本正序，则选用         ，若初始数据基本反序，则选用         。

（8）对n个元素的序列进行冒泡排序时，最少的比较次数是         。

3．问答题

（1）已知序列{17,18,60,40,7,32,73,65,85}，请给出采用冒泡排序法对该序列进行升序排序时的每一趟结果。

（2）已知序列{503,87,512,61,908,170,897,275,653,462}，请给出采用快速排序法对该序列进行升序排序时的每一趟结果。

（3）已知序列{503,17,512,908,170,897,275,653,426,154,509,612,677,765,703,94}，请给出采用希尔排序法（d1=8）对该序列进行升序排序时的每一趟结果。

（4）已知序列{70,83,100,65,10,32,7,9}，请给出采用简单插入排序法对该序列进行升序排序时的每一趟结果。

（5）已知序列{10,18,4,3,6,12,1,9,18,8}，请给出采用归并排序法对该序列进行升序排序时的每一趟结果。

4．上机操作题

（1）已知奇偶转换排序如下所述：第一趟对所有奇数的i，将a[i]和a[i+1]进行比较，第二趟对所有偶数的i，将a[i]和a[i+1]进行比较，每次比较时若a[i]>a[i+1]，则将两者交换，以后重复上述两趟过程交换进行，直至整个数组有序。

①试问排序结束的条件是什么?

②编写一个实现上述排序过程的算法。

（2）已知整型数组A[n]，设计一个算法调整A的数组元素，使其前边的所有数组元素小于0，后边的所有数组元素都不小于0（要求算法的时间复杂度为O(n)）。

（3）设n个互不相同的排序码值存于顺序表r[n]中，首先对每个记录统计排序码值比其小的记录个数，并根据统计结果将每个记录移到正确的位置上，请编写实现上述功能的算法。

（4）已知排序码值序列{k₁,k₂…k_n}是小根堆，试写一个算法，添加排序码值x到堆中{ k₁,k₂…k_n,x}后，将其调整成小根堆的算法，排序码值为k_i的记录存于r[i-1]中。

（5）节点类型和存储方式如下：

typedef struct

{

    int key;

     DataType data;  //DataType为一个数据类型

    int count;

} NodeType;

给出一个排序方法，不移动节点存储位置，只在节点的count字段记录节点在排序中的序号。