第10章-内部排序.doc

第十章 内部排序
快速 选择 堆 希尔 不稳定，选择 堆 希尔的空间复杂度为o(1) 不稳定中，选择是简单的。其余都是稳定的，稳定之中归并 和基数较复杂。
时间复杂度涉及o(nlog2n)的是快速 堆 希尔 归并
插入排序和冒泡排序是一样的 选择排序与插入排序和冒泡排序的最好情况不一样 是o(n2)而插入排序和冒泡排序是o(n) 且选择排序不稳定 但是是简单的 不稳定 不简单的是 快速 堆 希尔。选择 堆 希尔 插入 冒泡的空间复杂度是o(1)

希尔排序 O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂

一、时间性能
按平均的时间性能来分，有三类排序方法：
时间复杂度为O(nlogn)的方法有：快速排序、堆排序和归并排序，其中以快速排序为最好；
时间复杂度为O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；
时间复杂度为O(n)的排序方法只有，基数排序。
当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。
简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。
二、空间性能
指的是排序过程中所需的辅助空间大小。
1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；
2. 快速排序为O(logn )，为栈所需的辅助空间;
3. 归并排序所需辅助空间最多，其空间复杂度为O(n );
4.链式基数排序需附设队列首尾指针，则空间复杂度为O(rd )。
三、排序方法的稳定性能
1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。
2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。
3. 对于不稳定的排序方法，只要能举出一个实例说明即可。
4. 快速排序和堆排序是不稳定的排序方法
课程提要：
【主要内容】
1．插入排序
2．交换排序
3．选择排序
4．归并排序
5．基数排序
6．各种内部排序方法的比较与讨论
【教学目标】
1．深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。
2．了解各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序等。
3．掌握各种排序方法的时间复杂度的分析方法。
4．理解排序方法“稳定”和“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。
5．希尔排序、快速排序、堆排序和归并排序等高效方法是本章的重点和难点。

学习指导：
概念
Ÿ 排序：是计算机程序设计中一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为关键字。排序的确切定义如下：
输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。
输出：Ri1，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin（或Ki1≥Ki2≥…≥Kin）。
Ÿ 文件：文件是由一组记录组成的。记录则是由若干个数据项（或域）组成。其中有一项可用来标识一个记录，称为关键字项，该数据项的值称为关键字（Key）。
Ÿ 稳定性：若对任意的数据元素序列使用某个排序方法，对它按关键字进行排序，若相同关键字元素间的位置关系排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。
Ÿ 排序的分类：（1）按是否涉及数据的内、外存交换分类。在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序（简称内排序）。适合不太大的元素序列；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。适合大元素序列。（2）按排序策略分类。可以分为五类：插入排序、选择排序、交换排序、归并排序和基数排序。
2．插入排序
（1）直接插入排序
直接插入排序方法的算法思想是：仅有一个记录的表总是有序的，因此，对n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键字有序的表。算法的时间复杂度为O(n2)，需要一个辅助空间，是就地排序。
直接插入排序是稳定排序。
【例8-1】已知关键字序列（12，77，21，65，38，7，38，53），给出采用直接插入排序方法按关键字递增序排列时的每一趟结果。
解： 初始 12 77 21 65 38 7 38 53
1趟 12 77 21 65 38 7 38 53
2趟 12 21 77 65 38 7 38 53
3趟 12 21 65 77 38 7 38 53
4趟 12 21 38 65 77 7 38 53
5趟 7 12 21 38 65 77 38 53
6趟 7 12 21 38 38 65 77 53
7趟 7 12 21 38 38 53 65 77
（ 表示有序区）
（2）折半插入排序
折半插入排序的算法思想是：向有序表中插入一个记录，在有序表中确定插入位置，可以不断二分有序表来确定插入位置，即一次比较，通过待插入记录与有序表居中的记录按关键字比较，将有序表一分为二，下次比较在其中一个有序子表中进行，将子表又一分为二。这样继续下去，直到要比较子表中只有一个记录时，比较一次便确定了插入位置。
确定插入位置所进行的折半查找，仅减少了关键字间的比较次数，而记录的移动次数不变，故时间复杂度仍为O(n2)。是一个稳定的排序方法。
（3）希尔排序
希尔排序的算法思想是：
①选择一个步长序列t1，t2，…，tk，其中ti>tj，tk=1。
②按步长序列个数k，对序列进行k趟排序。
③每趟排序根据对应的步长ti，将待排序列分隔成若干长度为m的子序列，分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
希尔排序算法分析很难， 关键字的比较次数与记录移动次数依赖于步长因子序列的选取，特定情况下可以准确估算出关键字的比较次数和记录的移动次数。希尔排序是不稳定排序，它需要一个辅助空间，即就地排序。希尔排序记录的比较次数和移动次数都比直接插入排序时要少，n越大时，效果越明显。
【例8-2】待排序列为（ 39，80，76，41，13，29，50，78，30，11，100，7，41，86），步长因子分别取5、3、1，给出采用希尔排序方法按关键字递增序排列时的每一趟结果。
解：排序过程如下：
p=5　　39 80 76 41 13 29 50 78 30 11 100 7 41 86

