第八章排序new

1、一、教学内容：一、教学内容：1 1、插入排序（直接插入排序、折半插入排序、希尔排序）；、插入排序（直接插入排序、折半插入排序、希尔排序）；2 2、交换排序（起泡排序、快速排序）；、交换排序（起泡排序、快速排序）；3 3、选择排序（直接选择排序、堆排序）；、选择排序（直接选择排序、堆排序）；4 4、归并排序；、归并排序；5 5、基数排序；、基数排序；二、教学要求：二、教学要求：1 1、掌握排序的基本概念和各种排序方法的特点，并能加以、掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；灵活应用；2 2、掌握插入排序、交换排序、选择排序、归并排序的方法、掌握插入排序、交换排序、选择排序、归并

2、排序的方法及其性能分析方法；及其性能分析方法；3 3、了解基数排序方法及其性能分析方法。、了解基数排序方法及其性能分析方法。8.1 8.1 概述概述8.2 8.2 插入排序插入排序8.3 8.3 交换排序交换排序8.4 8.4 选择排序选择排序8.5 8.5 归并排序归并排序 将一组杂乱无章的将一组杂乱无章的按一定的按一定的顺次排列起来。顺次排列起来。定义：设有记录序列：定义：设有记录序列： R1 R1、R2 . Rn R2 . Rn 其相应的关键字序列为：其相应的关键字序列为： K1 K1、K2 .Kn ; K2 .Kn ; 若存在一种确定的关系：若存在一种确定的关系： Kx = Ky =

3、= Kz Kx = Ky = = Kz则将则将记录序列记录序列 R1 R1、R2 . Rn R2 . Rn 排成按该关排成按该关键字有序的序列：键字有序的序列： Rx Rx、Ry . Rz Ry . Rz 的的操作，称之为排序。操作，称之为排序。 便于查找！便于查找！若待排序记录都在内存中，称为内部排序；若待排序记录都在内存中，称为内部排序；若待排序记录一部分在内存，一部分在外存，则若待排序记录一部分在内存，一部分在外存，则称为外部排序。称为外部排序。注：注：外部排序时，要将数据分批调入内存来排序，中间外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。结

4、果还要及时放入外存，显然外部排序要复杂得多。 大多数排序算法都有两个基本的操作：大多数排序算法都有两个基本的操作：（1）比较两个关键字的大小）比较两个关键字的大小（2）将记录从一个位置移动到另一个位置）将记录从一个位置移动到另一个位置记录序列的存储方式：记录序列的存储方式：（1）顺序存储顺序存储 （2）静态链表）静态链表 （3）地址）地址注：注：大多数排序算法都是针对顺序表结构的大多数排序算法都是针对顺序表结构的( (便于直接移动元素便于直接移动元素) )Typedef struct /定义每个记录（数据元素）的结构定义每个记录（数据元素）的结构 KeyType key ; /关键字关键字 I

5、nfoType otherinfo; /其它数据项其它数据项RecordType ;Typedef struct /定义顺序表的结构定义顺序表的结构 RecordType r MAXSIZE +1 ; /存储顺序表的向量存储顺序表的向量 /r0/r0一般作哨兵或缓冲区一般作哨兵或缓冲区 int length ; /顺序表的长度顺序表的长度SqList ;# define MAXSIZE 20 /设记录不超过设记录不超过2020个个typedef int KeyType ; /设关键字为整型量（设关键字为整型量（intint型）型）按排序的规则不同，可分为按排序的规则不同，可分为5类：类：插入排

6、序插入排序交换排序（重点是快速排序）交换排序（重点是快速排序）选择排序选择排序归并排序归并排序基数排序基数排序d关键字的位数关键字的位数(长度长度)按排序算法的时间复杂度不同，可分为按排序算法的时间复杂度不同，可分为3类：类：简单的排序算法：时间效率低，简单的排序算法：时间效率低，O(n2)先进的排序算法先进的排序算法: 时间效率高，时间效率高，O( nlog2n )基数排序算算法：时间效率高，基数排序算算法：时间效率高，O( dn)插入排序有多种具体实现算法：插入排序有多种具体实现算法： 1) 直接插入排序直接插入排序 2) 折半插入排序折半插入排序 3) 希尔排序希尔排序插入到前面插入到前

