1、1、交换式排序、交换式排序2、选择式排序、选择式排序3、插入式排序、插入式排序4、归并排序、归并排序5、各种内排方法比较、各种内排方法比较第十一章第十一章 排序排序n排序：排序：将一个数据元素的任意序列，重新将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。排列成一个按关键字有序的序列。n数据表数据表:它是待排序数据对象的有限集合。它是待排序数据对象的有限集合。n主关键字主关键字:数据对象有多个属性域数据对象有多个属性域,即多个即多个数据成员组成数据成员组成,其中有一个属性域可用来区分其中有一个属性域可用来区分对象对象,作为排序依据，称为关键字。也称为排作为排序依据，称为关键字。也称
2、为排序码。序码。n排序方法的稳定性排序方法的稳定性:如果在对象序列中有两如果在对象序列中有两 个对象个对象ri和和rj,它们的关键字它们的关键字ki=kj,且在排序之前且在排序之前,对象对象ri排在排在rj前面。如果在排序之后前面。如果在排序之后,对象对象ri仍仍在对象在对象rj的前面的前面,则称这个排序方法是稳定的则称这个排序方法是稳定的,否否则称这个排序方法是不稳定的。则称这个排序方法是不稳定的。如记录对应关键字序列为：如记录对应关键字序列为：8，7，24，8，19使用某排序算法得到的序列：使用某排序算法得到的序列：7，8，8，19，24则这种排序方法是稳定的则这种排序方法是稳定的使用某排
3、序算法得到的序列：使用某排序算法得到的序列：7，8，8，19，24则这种排序方法是不稳定的则这种排序方法是不稳定的内排序与外排序内排序与外排序:内排序是指在排序期内排序是指在排序期间数据对象全部存放在内存的排序；外间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象数量太大，排序是指在排序期间全部对象数量太大，不能同时存放在内存，必须根据排序过不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的程的要求，不断在内、外存之间移动的排序。排序。排序的时间开销排序的时间开销:排序的时间开销是衡排序的时间开销是衡量算法好坏的最重要的标志。排序的时量算法好坏的最重要的标志。排序的
4、时间开销可用间开销可用算法执行中的数据比较次数算法执行中的数据比较次数与数据移动次数来衡量。与数据移动次数来衡量。通常，在排序的过程中需进行下列通常，在排序的过程中需进行下列两种基本操作两种基本操作：(1)比较两个关键字的大小；比较两个关键字的大小；(2)将记录从一个位置移动至另一个位置。将记录从一个位置移动至另一个位置。待排序的记录序列可有下列待排序的记录序列可有下列三种存储方式三种存储方式：(1)待排序的一组记录存放在地址连续的一组存储单元上。待排序的一组记录存放在地址连续的一组存储单元上。(2)一组待排序记录存放在静态链表中，记录之间的次序关系一组待排序记录存放在静态链表中，记录之间的次
5、序关系由指针指示，则实现排序不需要移动记录，仅需修改指针即可；由指针指示，则实现排序不需要移动记录，仅需修改指针即可；(3)待排序记录本身存储在一组地址连续的存储单元内，同时待排序记录本身存储在一组地址连续的存储单元内，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的移动记录本身，而移动地址向量中这些记录的“地址地址”，在排，在排序结束之后再按照地址向量中的值调整记录的存储位置。序结束之后再按照地址向量中的值调整记录的存储位置。内排序分类内排序分类依不同原则依不同原则交换式排序、选择式排序、
6、插入式排交换式排序、选择式排序、插入式排序、归并排序、基数排序序、归并排序、基数排序。依所须工作量依所须工作量简单排序简单排序-时间复杂度时间复杂度O(n2)先进排序方法先进排序方法-时间复杂度时间复杂度O(n logn)基数排序基数排序-时间复杂度时间复杂度O(d*n)11.2 交换式排序交换式排序 基本思想基本思想:两两比较待排序对象的关键字两两比较待排序对象的关键字,如发生逆序如发生逆序(即排列顺序与排序后的次序正好即排列顺序与排序后的次序正好相反相反)，则交换之，则交换之,直到所有对象都排好序为止。直到所有对象都排好序为止。一、起泡排序一、起泡排序(Bubble Sort)基本方法基本
7、方法：先将第一个记录的关键字和第二个先将第一个记录的关键字和第二个记录的关键字进行比较，如果前者比后者大，则记录的关键字进行比较，如果前者比后者大，则将两个记录交换。然后比较第二个和第三个记录将两个记录交换。然后比较第二个和第三个记录的关键字，依次类推直到第的关键字，依次类推直到第n-1个记录和第个记录和第n个记个记录进行比较交换完，这称为第一趟冒泡。经过一录进行比较交换完，这称为第一趟冒泡。经过一趟冒泡后，关键字最大的记录就被交换到了第趟冒泡后，关键字最大的记录就被交换到了第n个个位置。然后，对前位置。然后，对前n-1个记录进行同样的操作，则个记录进行同样的操作，则关键字是第二大的记录就被交
8、换到了第关键字是第二大的记录就被交换到了第n-1个位置个位置上。重复以上过程，每趟负责排好一个记录，经上。重复以上过程，每趟负责排好一个记录，经过过n-1趟后趟后n个记录中有个记录中有n-1个记录被排好，剩下的个记录被排好，剩下的一个记录不必再排了，至此一个记录不必再排了，至此n个记录全部排好。个记录全部排好。初初始始关关键键字字第第一一趟趟排排序序第第四四趟趟排排序序第第二二趟趟排排序序第第三三趟趟排排序序第第五五趟趟排排序序起泡排序的过程起泡排序的过程n最坏的情形是算法执行最坏的情形是算法执行n-1趟起泡趟起泡,第第i趟趟(1 i n)做做 n-i 次关键字比较次关键字比较,执行执行 n-
9、i 次对象次对象交换。这样在最坏情形下总的关键字比较次交换。这样在最坏情形下总的关键字比较次数数KCN和交换次数和交换次数RMN为：为：1111123121nininninRMNnninKCN)()(3)()(n起泡排序是一个稳定的排序方法。起泡排序是一个稳定的排序方法。n时间复杂度为时间复杂度为O(n2)。二、快速排序二、快速排序(Quick Sort)n基本思想基本思想:是任取待排序对象序列中的某是任取待排序对象序列中的某个对象个对象(例如取第一个对象例如取第一个对象)作为基准作为基准,按照按照该对象的关键字大小该对象的关键字大小,将整个对象序列划分将整个对象序列划分为左右两个子序列：为左
10、右两个子序列：u左侧子序列中所有对象的关键字都小于基左侧子序列中所有对象的关键字都小于基准对象的关键字准对象的关键字u右侧子序列中所有对象的关键字都大于基右侧子序列中所有对象的关键字都大于基准对象的关键字准对象的关键字n基准对象则排在这两个子序列中间基准对象则排在这两个子序列中间(这也是这也是该对象最终应安放的位置该对象最终应安放的位置)。n然后分别对这两个子序列重复施行上述方然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为法，直到所有的对象都排在相应位置上为止。止。n基准对象也称为枢轴（或支点）记录。基准对象也称为枢轴（或支点）记录。一趟快速排序的具体做法是：一趟快速
11、排序的具体做法是：设两个指针设两个指针low和和high，设枢轴记录的关键，设枢轴记录的关键字为字为key。首先从首先从high所指位置起所指位置起向前搜索找到第一个向前搜索找到第一个关键字小于关键字小于key的记录的记录，使，使high和和key的值交的值交换。换。再移动到再移动到low所在位置，然后从所在位置，然后从low所指位置所指位置起向后搜索，起向后搜索，找到第一个关键字大于找到第一个关键字大于key的的记录移动记录移动到到high所指位置，使所指位置，使low和和key的值的值交换。交换。重复这两步直至重复这两步直至low=high为止。为止。快速排序的过程快速排序的过程key初始
12、关键字初始关键字lowhigh21一次交换一次交换lowhigh21二次交换二次交换highlow21三次交换三次交换lowhigh21四次交换四次交换highlow完成一趟排序完成一趟排序lowhigh完成一趟排序完成一趟排序分别进行快速排序分别进行快速排序有序序列有序序列 算法实现过程中，先将基准记录保存在算法实现过程中，先将基准记录保存在r0位置上，排序过程中只作位置上，排序过程中只作rlow或或rhigh记录的移动，待一趟排序结束后记录的移动，待一趟排序结束后再将基准记录移至正确位置上。再将基准记录移至正确位置上。void quick_sort(int num,int s,int t)
13、int i,j;i=s;j=t;num0=nums;while(ii&num0numj)j-;if(ij)numi=numj;i+;while(ij&numi=num0)i+;if(ij)numj=numi;j-;numi=num0;if(si)quick_sort(num,s,j-1);if(it)quick_sort(num,j+1,t);n可以证明可以证明,函数函数quick_sort的平均时间复杂的平均时间复杂度是度是O(nlog2n)。实验结果表明。实验结果表明:就平均计算就平均计算时间而言时间而言,快速排序是所有内排序方法中最快速排序是所有内排序方法中最好的一个。好的一个。n快速排
14、序是递归的。快速排序是递归的。n快速排序是一种不稳定的排序方法。快速排序是一种不稳定的排序方法。n最佳状况时间复杂度是最佳状况时间复杂度是O(nlog2n)n最坏状况时间复杂度是最坏状况时间复杂度是O(n2)基本思想基本思想:每一趟每一趟(例如第例如第 i 趟趟,i=0,1,n-2)在后面在后面 n-i 个待排序记录中选出关键字最个待排序记录中选出关键字最小的记录小的记录,作为有序序列中的第作为有序序列中的第 i 个记录。待个记录。待到第到第n-2 趟做完趟做完,待排序记录只剩下待排序记录只剩下1个个,就不就不用再选了。用再选了。11.3 选择排序选择排序 直接选择排序是一种简单的排序方法直接
15、选择排序是一种简单的排序方法,它的它的基本步骤是：基本步骤是：在一组对象在一组对象 ViVn-1 中选择具有最中选择具有最小关键字的对象；小关键字的对象；若它不是这组对象中的第一个对象若它不是这组对象中的第一个对象,则将则将它与这组对象中的第一个对象对调它与这组对象中的第一个对象对调;在剩下的对象在剩下的对象Vi+1Vn-1中重复执行中重复执行第第、步步,直到剩余对象只有一个为止。直到剩余对象只有一个为止。一、选择排序一、选择排序直接选择排序直接选择排序0 1 2 3 4 5最小者最小者最小者最小者最小者最小者 直接选择排序的过程直接选择排序的过程最小者最小者0 1 2 3 4 5最小者最小者
16、各趟排序后的结果各趟排序后的结果n直接选择排序的排序比较次数与对象的初始排列直接选择排序的排序比较次数与对象的初始排列无关。设整个待排序对象序列有无关。设整个待排序对象序列有 n 个对象个对象,则第则第 i 趟选择具有最小排序码对象所需的比较次数总趟选择具有最小排序码对象所需的比较次数总是是 n-i-1 次。总的排序码比较次数为次。总的排序码比较次数为20211ninninKCN)()(n对象的移动次数与对象序列的初始排列有关。当对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其排序码从小到大有序这组对象的初始状态是按其排序码从小到大有序的时候的时候,对象的移动次数为对象的移动
17、次数为0，达到最少。，达到最少。n最坏情况是每一趟都要进行交换，总的对象移动最坏情况是每一趟都要进行交换，总的对象移动次数为次数为 3(n-1)。n直接选择排序是一种不稳定的排序方法。直接选择排序是一种不稳定的排序方法。二、堆排序二、堆排序 堆的定义：堆的定义：n个元素的序列个元素的序列(k1,k2,kn)，当且仅当，当且仅当满足下列关系时，称之为堆满足下列关系时，称之为堆或或(i=1,2,.n/2)ki k2iki k2i+1ki k2iki k2i+1例例 （96,83,27,38,11,9）例例 （13,38,27,50,76,65,49,97）962791138831327384965
18、765097可将堆序列看成完全二叉树，则可将堆序列看成完全二叉树，则堆顶元素堆顶元素（完全二叉（完全二叉树的根）树的根）必为序列中必为序列中n个元素的最小值或最大值个元素的最小值或最大值 堆排序：将无序序列建成一个堆，得到关键字最小堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，（或最大）的记录；输出堆顶的最小（大）值后，使剩余的使剩余的n-1个元素重又建成一个堆，则可得到个元素重又建成一个堆，则可得到n个个元素的次小值；重复执行，得到一个有序序列，这元素的次小值；重复执行，得到一个有序序列，这个过程叫个过程叫 堆排序需解决的两个问题：堆排序需解决的两个
19、问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？之成为一个新的堆？第二个问题解决方法第二个问题解决方法筛选筛选 方法：方法：输出堆顶元素之后，以堆中最后一个元输出堆顶元素之后，以堆中最后一个元素替代之素替代之；然后将根结点值与左、右子树的根然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换结点值进行比较，并与其中小者进行交换；重；重复上述操作，直至叶子结点，将得到新的堆，复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为称这个从堆顶至叶子的调整
20、过程为“筛选筛选”13273849657650979727384965765013输出：输出：132749389765765013输出：输出：139749382765765013输出：输出：13 273849502765769713输出：输出：13 276549502738769713输出：输出：13 27 384965502738769713输出：输出：13 27 387665502738499713输出：输出：13 27 38 495065762738499713输出：输出：13 27 38 499765762738495013输出输出13 27 38 49 506597762738495
21、013输出输出13 27 38 49 509765762738495013输出：输出：13 27 38 49 50 657665972738495013输出：输出：13 27 38 49 50 659765762738495013输出：输出：13 27 38 49 50 65 769765762738495013输出：输出：13 27 38 49 50 65 76 97第一个问题解决方法第一个问题解决方法方法：从无序序列的第方法：从无序序列的第 n/2 个元素个元素（即此无序序列对应的完全二叉树的最（即此无序序列对应的完全二叉树的最后一个非后一个非叶子叶子结点）起，至第一个元素结点）起，至第一
22、个元素止，进行反复筛选止，进行反复筛选含含8个元素的无序序列（个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097算法性能分析：算法性能分析：堆排序适用于记录数较多的文件，它所堆排序适用于记录数较多的文件，它所需要的辅助空间比较少，空间复杂度为需要的辅助空间比较少，空间复杂度为O（1）。）。因为堆是个树形的结构，所以时间复杂因为堆是个树形的结构，所以时间复杂度与树的高度有关系，在最坏的情况下度与树的高度有关系，在最坏的情况
23、下时间复杂度为时间复杂度为O（nlog2n)。堆排序是一种不稳定的排序方法。堆排序是一种不稳定的排序方法。11.4 插入排序插入排序(Insert Sorting)基本思想：每步将一个待排序的对象基本思想：每步将一个待排序的对象,按其关按其关键字大小键字大小,插入到前面已经排好序的一组对插入到前面已经排好序的一组对象的适当位置上象的适当位置上,直到对象全部插入为止。直到对象全部插入为止。排序过程：整个排序过程为排序过程：整个排序过程为n-1趟插入，即先趟插入，即先将序列中第将序列中第1个记录看成是一个有序子序列，个记录看成是一个有序子序列，然后从第然后从第2个记录开始，逐个进行插入，直至个记录
24、开始，逐个进行插入，直至整个序列有序整个序列有序例如：打扑克时，边抓牌，边码牌。例如：打扑克时，边抓牌，边码牌。n基本思想基本思想：当插入第当插入第i(i 1)个对象时个对象时,前面前面的的V0,V1,Vi-1已经排好序。这时已经排好序。这时,用用Vi的关键字与的关键字与Vi-1,Vi-2,的关键字的关键字顺序进行比较顺序进行比较,找到插入位置即将找到插入位置即将Vi插入插入,原来位置上的对象向后顺移。原来位置上的对象向后顺移。一、直接插入排序一、直接插入排序(Insert Sort)直接插入直接插入排序过程排序过程0 1 2 3 4 5 6i=249i=325*0 1 2 3 4 5 6 i
25、=125排序前排序前排序后排序后监视哨监视哨i=508i=4161616160 1 2 3 4 5 6 49 38 65 97 76 13 27i=2 38 (38 49)65 97 76 13 27i=3 65 (38 49 65)97 76 13 27i=4 97 (38 49 65 97)76 13 27i=5 76 (38 49 65 76 97)13 27i=6 13 (13 38 49 65 76 97)27i=1 ()i=7 (13 38 49 65 76 97)2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：排序结果：void
26、 insert_sort(int r,int n)int i,j;for(i=2;i=n;i+)r0=ri;j=i-1;while(r0rj)rj+1=rj;j-;rj+1=r0;算法分析算法分析n设待排序对象个数为设待排序对象个数为 n,则该算法的主程序则该算法的主程序执行执行n-1趟。趟。n关键字比较次数和对象移动次数与对象关关键字比较次数和对象移动次数与对象关键字的初始排列有关。键字的初始排列有关。n最好情况下最好情况下,排序前对象已按关键字从小排序前对象已按关键字从小到大有序到大有序,每趟只需与前面有序对象序列每趟只需与前面有序对象序列的最后一个对象比较的最后一个对象比较1次次,总的关
27、键字比较总的关键字比较次数为次数为 n-1,不需移动记录。不需移动记录。n最坏情况下最坏情况下,待排记录按关键字非递增有序待排记录按关键字非递增有序排列（逆序）时，第排列（逆序）时，第i趟时第趟时第i+1个对象必个对象必须与前面须与前面 i 个对象都做关键字比较个对象都做关键字比较,并且每并且每做做1次比较就要做次比较就要做1次数据移动。总比较次次数据移动。总比较次数为数为(n+2)(n-1)/2次，总移动次数为次，总移动次数为(n+4)(n-1)/2。n在平均情况下的关键字比较次数和对象移在平均情况下的关键字比较次数和对象移动次数约为动次数约为 n2/4。因此，直接插入排序的。因此，直接插入
28、排序的时间复杂度为时间复杂度为 O(n2)。n直接插入排序是一种稳定的排序方法。直接插入排序是一种稳定的排序方法。基本思想：基本思想：当待排记录数当待排记录数n很小时，直接插入排序的很小时，直接插入排序的效率较高。效率较高。当待排序列按关键字基本有序时直接插入当待排序列按关键字基本有序时直接插入排序的效率也较高。排序的效率也较高。所以从这两点出发可对直接插入排序改所以从这两点出发可对直接插入排序改进，先将整个待排记录序列分割成为若进，先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体个序列中的记录基本有序时，再对
29、全体记录进行一次直接插入排序。记录进行一次直接插入排序。二、希尔排序二、希尔排序(Shell Sort)（缩小增量排序）（缩小增量排序）n设待排序对象序列有设待排序对象序列有 n 个对象个对象,首先取一个首先取一个整数整数 gap=1)for(i=d+1;i0&r0rj)rj+d=rj;j=j-d;rj+d=r0;d=d/2;n开始时开始时 gap 的值较大的值较大,子序列中的对象较少子序列中的对象较少,排序速排序速度较快度较快;随着排序进展随着排序进展,gap 值逐渐变小值逐渐变小,子序列中子序列中对象个数逐渐变多对象个数逐渐变多,由于前面大多数对象已基本有序由于前面大多数对象已基本有序,所
30、以排序速度仍然很快。所以排序速度仍然很快。ngap的取法有多种。的取法有多种。shell 提出取提出取 gap=n/2，gap=gap/2，直到，直到gap=1。n对特定的待排序对象序列，可以准确地估算排序码的对特定的待排序对象序列，可以准确地估算排序码的比较次数和对象移动次数。比较次数和对象移动次数。n希尔排序所需的比较次数和移动次数约为希尔排序所需的比较次数和移动次数约为n 1.3一般认为，希尔排序的时间复杂度是一般认为，希尔排序的时间复杂度是O(nlog2 n)n希尔排序是一种不稳定的排序方法希尔排序是一种不稳定的排序方法11.5 归并排序归并排序(Merge Sort)n归并归并将两个
31、或两个以上的有序表合并成一个将两个或两个以上的有序表合并成一个新的有序表。新的有序表。n两路归并两路归并(2-way merging)原始序列原始序列initList 中两个有序表中两个有序表 initListl initListm和和initListm+1 initListn，它们可归并成一个有序表它们可归并成一个有序表,存于另一对象序存于另一对象序列列mergedList的的 l n 中。中。迭代的归并排序算法迭代的归并排序算法n迭代的归并排序算法就是利用两路归并过程迭代的归并排序算法就是利用两路归并过程进行排序的。其基本思想是：进行排序的。其基本思想是：假设初始对象序列有假设初始对象序列
32、有 n 个对象，首先把它看个对象，首先把它看成是成是 n 个长度为个长度为 1 的有序子序列的有序子序列(归并项归并项)，先做两两归并，得到先做两两归并，得到 n/2 个长度为个长度为 2 的归的归并项并项(如果如果 n 为奇数，则最后一个有序子序为奇数，则最后一个有序子序列的长度为列的长度为1)；再做两两归并，；再做两两归并，如此重，如此重复，最后得到一个长度为复，最后得到一个长度为 n 的有序序列。的有序序列。n在迭代的归并排序算法中在迭代的归并排序算法中,函数函数MergePass()做一趟两路归并排序做一趟两路归并排序,要调用要调用merge()函数函数 n/(2*len)O(n/le
33、n)次次,函数函数MergeSort()调用调用MergePass()正好正好 log2n 次次,而每次而每次merge()要执行比较要执行比较O(len)次次,所以算法总的所以算法总的时间复杂度为时间复杂度为O(nlog2n)。n归并排序占用附加存储较多归并排序占用附加存储较多,需要另外一个与需要另外一个与原待排序对象数组同样大小的辅助数组。这原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。是这个算法的缺点。n归并排序是一个稳定的排序方法。归并排序是一个稳定的排序方法。各种内部排序方法比较各种内部排序方法比较排序方法排序方法 最好时间最好时间 最坏时间最坏时间 平均时间平均时间 辅助
34、空间辅助空间稳定性稳定性直接插入直接插入O(n)O(n2)O(n2)O(1)稳定稳定直接选择直接选择O(n2)O(n2)O(n2)O(1)不稳定不稳定冒泡排序冒泡排序O(n2)O(n2)O(n2)O(1)稳定稳定希尔排序希尔排序-O(1)不稳定不稳定快速排序快速排序 O(nlog2n)O(n2)O(nlog2n)O(log2n)不稳定不稳定堆排序堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定不稳定归并排序归并排序 O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定稳定本 章 小 结本 章 小 结1.掌握排序的概念掌握排序的概念2.掌握交换式排序算法及
35、其性能分析掌握交换式排序算法及其性能分析3.3.掌握选择式排序算法及其性能分析掌握选择式排序算法及其性能分析4.4.掌握插入式排序算法及其性能分析掌握插入式排序算法及其性能分析5.掌握归并排序算法。掌握归并排序算法。1、没有任何一种通过比较元素重排序列的排序算法在、没有任何一种通过比较元素重排序列的排序算法在最坏情形下，时间复杂度好于最坏情形下，时间复杂度好于O（nlogn）()2、快速排序的速度在所有排序方法中为最快，而且所、快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。需附加空间也最少。()3、最大堆中的每个结点是以之为根的子树包含的结点、最大堆中的每个结点是以之为根的子树
36、包含的结点中，值最大的结点。中，值最大的结点。()4、对于一个堆，按二叉树的层次进行遍历可以得到一、对于一个堆，按二叉树的层次进行遍历可以得到一个有序序列。个有序序列。()5、（、（101，88，46，70，34，39，45，58，66，10）是堆。是堆。()6、归并排序所需的附加空间最多、归并排序所需的附加空间最多()XX7、用希尔方法排序时，若关键字的初始序列杂乱无、用希尔方法排序时，若关键字的初始序列杂乱无序，则排序效率就低。序，则排序效率就低。()8、下列算法中，（、下列算法中，（）算法可能出现下列情况：在）算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置最后一趟
37、开始之前，所有的元素都不在其最终的位置上。上。A.堆排序堆排序 B.冒泡排序冒泡排序 C.插入排序插入排序 D.快速排序快速排序9、排序的趟数与序列的原始状态有关的排序方法是、排序的趟数与序列的原始状态有关的排序方法是（）A.插入排序插入排序B.选择排序选择排序C.冒泡排序冒泡排序D.快速排序快速排序10、若需在、若需在O（nlog2n）的时间内完成排序，且要求）的时间内完成排序，且要求稳定，则可选择（稳定，则可选择（）A.快速排序快速排序 B.堆排序堆排序 C.归并排序归并排序 D.直接插入排序直接插入排序XCDC11、一组记录的关键字为、一组记录的关键字为45，80，55，40，42，85
38、，则利用堆排序方法建立的初始堆为（，则利用堆排序方法建立的初始堆为（）A.80,45,50,40,42,85 B.85,80,55,40,42,45C.85,80,55,45,42,40 D.85,55,80,42,45,4012、在待排序的元素序列基本有序的前提下，效率最、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（高的排序方法是（）A.插入排序插入排序 B.选择排序选择排序 C.快速排序快速排序 D.归并排序归并排序13、快速排序在（、快速排序在（）情况下不利于发挥其长处）情况下不利于发挥其长处A.待排序数据量太大待排序数据量太大 B.待排序数据相同值过多待排序数据相同值过多
39、C.待排序数据已基本有序待排序数据已基本有序 D.待排序数据值差过大待排序数据值差过大BAC14、设有字符序列、设有字符序列Q、H、C、Y、P、A、M、S、R、D、F、X，新序列为，新序列为D、H、C、F、P、A、M、Q、R、X、Y、X是下列（是下列（）排序算法的一趟扫描结果）排序算法的一趟扫描结果A.冒泡排序冒泡排序 B.初始步长为初始步长为4的希尔排序的希尔排序C.二路归并排序二路归并排序D.以第一个元素为分界元素的快速排序以第一个元素为分界元素的快速排序15、向一个有、向一个有127个有序元素的顺序表中插入一个新元个有序元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（素并保持原来顺序不变，平均要移动（）个元素）个元素A.8 B.63.5 C.63 D.7DB