子序列分别为{39，29，100}，{80，50，7}，{76，78，41}，{41，30，86}，{13，11}。
第一趟排序结果：
p=3 29 7 41 30 11 39 50 76 41 13 100 80 78 86

子序列分别为{29，30，50，13，78}，{7，11，76，100，86}，{41，39，41，80}。
第二趟排序结果：
p=1 13 7 39 29 11 41 30 76 41 50 86 80 78 100
此时，序列基本“有序”，对其进行直接插入排序，得到最终结果：
7 11 13 29 30 39 41 41 50 76 78 80 86 100
3．交换排序
（1）冒泡排序
冒泡排序的算法思想是：对n个记录的表，第一趟冒泡得到一个关键字最大的记录r[n]，第二趟冒泡对n-1个记录的表，再得到一个关键字最大的记录r[n-1]，如此重复，直到n个记录按关键字有序。
① j=n。
② 若j＜2，排序结束。
③ i=1。 //一趟冒泡，设置从第一个记录开始进行两两比较
④ 若i≥j，一趟冒泡结束，j=j-1；冒泡表的记录数-1，转（ii）
⑤ 比较r[i].key与r[i+1].key，若r[i].keyr≤[i+1].key，不交换，转（vii）
⑥ 当r[i].keyr＞[i+1].key时，将r[i]与r[i+1]交换。
⑦ i=i+1；调整对下两个记录进行两两比较，转（iv）
冒泡排序是稳定排序，移动记录次数较多，平均时间性能比直接插入排序差。时间复杂度为O(n2)。空间复杂度为O(1)，仅用了一个辅助单元，是就地排序。

【例8-3】已知序列（17，18，60，40，7，32，73，65，85），请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。
解：
初始 1趟 2趟 3趟 4趟 5趟
17 17 17 17 7 7
18 18 18 7 17 17
60 40 7 18 18 18
40 7 32 32 32 32
7 32 40 40 40 40
32 60 60 60 60 60
73 65 65 65 65 65
65 73 73 73 73 73
85 85 85 85 85 85
（ 表示有序区）
（2）快速排序
快速排序的算法思想是：通过比较关键字、交换记录，以某个记录为界（该记录称为支点），将待排序列分成两部分。其中一部分所有记录的关键字大于等于支点记录的关键字，另一部分所有记录的关键字小于支点记录的关键字。将待排序列按关键字以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键字有序。
快速排序是不稳定排序，当n较大时，在平均情况下它是速度最快的一种排序方法。时间复杂度为O(nlog2n)，就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。空间复杂度为O(log2n)。