7、面的的上上新元素插入到哪里？新元素插入到哪里？例例1 1：关键字序列关键字序列T=（13，6，3，31，9，27，5，11），）， 请写出直接插入排序的中间过程序列。请写出直接插入排序的中间过程序列。【13】, 6, 3, 31, 9, 27, 5, 11【6, 13】, 3, 31, 9, 27, 5, 11【3, 6, 13】, 31, 9, 27, 5, 11【3, 6, 13，31】, 9, 27, 5, 11【3, 6, 9, 13，31】, 27, 5, 11【3, 6, 9, 13，27, 31】, 5, 11【3, 5, 6, 9, 13，27, 31】, 11【3, 5, 6

8、, 9, 11，13，27, 31】 在已形成的在已形成的有序表中有序表中线性查找线性查找，并在，并在适当位置插入，把原来位置上的元素向后适当位置插入，把原来位置上的元素向后顺移顺移。* *表示后一个表示后一个25250 1 2 3 4 5 6254925*1608解：解：假设该序列已存入一维数组假设该序列已存入一维数组V7V7中，将中，将V0V0作为缓冲或作为缓冲或暂存单元（暂存单元（TempTemp）。则程序执行过程为：）。则程序执行过程为：初态：初态：直接插入排序的演示直接插入排序的演示void Insertsort(SqList void Insertsort(SqList * *l)

9、l) int i,j; int i,j; for(i=2;ilength;i+) for(i=2;ilength;i+) l-r0=l-ri; l-r0=l-ri; j=i-1; j=i-1; while(l-r0.keyrj.key) while(l-r0.keyrj.key) l-rj+1=l-rj; l-rj+1=l-rj; j-; j-; l-rj+1=l-r0; l-rj+1=l-r0; 111122142221nininnniRMNnnniKCN/)()( ,/)(22比较的次数大大减少，全部元素比较次数仅为比较的次数大大减少，全部元素比较次数仅为O(nlogO(nlog2 2n)

10、n)。虽然比较次数大大减少，可惜移动次数并未减少，虽然比较次数大大减少，可惜移动次数并未减少，所以排序效率仍为所以排序效率仍为O(nO(n2 2) ) 。 O O（1 1）稳定稳定 在已形成的在已形成的，并在适当位置插入，把，并在适当位置插入，把原来位置上的元素向后原来位置上的元素向后。void binsort(SqList void binsort(SqList * *L)L) int i,j, s,m,k; int i,j, s,m,k; KeyType x; KeyType x; for(i=2;ilength;i+) for(i=2;ilength;i+) L-r0=L-ri; L-r

11、0=L-ri; x=L-ri.key; x=L-ri.key; s=1; j=i-1;s=1; j=i-1; while(s=j) while(s=j) m=(s+j)/2; m=(s+j)/2; if(xrm.key) if(xrm.key) j=m-1;j=m-1; else s=m+1;else s=m+1; for(k=i-1;k=s;k-)for(k=i-1;k=s;k-) L-rk+1=L-rk; L-rk+1=L-rk; L-rs=L-r0; L-rs=L-r0; 讨论：讨论：若记录是链表结构，用直接插入排序行否？折半插入若记录是链表结构，用直接插入排序行否？折半插入排序呢？排序

12、呢？答：答：直接插入不仅可行，而且还无需移动元素，时间效率更直接插入不仅可行，而且还无需移动元素，时间效率更高！高！380123456789 1049 38 65 97 76 13 27 49*55 044913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 开始时开始时dk 的值较大，子序列中的对象较少，排序速度的值较大，子序列中的对象较少，排序速度较快；随着排序进展，较快；随着排序进展，dk

13、值逐渐变小，子序列中对象个数值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。所以排序速度仍然很快。空间效率：空间效率：因为仅占用因为仅占用1 1个缓冲单元个缓冲单元算法的稳定性：算法的稳定性：因为因为4949* *排序后却到了排序后却到了4949的前面的前面参见教材参见教材P167P167经验公式经验公式希尔排序的演示希尔排序的演示1. 欲将序列（欲将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按）中的关键码按字母升序重排，则初始步长为字母升序重排

14、，则初始步长为4的希尔排序一趟的结果是？的希尔排序一趟的结果是？答：答：原始序列：原始序列： Q, H, C, Y, P, A, M, S, R, D, F, X shellshell一趟后：一趟后：2. 以关键字序列（以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，分别写出执行以下算法的）为例，分别写出执行以下算法的各趟各趟排序结束时，关排序结束时，关键字序列的状态，并说明这些排序方法中，哪些易于在链表（包键字序列的状态，并说明这些排序方法中，哪些易于在链表（包括各种单、双、循环链表）上实现？括各种单、双、循环链表）上实现？ 直接插入排序直

15、接插入排序 希尔排序（取希尔排序（取dk=5,3,1）P,Q,R,A,D,H,C,F,M,S,X ,Y答：答：显然，直接插入排序方法易于在链表上实现；但希尔排显然，直接插入排序方法易于在链表上实现；但希尔排序方法因为是按增量选择记录，不易于在链表上实现。序方法因为是按增量选择记录，不易于在链表上实现。 两种排序方法的中间状态分别描述如后：两种排序方法的中间状态分别描述如后： 256256，301301 ，751751，129129，937937，863863，742742，694694，076076，438438 256256，301301，751751 ，129129，937937，8638

16、63，742742，694694，076076，438438 129129，256256，301301，751751 ，937937，863863，742742，694694，076076，438438 129129，256256，301301，751751，937937 ，863863，742742，694694，076076，438438 129129，256256，301301，751751，863863，937937 ，742742，694694，076076，438438 129129，256256，301301，742742，751751，863863，937937 ，694694

17、，076076，438438 129129，256256，301301，694694，742742，751751，863863，937937 ，076076，438438 076076，129129，256256，301301，694694，742742，751751，863863，937937 ，438438 076076，129129，256256，301301，438438，694694，742742，751751，863863，937937 第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第第6趟趟第第7趟趟第第8趟趟第第9趟趟256256，301301，751751，129129，

18、937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，937937，863863，742742，751751，076076，438438256256，301301，694694，076076，937937，863863，742742，751751，129129，438438256256，301301，694694，076076，438438，863863，742742，751

19、751，129129，937937第第1趟趟dk=5dk=5第第2趟趟dk=3dk=3第第3趟趟dk=1dk=1256256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，694694，076076，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，86

20、3863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，86386

21、3，937937076076，129129，256256，301301，438438，694694，742742，751751，863863，937937交换排序的主要算法有：交换排序的主要算法有： 1) 冒泡排序冒泡排序 2) 快速排序快速排序基本思路：基本思路：每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。）规则交换。优点：优点：每趟结束时，不仅能挤出一个最大值到最后面位置，每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前