【例8-4】已知关键字序列（38，12，21，77，65，7，38，53）给出采用快速排序方法按关键字增序排序时的第一趟块排过程，并举出一个反例说明快速排序是不稳定排序。
解：（1）
初始 38 12 21 77 65 7 38 53
↑ ↑
low high
第一次交换
从high开始比较，得到的结果：
7 12 21 77 65 □ 38 53
↑ ↑
low high
从low开始比较，得到的结果：
7 12 21 □ 65 77 38 53
↑ ↑
low high
第二次交换
从high开始比较，得到的结果：
7 12 21 □ 65 77 38 53
↑↑
low high
low=high，所以第一趟快速排序的结果为：
7 12 21 38 65 77 38 53
（2）关键字序列（2，2，1）可以作为一个反例。取第一个关键字作为支点，在一趟快排之后的结果是（1，2，2），由于2已在排序后的最终位置，2在2划分出的前一部分子表中，所以2不可能再出现在2之后，即不可能与原始序列中两者的顺序一致。此反例说明快速排序不是稳定排序。
4．选择排序
（1）简单选择排序
简单选择排序的算法思想是：
第一趟，从n个记录中找出关键字最小的记录与第一个记录交换；第二趟，从第二个记录开始的n-1个记录中再选出关键字最小的记录与第二个记录交换；如此，第i趟，则从第i个记录开始的n-i+1个记录中选出关键字最小的记录与第i个记录交换，直到整个序列按关键字有序。
由于存在不相邻记录之间的交换，可能改变相同关键字记录的前后顺序，所以此方法是不稳定排序。当每一记录占用的空间较多时，此方法比直接插入排序快。
时间复杂度为O(n2)，比较次数与表的初始状态无关。空间复杂度为O(1)，在记录交换位置时需要一个辅助空间。
（2）树形选择排序
树形选择排序的算法思想是：按照锦标赛的思想进行选择排序。即将n个参赛的选手看成一棵完全二叉树的叶结点，则该完全二叉树有2n-2或2n-1个结点。首先，树中兄弟两两进行比赛（比较大小），如果该结点无兄弟，则轮空，直接进入下议论。胜出（较大）的在兄弟间再两两进行比较，直到产生第一名；接下来，将作为第一名的结点看成最差的，并从该结点开始，沿该结点到根路径上，依次进行各分支结点孩子结点间的比较，胜出的就是第二名。如此，继续进行下去，直到所有选手的名次排定。
时间复杂度为O(nlog2n)。该方法占用空间较多，除需要输出排序结果的n个单元外，尚需n-1个辅助单元，且要和“最大值”进行多余的比较等缺点。
（3）堆排序
堆排序的算法思想是：设有n个元素，将其按关键字排序。首先将这n个元素按关键字建成堆，将堆顶元素输出，得到n个元素中关键字最小（或最大）的元素。然后，再对剩下的n-1个元素建成堆，输出堆顶元素，得到n个元素中关键字次小（或次大）的元素。如此反复，便得到一个按关键字有序的序列。称这个过程为堆排序。
堆排序是不稳定排序，初始建堆所需的比较次数较多，因此记录数较少时不宜采用。堆排序在最坏情况下时间复杂度为O(nlog2n)，相对于快速排序最坏情况下为O(n2)而言是一优点。空间复杂度为O(1)。

【例8-5】已知序列（503，87，512，61，908，170，897，275，653，462），给出采用堆排序方法按关键字递增排序时的每一趟结果。
(a) 初始
1
503
87
275
653
462
908
61
170
897
512
2
3
4
5
6
7
8
9
10
(b) 建堆
1
908
87
275
653
503
462
61
170
512
897
2
3
4
5
6
7
8
9
10
(c) 1趟：交换908和87
1
908
87
275
653
503
462
61
170
512
897
2
3
4
5
6
7
8
9
10
(d) 筛选调整
1
908
87
275
653
503
462
61
170
897
512
2
3
4
5
6
7
8
9
10
(e) 2趟：交换897和61
1
908
87
275
653
503
462
61
170
897
512
2
3
4
5
6
7
8
9
10
(f) 筛选调整
1
908
87
897
503
275
462

61
170
653
512
2
3
4
5
6
7
8
9
10
解：各趟结果如图8-1所示