22、结束排序。生，还可以提前结束排序。前提：前提：顺序存储结构顺序存储结构 例：例：关键字序列关键字序列 T=(21，25，49，25*，16，08），请写出），请写出冒泡排序的具体实现过程。冒泡排序的具体实现过程。21，25，49， 25*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，49初态：初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟冒泡排序的演示冒泡排序的演示详细分析：详细分析：最好情况：最好情况：初始排列

23、已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做 n- -1 次关键码比较，不移动对象。次关键码比较，不移动对象。最坏情形：最坏情形：初始排列逆序，初始排列逆序，算法要执行算法要执行n-1 1趟起泡，第趟起泡，第i趟趟(1 i n) 做了做了n- i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换。次对象交换。此时的比较总次数此时的比较总次数KCN和记录移动次数和记录移动次数RMN为：为：11111233121nininninRMNnninKCN)()()()(void bubble_sort(SqList void bubble_sort(SqList * *L)

24、L) int m,i,j,flag=1; int m,i,j,flag=1; RecordType x; RecordType x; m=n-1; m=n-1; while(m0)&(flag=1) while(m0)&(flag=1) flag=0; flag=0; for(j=1;j=m;j+) for(j=1;jrj.keyL-rj+1.key)if(L-rj.keyL-rj+1.key) flag=1; flag=1; x=L-rj; x=L-rj; L-rj=L-rj+1; L-rj=L-rj+1; L-rj+1=x; L-rj+1=x; m-; m-; ( )，设以首元素为枢轴中心

25、设以首元素为枢轴中心21， 25， 49， 25*，16， 08初态：初态：第第1趟：趟：第第2趟：趟：第第3趟：趟：08，16，21，25， 25*，(49)2116，08，( )25，25*，49(08)，16，21，25，(25*，49)快速排序的演示快速排序的演示编程时：编程时：每一趟的子表的形成是采用从两头向中间交替式逼近法；每一趟的子表的形成是采用从两头向中间交替式逼近法；由于每趟中对各子表的操作都相似，主程序可采用递归算法。由于每趟中对各子表的操作都相似，主程序可采用递归算法。int int (SqList &L,(SqList &L,int lowint low, ,int h

26、ighint high) ) /一趟快排一趟快排/交换子表交换子表 rlowhighrlowhigh的记录，使支点（枢轴）记录到位，并返回其位置。的记录，使支点（枢轴）记录到位，并返回其位置。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。 r0=r0=rlowrlow; ; /以子表的首记录作为支点记录，放入以子表的首记录作为支点记录，放入r0r0单元单元（续下页）（续下页）一趟快速排序算法一趟快速排序算法（针对一个子表的操作）（针对一个子表的操作）pivotkey=pivotkey=rlow.keyrlow.key

27、; ; /取支点的关键码存入取支点的关键码存入pivotkeypivotkey变量变量while(low high)while(low high) /从表的两端交替地向中间扫描从表的两端交替地向中间扫描while(while(lowhighlow=pivotkeyrhigh.key=pivotkey ) ) rlow=rhigh; rlow=rhigh; /将比支点小的记录交换到低端；将比支点小的记录交换到低端；while(while(lowhighlowhigh & & rlow.key=pivotkeyrlow.key=pivotkey) ) rhigh=rlow; rhigh=rlow;

28、 /将比支点大的记录交换到高端；将比支点大的记录交换到高端；rlow=r0; rlow=r0; /支点记录到位；支点记录到位；return low; return low; /返回支点记录所在位置。返回支点记录所在位置。 /ri0123456初态初态21254925*1608第第1趟趟highhighlowlow210825164925*321pivotkey=pivotkey=212108251649( 08 ，16 ） 21 （ 25* ， 49， 25 ）void QSort ( SqList &L, int low, int high ) if ( low 1/对顺序表对顺序表L中的子

29、序列中的子序列r lowhigh 作快速排序作快速排序/一趟快排，将一趟快排，将r 一分为二一分为二/在左子区间进行递归快排，直到长度为在左子区间进行递归快排，直到长度为1/在右子区间进行递归快排，直到长度为在右子区间进行递归快排，直到长度为1/QSort新的新的low 1, L.length 原始序列：原始序列： 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438第第1趟趟第第2趟趟第第3趟趟第第4趟趟256256，301301，751751，129129，937937，863863，742742，694

30、694，076076，438438，129129，937937，863863，742742，694694，301301，438438要求模拟算法实现步骤要求模拟算法实现步骤076076301301129129751751，129129，438438，301301，694694，742742，694694，863863，937937，301301，694694，742742，937937，301301，301301，694694，742742，937937，742742，快速排序是递归的，需要有一个栈存放每层递归调用时的指快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数针和参数（新的

31、（新的lowlow和和highhigh）。可以证明，函数可以证明，函数quicksort的平均计算时间也是的平均计算时间也是O(nlog2n)。实实验结果表明：就平均计算时间而言，快速排序是我们所讨论的验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个所有内排序方法中最好的一个。最大递归调用层次数与递归树的深度一致，理想情况为最大递归调用层次数与递归树的深度一致，理想情况为 log2(n+1) 。因此，要求存储开销为。因此，要求存储开销为 o(log2n)。如果每次划分对一个对象定位后，该对象的左侧子序列与右如果每次划分对一个对象定位后，该对象的左侧子序列与右侧子

32、序列的长度相同，则下一步将是对两个长度减半的子序列侧子序列的长度相同，则下一步将是对两个长度减半的子序列进行排序，这是最理想的情况。此时，快速排序的趟数最少。进行排序，这是最理想的情况。此时，快速排序的趟数最少。 在最坏的情况，即待排序对象序列已经按其关键码从小在最坏的情况，即待排序对象序列已经按其关键码从小到大排好序的情况下，到大排好序的情况下，其递归树成为单支树其递归树成为单支树，每次划分只，每次划分只得到一个比上一次少一个对象的子序列。这样，必须经过得到一个比上一次少一个对象的子序列。这样，必须经过 n-1 趟才能把所有对象定位，而且第趟才能把所有对象定位，而且第 i 趟需要经过趟需要经

33、过 n-i 次关键码比较才能找到第次关键码比较才能找到第 i 个对象的安放位置，总的关键个对象的安放位置，总的关键码比较次数将达到码比较次数将达到n n2 2/2/2 快速排序是一个快速排序是一个不稳定不稳定的排序方法。的排序方法。设每个子表的支点都在中间（比较均衡），则：设每个子表的支点都在中间（比较均衡），则：第第1 1趟比较，可以确定趟比较，可以确定1 1个元素的位置；个元素的位置；第第2 2趟比较（趟比较（2 2个子表），可以再确定个子表），可以再确定2 2个元素的位置；个元素的位置；第第3 3趟比较（趟比较（4 4个子表），可以再确定个子表），可以再确定4 4个元素的位置；个元素的位

34、置；第第4 4趟比较（趟比较（8 8个子表），可以再确定个子表），可以再确定8 8个元素的位置；个元素的位置； 只需只需 loglog2 2n n 1 1趟便可排好序。趟便可排好序。而且，每趟需要比较和移动的元素也呈指数下降，加上而且，每趟需要比较和移动的元素也呈指数下降，加上编程时使用了交替逼近技巧，更进一步减少了移动次数，所编程时使用了交替逼近技巧，更进一步减少了移动次数，所以速度特别快。以速度特别快。 基本思想基本思想在待排记录中依次选择关键字最在待排记录中依次选择关键字最小的记录作为有序序列的最后一小的记录作为有序序列的最后一条记录，逐渐缩小范围直至全部条记录，逐渐缩小范围直至全部记录

35、选择完毕。记录选择完毕。 49 38 65 97 76 49 38 65 97 76 1313 27 27 4949 1338 65 97 76 49 1338 65 97 76 49 2727 4949 13 2765 97 76 49 13 2765 97 76 49 38 38 4949 13 27 3865 97 76 13 27 3865 97 76 4949 4949 13 27 38 4965 97 76 13 27 38 4965 97 76 4949 13 27 38 49 13 27 38 49 4949 6565 97 76 97 76 13 27 38 49 13 27

36、 38 49 4949 6597 6597 7676 13 27 38 49 13 27 38 49 4949 65 76 97 65 76 97简单选择排序的演示简单选择排序的演示void SelectSort(SqList &K) /简单选择排序简单选择排序 for (i=1; iL.length; +i) /在在L.ri.L.length 中选择中选择key最小的记录最小的记录 k=i; for( j=i+1;j=L.length ; j+) if ( L.rj.key L.rk.key) k=j; if(k!=i)L.riL.rj; /SelectSort 特点：特点： 1) 1) 算

37、法简单算法简单, , 时间复杂度为时间复杂度为O(nO(n2 2) ) 2)2) 序列存储：顺序、链式序列存储：顺序、链式 3) 3) 稳定稳定 1313 4949 3838 3838 3838 6565 6565 9797 7676 131313131313 2727 2727 494949 38 65 97 76 13 27 49 38 65 97 76 13 27 4949 2727 4949 3838 3838 3838 6565 6565 9797 7676 * * 2727 7676 2727 2727 4949堆排序堆排序1堆的定义堆的定义若有若有n个元素个元素(a1，a2，a3

38、，an)，当满足如下条件：，当满足如下条件： aia2i aia2i（1） aia2i+1 或或 (2) aia2i+1 其中其中i=1,2, n/2 则称此则称此n个元素个元素a1，a2，a3，an为一个堆。为一个堆。若将此元素序列按顺序组成一棵完全二叉树，则（若将此元素序列按顺序组成一棵完全二叉树，则（1）称）称为小根堆（二叉树的所有根结点值小于或等于左右孩子为小根堆（二叉树的所有根结点值小于或等于左右孩子的值），（的值），（2）称为）称为大根堆大根堆（二叉树的所有根结点值大于（二叉树的所有根结点值大于或等于左右孩子的值）。或等于左右孩子的值）。小根堆小根堆 8 81616 9 9 1 1