(o) 7趟：交换275和61
8
1
908
87
897
275
462
503
61
653
512
170
2
3
4
5
6
7
9
10
(p) 筛选调整
8
1
908
87
897
275
462
503
61
653
512
170
2
3
4
5
6
7
9
10
(m) 6趟：交换462和87
8
1
908
87
897
275
462
503
61
653
512
170
2
3
4
5
6
7
9
10
(n) 筛选调整
8
1
908
87
897
275
462
503
61
653
512
170
2
3
4
5
6
7
9
10
(i) 4趟：交换512和87
1
8
908
87
897
503
275
462
61
653
512
170
2
3
4
5
6
7
9
10
(j) 筛选调整
1
8
908
87
897
462
275
512
61
653
503
170
2
3
4
5
6
7
9
10
8
(g) 3趟：交换653和61
1
908
87
653
503
275
462
61
170
897
512
2
3
4
5
6
7
9
10
1
8
(h) 筛选调整

908
87
897
503
275
462
61
653
512
170
2
3
4
5
6
7
9
10
1
462
(k) 5趟：交换503和61
8
1
908
61
897
462
275
503
87
653
512
170
2
3
4
5
6
7
9
10
(l) 筛选调整
8
908
87
897
275
503
512
61
653
170
2
3
4
5
6
7
9
10

(s) 8趟：交换87和61
图8-1数据堆排序过程
8
1
908
87
897
275
462
503
61
653
512
170
2
3
4
5
6
7
9
10
(q) 8趟：交换170和61
8
1
908
87
897
275
462
503
61
653
512
170
2
3
4
5
6
7
9
10
(r) 筛选调整
8
1
908
61
897
275
462
503
87
653
512
170
2
3
4
5
6
7
9
10

5．归并排序
（1）归并排序的算法思想是：设r[u..t]由两个有序子表r[u..v-1]和r[v..t]组成，两个子表长度分别为v-u、t-v+1。合并步骤如下：
①设置两个子表的起始下标及辅助数组的起始下标为：i=u；j=v；k=u。
②若i>v或j>t，转④。
③选取r[i]和r[j]关键字较小的存入辅助数组rf。
如果r[i].key<r[j].key，rf[k]=r[i]；i++；k++；转②。否则，rf[k]=r[j]；j++；k++；转②。
④将尚未处理完的子表中元素存入fr。如果i<v，将r[i..v-1]存入rf[k..t]。如果j<=t，将r[i..v]存入rf[k..t]。
⑤合并结束。
（2）两路归并的迭代算法
一个元素的表总是有序的。所以对n个元素的待排序列，每个元素可看成一个有序子表。对子表两两合并生成个子表，所得子表除最后一个子表长度可能为1外，其余子表长度均为2，再进行两两合并，直到生成n个元素按关键字有序的表。
（3）算法分析
归并排序是稳定排序，若用单链表作为存储结构，可以实现就地排序。这种排序方法可用于内部排序，也可用于外部排序中。时间复杂度为O(nlog2n)。需进行log2n趟归并，每一趟归并中，比较次数最多为n次，移动次数等为2n次。空间复杂度为O(n)。
6．基数排序
基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
（1）多关键字排序
多关键字排序按照从最主位关键字到最次位关键字或从最次位关键字到最主位关键字的顺序逐次排序，分两种方法：
①最高位优先法（简称MSD法）
②最低位优先法（简称LSD法）
（2）链式基数排序
①算法思想
基数排序：从最低位关键字起，按关键字的不同值将序列中的记录“分配”到RADIX个队列中，然后再“收集”之。如此重复d次即可。链式基数排序是用RADIX个链队列作为分配队列，关键字相同的记录存入同一个链队列中，收集则是将各链队列按关键字大小顺序连接起来。
②算法分析
基数排序是稳定排序，如果记录序列初始不是顺序存储，而是单链表形式，那么各辅助链队列无须分配结点空间，利用原链表的结点空间即可，而且分配和收集时都不必移动记录，只要修改指针，这样可以节省一定的时间和空间。
7．各种内部排序方法的比较与讨论
（1）内部排序方法的共同点
①基本操作相同
大多数排序算法都有两个基本的操作：
（i）比较两个关键字的大小。
（ii）改变指向记录的指针或移动记录本身，这种基本操作的实现依赖于待排序记录的存储方式。
②待排文件的常用存储方式相同
尽管排序可以采用不同方法，但所有待排序文件的存储方式都可以采用以下形式：
（i）顺序表（或直接用向量）作为存储结构
（ii）以链表作为存储结构。
（iii）用顺序的方式存储待排序的记录，但同时建立一个辅助表。
（2）内部排序方法的不同点
排序方法
平均时间复杂度
最坏时间复杂度
辅助存储空间
稳定性
插入排序
O(n2)
O(n2)
O(1)
稳定
希尔排序
不确定
不确定
O(1)
不稳定
冒泡排序
O(n2)
O(n2)
O(1)
稳定
简单选择排序
O(n2)
O(n2)
O(1)
稳定
基数排序
O(d(n+rd))
O(d(n+rd))
O(rd)
稳定
快速排序
O(nlogn)
O(n2)
O(logn)
不稳定
堆排序
O(nlogn)
O(nlogn)
O(1)
不稳定
归并排序
O(nlogn)
O(nlogn)
O(n)
稳定
（3）排序方法的选择
①若n较小（如n≤50）可采用直接插入或简单选择排序。
②若文件初始状态基本有序（指正序），则应选用直接插入、冒泡或随机的快速排序为宜。
③若n较大，则应采用时间复杂度为O（nlogn）的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

一、选择题
1、若需要在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
A. 快速排序　 B. 堆排序 C. 归并排序 D. 直接插入排序
2、下列排序方法中（ ）方法是不稳定的。
A. 冒泡排序 B. 选择排序 C. 堆排序 D. 直接插入排序
3、一个序列中有10000个元素，若只想得到其中前10个最小元素，则最好采用（ ）方法。
A. 快速排序　 B. 堆排序 C. 插入排序 D. 归并排序
4、一组待排序序列为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为（ ）。
A. 79,46,56,38,40,80 B. 84,79,56,38,40,46
C. 84,79,56,46,40,38 D. 84,56,79,40,46,38
5、快速排序方法在（ ）情况下最不利于发挥其长处。
A. 要排序的数据量太大 B. 要排序的数据中有多个相同值
C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数
6、排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置，这是（ ）排序的基本思想。
A. 堆排序 B. 直接插入排序 C. 快速排序 D. 冒泡排序
7、在任何情况下，时间复杂度均为O(nlogn)的不稳定的排序方法是（ ）。
A.直接插入　 B. 快速排序 C. 堆排序 D. 归并排序
8、如果将所有中国人按照生日来排序，则使用（ ）算法最快。
A. 归并排序　 B. 希尔排序 C. 快速排序 D. 基数排序
9、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。
A. O(log2n)　 B. O(1) C. O(n) D. O(nlog2n)
12、用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：
⑴ 25，84，21，47，15，27，68，35，20
⑵ 20，15，21，25，47，27，68，35，84
⑶ 15，20，21，25，35，27，47，68，84
⑷ 15，20，21，25，27，35，47，68，84
则所采用的排序方法是（ ）。
A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序
13、设有1024个无序的元素，希望用最快的速度挑选出其中前5个最大的元素，最好选用（ ）。
A. 冒泡排序　 B. 选择排序 C. 快速排序 D. 堆排序
14、下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是（ ）。
A. 快速排序　 B. 堆排序 C. 归并排序 D. 基数排序
15、希尔排序的增量序列必须是（ ）。
A. 递增的　 B. 递减的 C. 随机的 D. 非递减的

二、填空题
1、在插入和选择排序中，若初始数据基本正序，则选用 ，若初始数据基本反序，则选用 。
答案：递增排列 递减排列
2、在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有 。

三、判断题
1、直接选择排序是一种稳定的排序方法稳定：快速 选择 堆 希尔
。P
2、快速排序在所有排序方法中最快，而且所需附加空间也最少O(log2n)
。O
3、直接插入排序是不稳定的排序方法。O
4、选择排序是一种不稳定的排序方法。

四、程序分析题