39、 6 6 2 2 11111010 5 5 4 4大根堆大根堆1616 9 9 8 81010 6 6 2 2 1111 1 1 5 5 4 4 1 1 6 6 8 81212 9 91616 2 2 1111 5 5 1 14 4 1 1 9 9 8 81010 6 61616 2 2 1111 5 5 4 4不是堆不是堆不是堆不是堆2.堆与完全二叉树关系堆与完全二叉树关系若若n个元素个元素a1，a2，a3，an满足堆，且让结点按满足堆，且让结点按1、2、3、n顺序编号，根据完全二叉树的性质（若顺序编号，根据完全二叉树的性质（若i为根结点，为根结点，则左孩子为则左孩子为2i，右孩子为，右孩子

40、为2i+1）可知，一个堆对应着一颗）可知，一个堆对应着一颗完全二叉树，堆排序实际与一棵完全二叉树有关。若将元完全二叉树，堆排序实际与一棵完全二叉树有关。若将元素初始序列组成一棵完全二叉树，则堆排序可以包含建立素初始序列组成一棵完全二叉树，则堆排序可以包含建立初始堆（使排序码变成能符合堆的定义的完全二叉树）和初始堆（使排序码变成能符合堆的定义的完全二叉树）和利用堆进行排序两个阶段。利用堆进行排序两个阶段。3、实例、实例如序列如序列(80,75,40,62,73,35,28,50,38,25,47,15)可以验证它满足可以验证它满足堆的条件堆的条件,因此是一个堆因此是一个堆.下图给出其对应的完全二