五、综合题
1、写出用直接插入排序将关键字序列{54,23,89,48,64,50,25,90,34}排序过程的每一趟结果。
答案：初始： 54，23，89，48，64，50，25，90，34
1：（23，54），89，48，64，50，25，90，34
2：（23，54，89），48，64，50，25，90，34
3：（23，48，54，89），64，50，25，90，34
4：（23，48，54，64，89），50，25，90，34
5：（23，48，50，54，64，89），25，90，34
6：（23，25，48，50，54，64，89），90，34
7：（23，25，48，50，54，64，89，90），34
8：（23，25，48，50，54，64，89，90，34）
2、设待排序序列为{10,18,4,3,6,12,1,9,15,8}请写出希尔排序每一趟的结果。增量序列为5，3，2，1。
答案：初始： 10，18，4，3，6，12，1，9，15，8
d=5： 10，1，4，3，6，12，18，9，15，8
d=3： 3，1，4，8，6，12，10，9，15，18
d=2： 3，1，4，8，6，9，10，12，15，18
d=1： 1，3，4，6，8，9，10，12，15，18
3、已知关键字序列{418，347，289，110，505，333，984，693，177}，按递增排序，求初始堆（画出初始堆的状态）。
答案：418，347，289，110，505，333，984，693，177

4、有一关键字序列（265，301，751，129，937，863，742，694，076，438），写出希尔排序的每趟排序结果。（取增量为5，3，1）
答案：
初始： 265，301，751，129，937，863，742，694，076，438
d=5： 265，301，694，076，438，863，742，751，129，937
d=3： 076，301，129，265，438，694，742，751，863，937
d=1： 076，129，265，301，438，694，742，751，863，937
5、对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：
（1）平均时间复杂度低于O（n2）的排序方法快速 归并 堆 希尔 平均时间复杂度低于o(n2)
；
（2）所需辅助空间最多的排序方法；
答案：(1) 希尔、快速、堆、归并 (2) 归并

6、对关键子序列（72，87，61，23，94，16，05，58）进行堆排序，使之按关键字递减次序排列（最小堆），请写出排序过程中得到的初始堆和前三趟的序列状态。
答案：

习题8
一、单项选择题
1. 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（ ）。
A. j-i B. i-j-1 C. i-j D. i-j+1
2. 若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（ ）。
A. O(1) B. O(n) C. O(n2) D. O(log2n)
3. 在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟。
A. n B. n+1 C. n-1 D. 2n
4. 对n个元素进行直接插入排序时间复杂度为（ ）。
A. O(1) B. O(n) C. O(n2) D. O(log2n)
5. 在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（ ）对相邻元素之间的交换。
A. n B. n-1 C. n+1 D. n/2
6. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（ 冒泡排序和插入排序是一样的 时间复杂度为o(n2),最坏情况是o(n2)，最好情况是o(n)，空间复杂度是o(1)。稳定简单。选择是最好情况与之不同为o(n2) 且选择是不稳定的
）。
A. O(1) B. O(log2n) C. O(n2) D. O(n)
7. 在对n个元素进行冒泡排序的过程中，至少需要（ ）趟完成。
A. 1 B. n C. n-1 D. n/2
8. 在对n个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则整个排序过程得到的含两个或两个元素的区间个数大致为（ ）。
A. n B. n/2 C. log2n D. 2n
9. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素，包括开始把支点元素移动到临时变量的一次在内。
A. n/2 B. n-1 C. n D. n+1
10. 在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）躺快速排序是不稳定 较复杂的 时间复杂度是o(nlog2n)，最好情况是o(nlog2n)，最坏情况是o(n2)，空间复杂度是o(log2n)
。
A. n B. n/2 C. log2n D. 2n
11. 在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）躺。
A. n B. n-1 C. n/2 D. log2n
12. 在对n个元素进行快速排序的过程中，平均情况下的时间复杂度为（ ）。
A. O(1) B. O(log2n) C. O(n2) D. O(nlog2n)
13. 在对n个元素进行快速排序的过程中，最坏情况下的时间复杂度为（ ）。
A. O(1) B. O(l