41、叉树下图给出其对应的完全二叉树.1 8075406273283550382547 1532456789101112 堆排序：将无序序列建成一个堆，得到关键字最小（或堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到个元素重又建成一个堆，则可得到n个元素的次小值个元素的次小值；重复执行，得到一个有序序列，这个过程叫；重复执行，得到一个有序序列，这个过程叫 堆排序需解决的两个问题：堆排序需解决的两个问题： 如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？ 如

42、何在输出堆顶元素之后，调整剩余元素，使之成为如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？一个新的堆？ 第二个问题解决方法第二个问题解决方法筛选筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为过程为“筛选筛选”例1327384965765097972738

43、4965765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 27 384965502738769713输出：13 27 387665502738499713输出：13 27 38 495065762738499713输出：13 27 38 499765762738495013输出：13 27 38 49 506597762738495013输出：13 27 38 49 509765762738495013输出：13 27 38 49 50 65

44、7665972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 97堆排序的演示堆排序的演示 typedef SqList HeapType; 1 1 9 9 8 8 1010 6 61616 2 2 1111 4 4 5 5H.length1010H.r 1 1 2 92 9 11 4 6 811 4 6 8 1010 16 516 5 0 1 2 0 1 2 3 4 3 4 5 5 6 7 6 7 8 9 10 8 9 10

45、算法描述 第一个问题解决方法 方法：从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例 含8个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 5050971365381327494913382765765097算法描述算法评价时间复杂度：最坏情况下T(n)=O(nlogn)空间复杂度：

46、S(n)=O(1)堆排序的性能堆排序的性能堆排序是不稳定的；堆排序是不稳定的；堆排序适用于堆排序适用于n 较大的情况较大的情况 堆排序的性能堆排序的性能 堆排序是不稳定的；堆排序是不稳定的； 堆排序的时间复杂度堆排序的时间复杂度O(nlog n) 堆排序适用于堆排序适用于n 较大的情况较大的情况8.5 归并排序 归并将两个或两个以上的有序表组合成一个新的有序表，叫 2-路归并排序 排序过程设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1两两合并，得到n/2个长度为2或1的有序子序列再两两合并，如此重复，直至得到一个长度为n的有序序列为止将下属两个已排序的顺序表合并成一个有序表。将下属两个已排序的顺序表合并成一个有序表。顺序比较两者的相应元素，小者移入另一表中，反顺序比较两者