内部排序-数据结构DATASTRUCTURE.ppt

数据结构数据结构 (DATA STRUCTURE)计算机科学与技术学院计算机科学与技术学院课程代码：0600060第十章第十章 排序排序概述概述 插入排序插入排序 交换排序交换排序 选择排序选择排序 归并排序归并排序 基数排序基数排序2课程代码：060006010.1 概述概述1)1)基本概念基本概念n n排排排排序序序序：将将将将一一一一组组组组记记记记录录录录按按按按相相相相应应应应关关关关键键键键字字字字的的的的值值值值递递递递增增增增或或或或递递递递减减减减次序重新排列的过程。次序重新排列的过程。次序重新排列的过程。次序重新排列的过程。n n关关关关键键键键字字字字(key):(key):通通通通常常常常数数数数据据据据对对对对象象象象有有有有多多多多个个个个属属属属性性性性域域域域，即即即即多多多多个个个个数数数数据据据据成成成成员员员员组组组组成成成成，其其其其中中中中有有有有一一一一个个个个属属属属性性性性域域域域可可可可用用用用来来来来区区区区分分分分对象对象对象对象，作为排序依据。该域即为关键字。，作为排序依据。该域即为关键字。，作为排序依据。该域即为关键字。，作为排序依据。该域即为关键字。n n排序算法的稳定性排序算法的稳定性:如果在对象序列中有两个对如果在对象序列中有两个对象象ri和和rj，它们的关键字，它们的关键字 ki=kj，且在排，且在排序之前，对象序之前，对象ri排在排在rj前面。如果在排序之后，前面。如果在排序之后，对象对象ri仍在对象仍在对象rj的前面，则称这个排序方法的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。是稳定的，否则称这个排序方法是不稳定的。3课程代码：0600060 2 2）排序方法的分类）排序方法的分类n n根据排序时使用的存储器不同，分为：根据排序时使用的存储器不同，分为：根据排序时使用的存储器不同，分为：根据排序时使用的存储器不同，分为：内部排序内部排序内部排序内部排序:在内存实现，数据对象全部存放在内存，无在内存实现，数据对象全部存放在内存，无在内存实现，数据对象全部存放在内存，无在内存实现，数据对象全部存放在内存，无内外存数据交换；适合少量数据，速度快。内外存数据交换；适合少量数据，速度快。内外存数据交换；适合少量数据，速度快。内外存数据交换；适合少量数据，速度快。外部排序外部排序外部排序外部排序:排序期间全部对象太多，不能同时存放在内排序期间全部对象太多，不能同时存放在内排序期间全部对象太多，不能同时存放在内排序期间全部对象太多，不能同时存放在内存，必须根据排序过程的要求，不断在内外存之间移存，必须根据排序过程的要求，不断在内外存之间移存，必须根据排序过程的要求，不断在内外存之间移存，必须根据排序过程的要求，不断在内外存之间移动；适合大量数据，速度慢。动；适合大量数据，速度慢。动；适合大量数据，速度慢。动；适合大量数据，速度慢。n n按实现策略，内排序分五大类：按实现策略，内排序分五大类：按实现策略，内排序分五大类：按实现策略，内排序分五大类：插入排序插入排序插入排序插入排序:直接插入、直接插入、直接插入、直接插入、shellshell排序排序排序排序 交换排序：冒泡、快速排序交换排序：冒泡、快速排序交换排序：冒泡、快速排序交换排序：冒泡、快速排序 选择排序：简单选择、树型选择、堆排序选择排序：简单选择、树型选择、堆排序选择排序：简单选择、树型选择、堆排序选择排序：简单选择、树型选择、堆排序 归并排序：归并排序：归并排序：归并排序：基数排序：基数排序：基数排序：基数排序：4课程代码：0600060n n按排序所需工作量，内排序分为：按排序所需工作量，内排序分为：按排序所需工作量，内排序分为：按排序所需工作量，内排序分为：简单排序方法简单排序方法简单排序方法简单排序方法:O(n:O(n2 2)简单排序简单排序简单排序简单排序 先进排序方法先进排序方法先进排序方法先进排序方法:O(nlogn):O(nlogn)堆排序、快速排序堆排序、快速排序堆排序、快速排序堆排序、快速排序 基数排序方法基数排序方法基数排序方法基数排序方法:O(dn):O(dn)基数排序基数排序基数排序基数排序3 3）排序算法的评价标准）排序算法的评价标准n n时间复杂度时间复杂度时间复杂度时间复杂度:排序的时间开销用算法执行中的排序的时间开销用算法执行中的排序的时间开销用算法执行中的排序的时间开销用算法执行中的数据数据数据数据比较次数比较次数比较次数比较次数与与与与数据移动次数数据移动次数数据移动次数数据移动次数来衡量。来衡量。来衡量。来衡量。n n空间复杂度空间复杂度空间复杂度空间复杂度:算法执行时所需的附加空间算法执行时所需的附加空间算法执行时所需的附加空间算法执行时所需的附加空间。n n稳定性稳定性稳定性稳定性:n n简单性简单性简单性简单性:5课程代码：0600060 4 4）本书中待排序数据表的数据类型描述）本书中待排序数据表的数据类型描述#define Maxsize 50 /待排序序列中记录的最大个数待排序序列中记录的最大个数 待排序表中每个数据元素的数据类型定义待排序表中每个数据元素的数据类型定义typedef struct int key;/表示排序关键字表示排序关键字 elemtype otherinfo;/排序记录中的其他所有数据项排序记录中的其他所有数据项 Snode;待排序数据表的数据类型定义待排序数据表的数据类型定义typedef struct Snode RMaxsize+1;/存放待排序全体记录存放待排序全体记录 int length;/排序记录个数排序记录个数 SList;6课程代码：060006010.2 插入排序插入排序(Insert Sorting)1)基本思想：基本思想：将一个记录将一个记录将一个记录将一个记录插入插入插入插入到已排好序的到已排好序的到已排好序的到已排好序的有序表有序表有序表有序表中中中中，从而得到一个新的、记录数增，从而得到一个新的、记录数增，从而得到一个新的、记录数增，从而得到一个新的、记录数增1 1的有序表。的有序表。的有序表。的有序表。将顺序存储的将顺序存储的将顺序存储的将顺序存储的 n n 个待排序记录划分为个待排序记录划分为个待排序记录划分为个待排序记录划分为两个区间两个区间两个区间两个区间：一个有：一个有：一个有：一个有序区，一个无序区序区，一个无序区序区，一个无序区序区，一个无序区;初始时：有序区为初始时：有序区为初始时：有序区为初始时：有序区为RR1 1，无序区为，无序区为，无序区为，无序区为RR2 2.R.Rn n，令，令，令，令 i i 指向无序区中第一个记录，初值指向无序区中第一个记录，初值指向无序区中第一个记录，初值指向无序区中第一个记录，初值 i i=2=2。当当当当i i n n时，重复执行：时，重复执行：时，重复执行：时，重复执行：将当前无序区中第一个记录将当前无序区中第一个记录将当前无序区中第一个记录将当前无序区中第一个记录 R Ri i 插入到有序区的插入到有序区的插入到有序区的插入到有序区的适当位置适当位置适当位置适当位置，使有序区变为：使有序区变为：使有序区变为：使有序区变为：RR1 1.R.Ri i，无序区变为，无序区变为，无序区变为，无序区变为RRi+1i+1.R.Rn n。当当当当i in n时，有序区变为时，有序区变为时，有序区变为时，有序区变为RR1 1.R.Rn n，排序结束。，排序结束。，排序结束。，排序结束。直接插入排序直接插入排序7课程代码：06000602）逐步求精：）逐步求精：将将 Ri 插入到有序区插入到有序区R1.Ri-1中中适适当位置当位置，即保持仍然有序。，即保持仍然有序。具体做法：当插入第具体做法：当插入第 i 个对象时，前面的个对象时，前面的 R1,R2.Ri-1已经排好序。这时，用已经排好序。这时，用 Ri 的关键字与的关键字与Ri-1,Ri-2,的关键字顺序进行比较，若比的关键字顺序进行比较，若比 Ri 的关键字大，就后移一个位置，如此重复，的关键字大，就后移一个位置，如此重复，直到找到直到找到适当的插入位置适当的插入位置，即将，即将Ri插入。插入。8课程代码：0600060排序过程演示：排序过程演示：9课程代码：0600060 3）算法实现：）算法实现：void InsertSort(SqList&L)for(i=2；i=L.length；i+)if(L.Ri.key L.Ri-1.key)/小于时小于时,将将Ri插入有序表插入有序表 L.R0=L.Ri；/R0作监测哨兵作监测哨兵 for(j=i-1；L.R0.key L.Rj.key；j-)L.Rj+1=L.Rj；/*记录后移记录后移*/L.Rj+1=L.R0；/*插插入入到到正正确确位位置置*/10课程代码：06000604)算法分析算法分析n n时间复杂度：时间复杂度：时间复杂度：时间复杂度：设待排序对象个数为设待排序对象个数为设待排序对象个数为设待排序对象个数为 n n，则共需，则共需，则共需，则共需n n-1-1 趟插入排序。每趟排序过程中关键字比较趟插入排序。每趟排序过程中关键字比较趟插入排序。每趟排序过程中关键字比较趟插入排序。每趟排序过程中关键字比较次数和对象移动次数与对象的初始排列有关。次数和对象移动次数与对象的初始排列有关。次数和对象移动次数与对象的初始排列有关。次数和对象移动次数与对象的初始排列有关。最好情况最好情况最好情况最好情况(正序正序正序正序):):最坏情况最坏情况最坏情况最坏情况(逆序逆序逆序逆序):):n n空间复杂度：空间复杂度：空间复杂度：空间复杂度：使用了一个临时空间使用了一个临时空间使用了一个临时空间使用了一个临时空间 O(1)O(1)n n稳定性：稳定性：稳定性：稳定性：直接插入排序是一种直接插入排序是一种直接插入排序是一种直接插入排序是一种稳定稳定稳定稳定的排序方的排序方的排序方的排序方法。法。法。法。11课程代码：0600060 希尔排序希尔排序(缩小增量法）缩小增量法）1）基本思想：）基本思想：先将整个待排序记录序列先将整个待排序记录序列先将整个待排序记录序列先将整个待排序记录序列分割成若干分割成若干分割成若干分割成若干子序列子序列子序列子序列分别进行直接插入排序，待整个序列分别进行直接插入排序，待整个序列分别进行直接插入排序，待整个序列分别进行直接插入排序，待整个序列“基本基本基本基本有序有序有序有序”时，再对时，再对时，再对时，再对全体记录全体记录全体记录全体记录进行一次直接插入排序。进行一次直接插入排序。进行一次直接插入排序。进行一次直接插入排序。排序过程：排序过程：排序过程：排序过程：先将整个待排序记录先将整个待排序记录先将整个待排序记录先将整个待排序记录以以以以d d1为步长分成若干子序列为步长分成若干子序列为步长分成若干子序列为步长分成若干子序列，把所把所把所把所有相隔为有相隔为有相隔为有相隔为d d1的记录放在同一组内；的记录放在同一组内；的记录放在同一组内；的记录放在同一组内；在每个在每个在每个在每个分组内进行直接插入分组内进行直接插入分组内进行直接插入分组内进行直接插入排序；排序；排序；排序；在将整个待排序记录序列在将整个待排序记录序列在将整个待排序记录序列在将整个待排序记录序列以以以以d d2(d(d2dd1n)r2.keyr1.keyr2.key，则则则则交换交换交换交换；然后比；然后比；然后比；然后比较第二个记录与第三个记录；依次类推，直至第较第二个记录与第三个记录；依次类推，直至第较第二个记录与第三个记录；依次类推，直至第较第二个记录与第三个记录；依次类推，直至第n-1n-1个记录和第个记录和第个记录和第个记录和第n n个记录比较为止个记录比较为止个记录比较为止个记录比较为止第一趟冒泡排序第一趟冒泡排序第一趟冒泡排序第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上结果关键字最大的记录被安置在最后一个记录上结果关键字最大的记录被安置在最后一个记录上结果关键字最大的记录被安置在最后一个记录上 对前对前对前对前n-1n-1个记录进行第二趟冒泡排序，结果使关键字个记录进行第二趟冒泡排序，结果使关键字个记录进行第二趟冒泡排序，结果使关键字个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第次大的记录被安置在第次大的记录被安置在第次大的记录被安置在第n-1n-1个记录位置个记录位置个记录位置个记录位置 重复上述过程，直到重复上述过程，直到重复上述过程，直到重复上述过程，直到“在一趟排序过程中没有进行在一趟排序过程中没有进行在一趟排序过程中没有进行在一趟排序过程中没有进行过交换记录的操作过交换记录的操作过交换记录的操作过交换记录的操作”为止为止为止为止16课程代码：06000602）算法实现）算法实现void bubble_Sort(int a,int n)/起泡排序算法起泡排序算法起泡排序算法起泡排序算法 for(int i=n-1,change=1;i=1&change;i-)change=0;for(j=0;j aj+1)Swap(j+1,j);/发生逆序发生逆序发生逆序发生逆序 change=1;/做做做做“发生了交换发生了交换发生了交换发生了交换”标志标志标志标志 17课程代码：0600060排序过程演示：排序过程演示：18课程代码：06000603）算法分析）算法分析n n时间复杂度：时间复杂度：最好情况最好情况最好情况最好情况(正序正序正序正序)：算法只执行一趟排序，做算法只执行一趟排序，做算法只执行一趟排序，做算法只执行一趟排序，做 n-1 n-1 次关键字比较，不移动对象。次关键字比较，不移动对象。次关键字比较，不移动对象。次关键字比较，不移动对象。最坏情况最坏情况最坏情况最坏情况(逆序逆序逆序逆序):):算法执行了算法执行了算法执行了算法执行了n-1n-1趟起泡，第趟起泡，第趟起泡，第趟起泡，第 i i 趟趟趟趟(1(1 i i n)n)做了做了做了做了 n-i n-i 次关键字比较，执行了次关键字比较，执行了次关键字比较，执行了次关键字比较，执行了n-i n-i 次对象交换。次对象交换。次对象交换。次对象交换。n n总的关键字比较次数总的关键字比较次数总的关键字比较次数总的关键字比较次数:n n总的对象移动次数为：总的对象移动次数为：总的对象移动次数为：总的对象移动次数为：n n空间复杂度：空间复杂度：O(1)n n稳定性：稳定稳定性：稳定19课程代码：0600060 快速排序快速排序(Quick Sort)1）基本思想：）基本思想：通过一趟排序，将待排通过一趟排序，将待排序记录序记录分割分割成独立的两部分，其中成独立的两部分，其中一一部分记录的关键字均比另一部分记录部分记录的关键字均比另一部分记录的关键字小，的关键字小，则可分别对这两部分记则可分别对这两部分记录进行排序，以达到整个序列有序。录进行排序，以达到整个序列有序。20课程代码：0600060排序过程演示：排序过程演示：21课程代码：06000602）算法分析：）算法分析：n n时间复杂度：平均时间复杂度是时间复杂度：平均时间复杂度是O(nlog2n)。实验结果表明：实验结果表明：就平均计算时间而言，快速就平均计算时间而言，快速排序是我们所讨论所有内排序方法中最好的排序是我们所讨论所有内排序方法中最好的一个一个。n n空间复杂度：空间复杂度：快快快快速速速速排排排排序序序序是是是是递递递递归归归归的的的的，需需需需要要要要有有有有一一一一个个个个栈栈栈栈存存存存放放放放每每每每层层层层递递递递归调用时的指针和参数。归调用时的指针和参数。归调用时的指针和参数。归调用时的指针和参数。最最最最大大大大递递递递归归归归调调调调用用用用层层层层次次次次数数数数与与与与递递递递归归归归树树树树的的的的深深深深度度度度一一一一致致致致，理理理理想想想想情情情情况况况况为为为为 loglog2 2(n n+1)+1)。因因因因此此此此，要要要要求求求求存存存存储储储储开开开开销销销销为为为为 O(logO(log2 2n n)。最坏情况将达到。最坏情况将达到。最坏情况将达到。最坏情况将达到O(O(n n)。n n稳定性：稳定性：快速排序是一种快速排序是一种不稳定不稳定的排序方法。的排序方法。22课程代码：060006010.4 选择排序选择排序n n基本思想：基本思想：每一趟排序每一趟排序(如第如第 i 趟，趟，i=1,2,n-1-1)在在 n-i+1 个待排序对象中选出关键字最小的对个待排序对象中选出关键字最小的对象象,作为有序序列的第作为有序序列的第 i 个对象。个对象。待第待第 n-1 趟排序后，待排序对象只剩下趟排序后，待排序对象只剩下1个，个，就不用再选了。就不用再选了。23课程代码：06000601）基本思想：）基本思想：直接选择排序是一种简单的直接选择排序是一种简单的排序方法，它的基本步骤是：排序方法，它的基本步骤是：把顺序存储的把顺序存储的 n 个待排序的记录看成由一个个待排序的记录看成由一个有序区有序区和一个和一个无序区无序区组成。初始时，有序区组成。初始时，有序区为空，无序区为为空，无序区为(R1,R2,Rn)；在一趟选择排序中，从无序区在一趟选择排序中，从无序区选出一个关键选出一个关键字最小的记录字最小的记录，把它放到有序区的，把它放到有序区的表尾；表尾；经过经过 n-1 趟选择和插入后，趟选择和插入后，n个记录变为递增个记录变为递增有序。有序。直接选择排序直接选择排序24课程代码：0600060排序过程演示：排序过程演示：25课程代码：06000602）算法分析）算法分析 n n时间复杂度：时间复杂度：记录移动次数记录移动次数记录移动次数记录移动次数n n 最好情况：最好情况：最好情况：最好情况：0 0n n 最坏情况：最坏情况：最坏情况：最坏情况：3(n-1)3(n-1)比较次数：比较次数：比较次数：比较次数：直接选择排序的关键字比较次数与对直接选择排序的关键字比较次数与对直接选择排序的关键字比较次数与对直接选择排序的关键字比较次数与对象的初始排列无关。象的初始排列无关。象的初始排列无关。象的初始排列无关。n n第第第第 i i 趟选择具有最小关键字对象所需的比较次数总是趟选择具有最小关键字对象所需的比较次数总是趟选择具有最小关键字对象所需的比较次数总是趟选择具有最小关键字对象所需的比较次数总是 n n-i i次；次；次；次；n n因此，总的关键字比较次数为因此，总的关键字比较次数为因此，总的关键字比较次数为因此，总的关键字比较次数为:n n空间复杂度：空间复杂度：空间复杂度：空间复杂度：O(1)O(1)n n稳定性：不稳定稳定性：不稳定稳定性：不稳定稳定性：不稳定26课程代码：0600060 树型选择排序树型选择排序1）锦标赛排序）锦标赛排序(Tournament Tree Sort)n n它的思想与体育比赛时的淘汰赛类似。首先取得它的思想与体育比赛时的淘汰赛类似。首先取得它的思想与体育比赛时的淘汰赛类似。首先取得它的思想与体育比赛时的淘汰赛类似。首先取得 n n 个对象的关键字，进行两两比较，得到个对象的关键字，进行两两比较，得到个对象的关键字，进行两两比较，得到个对象的关键字，进行两两比较，得到 n n/2/2 个比个比个比个比较的优胜者较的优胜者较的优胜者较的优胜者(关键字小者关键字小者关键字小者关键字小者)，作为第一步比较的结果，作为第一步比较的结果，作为第一步比较的结果，作为第一步比较的结果保留下来。然后对这保留下来。然后对这保留下来。然后对这保留下来。然后对这 n n/2/2 个对象再进行关键字的个对象再进行关键字的个对象再进行关键字的个对象再进行关键字的两两比较，两两比较，两两比较，两两比较，如此重复，直到选出一个关键字最，如此重复，直到选出一个关键字最，如此重复，直到选出一个关键字最，如此重复，直到选出一个关键字最小的对象为止。小的对象为止。小的对象为止。小的对象为止。n n在图例中，最下面是对象排列的初始状态，相当于在图例中，最下面是对象排列的初始状态，相当于在图例中，最下面是对象排列的初始状态，相当于在图例中，最下面是对象排列的初始状态，相当于一棵满二叉树的叶结点，它存放的是所有参加排序一棵满二叉树的叶结点，它存放的是所有参加排序一棵满二叉树的叶结点，它存放的是所有参加排序一棵满二叉树的叶结点，它存放的是所有参加排序的对象的关键字。的对象的关键字。的对象的关键字。的对象的关键字。27课程代码：0600060n n如如如如果果果果 n n 不不不不是是是是2 2的的的的 k k 次次次次幂幂幂幂，则则则则让让让让叶叶叶叶结结结结点点点点数数数数补补补补足足足足到到到到满满满满足足足足 2 2k k-1 1 n n 2 2k k 的的的的2 2k k个个个个。叶叶叶叶结结结结点点点点上上上上面面面面一一一一层层层层的的的的非非非非叶叶叶叶结结结结点点点点是是是是叶结点关键字两两比较的结果。最顶层是树的根。叶结点关键字两两比较的结果。最顶层是树的根。叶结点关键字两两比较的结果。最顶层是树的根。叶结点关键字两两比较的结果。最顶层是树的根。0808Winner Winner 212108080808636325*25*212121212525494925*25*161608086363treetree7 7 treetree8 8 treetree9 9 treetree10 10 treetree11 11 treetree12 12 treetree13 13 treetree141428课程代码：0600060 堆排序堆排序1 1）堆的定义：）堆的定义：n n个元素的序列个元素的序列(R1,R2,Rn),(R1,R2,Rn),对应的对应的关键字序列为关键字序列为(k1,k2,kn)(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)962791138831327384965765097可将堆序列看成完全二叉树，则堆顶可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中元素（完全二叉树的根）必为序列中n n个元素的最小值或最大值个元素的最小值或最大值29课程代码：0600060n n堆排序在排序过程中，利用完全二叉树双亲与孩子结点堆排序在排序过程中，利用完全二叉树双亲与孩子结点堆排序在排序过程中，利用完全二叉树双亲与孩子结点堆排序在排序过程中，利用完全二叉树双亲与孩子结点的关系来选择关键字最小（或最大）的记录。的关系来选择关键字最小（或最大）的记录。的关系来选择关键字最小（或最大）的记录。的关系来选择关键字最小（或最大）的记录。n n基本思想：基本思想：基本思想：基本思想：将整个待排序记录分为有序区和无序区，初始时有序区为空，无序区将整个待排序记录分为有序区和无序区，初始时有序区为空，无序区将整个待排序记录分为有序区和无序区，初始时有序区为空，无序区将整个待排序记录分为有序区和无序区，初始时有序区为空，无序区为为为为R1,R2,RnR1,R2,Rn 将无序区中记录看作一棵顺序存放的完全二叉树上的结点，对该完全将无序区中记录看作一棵顺序存放的完全二叉树上的结点，对该完全将无序区中记录看作一棵顺序存放的完全二叉树上的结点，对该完全将无序区中记录看作一棵顺序存放的完全二叉树上的结点，对该完全二叉树按照堆定义要求进行调整，使关键字最小二叉树按照堆定义要求进行调整，使关键字最小二叉树按照堆定义要求进行调整，使关键字最小二叉树按照堆定义要求进行调整，使关键字最小(大大大大)的记录成为二叉的记录成为二叉的记录成为二叉的记录成为二叉树的根树的根树的根树的根(存在存在存在存在R1R1中中中中)初建堆初建堆初建堆初建堆 将根结点中记录与无序区中最后一个结点将根结点中记录与无序区中最后一个结点将根结点中记录与无序区中最后一个结点将根结点中记录与无序区中最后一个结点交换交换交换交换，并将无序区中最后一，并将无序区中最后一，并将无序区中最后一，并将无序区中最后一个记录划入有序区内。个记录划入有序区内。个记录划入有序区内。个记录划入有序区内。无序区中记录所构成的二叉树中，根结点的左、右子树均满足堆定义，无序区中记录所构成的二叉树中，根结点的左、右子树均满足堆定义，无序区中记录所构成的二叉树中，根结点的左、右子树均满足堆定义，无序区中记录所构成的二叉树中，根结点的左、右子树均满足堆定义，故经过适当调整后可将无序区中记录重建成堆，无序区当前最小故经过适当调整后可将无序区中记录重建成堆，无序区当前最小故经过适当调整后可将无序区中记录重建成堆，无序区当前最小故经过适当调整后可将无序区中记录重建成堆，无序区当前最小(大大大大)成为根。成为根。成为根。成为根。堆调整堆调整堆调整堆调整 重复上述过程，直到无序区为空重复上述过程，直到无序区为空重复上述过程，直到无序区为空重复上述过程，直到无序区为空(即执行即执行即执行即执行n-1n-1次次次次)。2)2)堆排序基本思想堆排序基本思想30课程代码：0600060n n堆排序需解决的两个问题：堆排序需解决的两个问题：堆排序需解决的两个问题：堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一如何在输出堆顶元素之后，调整剩余元素，使之成为一如何在输出堆顶元素之后，调整剩余元素，使之成为一如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？个新的堆？个新的堆？个新的堆？n n第二个问题解决方法第二个问题解决方法第二个问题解决方法第二个问题解决方法筛选筛选筛选筛选 方法：输出堆顶元素之后，以堆中最后一个元素替代之；方法：输出堆顶元素之后，以堆中最后一个元素替代之；方法：输出堆顶元素之后，以堆中最后一个元素替代之；方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并然后将根结点值与左、右子树的根结点值进行比较，并然后将根结点值与左、右子树的根结点值进行比较，并然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，与其中小者进行交换；重复上述操作，直至叶子结点，与其中小者进行交换；重复上述操作，直至叶子结点，与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为将得到新的堆，称这个从堆顶至叶子的调整过程为将得到新的堆，称这个从堆顶至叶子的调整过程为将得到新的堆，称这个从堆顶至叶子的调整过程为“堆堆堆堆筛选筛选筛选筛选”31课程代码：0600060n n第一个问题解决方法第一个问题解决方法第一个问题解决方法第一个问题解决方法 方法：依次对无序序列的第方法：依次对无序序列的第方法：依次对无序序列的第方法：依次对无序序列的第 n/2n/2 ，n/2n/2 -1,-1,直至第直至第直至第直至第1 1个元素作为根的子树进行堆调整。个元素作为根的子树进行堆调整。个元素作为根的子树进行堆调整。个元素作为根的子树进行堆调整。因为无序序列所对应完全二叉树的最后一个非终端结因为无序序列所对应完全二叉树的最后一个非终端结因为无序序列所对应完全二叉树的最后一个非终端结因为无序序列所对应完全二叉树的最后一个非终端结点是点是点是点是第第第第 n/2n/2 个元素，所以筛选要从个元素，所以筛选要从个元素，所以筛选要从个元素，所以筛选要从第第第第 n/2n/2 个元素开个元素开个元素开个元素开始向上进行。始向上进行。始向上进行。始向上进行。4 4）初建堆）初建堆 自下而上自下而上3 3）堆调整）堆调整 自上而下自上而下32课程代码：0600060排序过程演示：排序过程演示：33课程代码：06000605)算法分析算法分析n n时间复杂度：时间复杂度：O(nlog2n)。n n空间复杂度：空间复杂度：O(1)n n稳定性：堆排序是一个稳定性：堆排序是一个不稳定不稳定的排序方法。的排序方法。34课程代码：060006010.5 归并排序归并排序(Merge Sort)1）归并：）归并：是将两个或两个以上的是将两个或两个以上的有序表有序表合并合并成一个新的有序表。成一个新的有序表。两路归并两路归并两路归并两路归并多路归并多路归并多路归并多路归并n n归并方法：设两个有序表归并方法：设两个有序表A和和B 的对象个数的对象个数(表长表长)分别为分别为 al 和和 bl，变量，变量 i 和和 j 分别是表分别是表A和表和表B的当前检测指针。设表的当前检测指针。设表C是归并后的新是归并后的新有序表，变量有序表，变量 k 是它的当前存放指针。是它的当前存放指针。35课程代码：06000602）归并排序）归并排序n n归并排序算法就是利用两路归并过程进行排归并排序算法就是利用两路归并过程进行排序。其基本思想是：序。其基本思想是：设初始待排序序列含有设初始待排序序列含有设初始待排序序列含有设初始待排序序列含有n n个记录，则可看成个记录，则可看成个记录，则可看成个记录，则可看成n n个有个有个有个有序的子序列序的子序列序的子序列序的子序列，每个子序列长度为，每个子序列长度为，每个子序列长度为，每个子序列长度为1 1。把这。把这。把这。把这n n个记录个记录个记录个记录两两两两两两两两二路归并，得到二路归并，得到二路归并，得到二路归并，得到 n n/2/2 个有序子序列，每个个有序子序列，每个个有序子序列，每个个有序子序列，每个子序列的长度为子序列的长度为子序列的长度为子序列的长度为2 2或或或或1(n1(n为奇数为奇数为奇数为奇数)。一趟归并一趟归并一趟归并一趟归并排序排序排序排序再对再对再对再对 n n/2/2 个有序子序列进行两两个有序子序列进行两两个有序子序列进行两两个有序子序列进行两两二路归并二路归并二路归并二路归并，如此重复，直至得到一个长度为如此重复，直至得到一个长度为如此重复，直至得到一个长度为如此重复，直至得到一个长度为n n的有序序列为的有序序列为的有序序列为的有序序列为止。止。止。止。36课程代码：0600060例例初始关键字：初始关键字：49 38 65 97 76 13 27一趟归并后：一趟归并后：38 49 65 97 13 76 27二趟归并后：二趟归并后：38 49 65 97 13 27 76三趟归并后：三趟归并后：13 27 38 49 65 76 9737课程代码：0600060排序过程演示：排序过程演示：38课程代码：06000603）算法分析）算法分析n n时间复杂度：时间复杂度：O(nlog2n)n n空间复杂度：空间复杂度：O(n)归归并并排排序序占占用用附附加加存存储储较较多多，需需要要另另外外一一个个与与原原待待排排序序对对象象数数组组同同样样大大小小的的辅辅助助数数组组。这是这个算法的缺点。这是这个算法的缺点。n n稳定性：归并排序是一种稳定性：归并排序是一种稳定稳定的排序方法。的排序方法。39课程代码：060006010.6 基数排序基数排序(分配排序分配排序)1）基本概念）基本概念n n基数基数：若任一记录的：若任一记录的关键字关键字 ki 可以看成由可以看成由d个个分量分量 ki1,ki2,kid 组成，且每个分量的取值范围相同：组成，且每个分量的取值范围相同：C1 kij Crd (1 j d)，则称，则称rd为基数。为基数。十进制数十进制数十进制数十进制数 rd=10 C rd=10 C1 1=0,C=0,C1010=9=9小写字母小写字母小写字母小写字母 rd=26 C rd=26 C1 1=a,C=a,C1010=z=zn n基数排序是采用基数排序是采用“分配分配”与与“收集收集”的办法，用的办法，用对多关键字进行排序的思想实现对单关键字进行对多关键字进行排序的思想实现对单关键字进行排序的方法。排序的方法。40课程代码：0600060n n多关键字排序多关键字排序 以以以以扑扑扑扑克克克克牌牌牌牌排排排排序序序序为为为为例例例例。每每每每张张张张扑扑扑扑克克克克牌牌牌牌有有有有两两两两个个个个“关关关关键键键键字字字字”：花花花花色和面值。其有序关系为：色和面值。其有序关系为：色和面值。其有序关系为：色和面值。其有序关系为：n n 花色：花色：花色：花色：n n 面值：面值：面值：面值：2 3 4 5 6 7 8 9 10 J Q K A2 3 4 5 6 7 8 9 10 J Q K A 如果我们把所有扑克牌排成以下次序：如果我们把所有扑克牌排成以下次序：如果我们把所有扑克牌排成以下次序：如果我们把所有扑克牌排成以下次序：2,2,A,A,2,2,A,A,2,2,A,A,2,2,A A 这就是这就是这就是这就是多关键字排序多关键字排序多关键字排序多关键字排序。排序后形成的有序序列叫做词典。排序后形成的有序序列叫做词典。排序后形成的有序序列叫做词典。排序后形成的有序序列叫做词典有序序列。有序序列。有序序列。有序序列。2）基数排序）基数排序41课程代码：0600060对于上例两关键字的排序，可以先按花色排序，对于上例两关键字的排序，可以先按花色排序，对于上例两关键字的排序，可以先按花色排序，对于上例两关键字的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再之后再按面值排序；也可以先按面值排序，再之后再按面值排序；也可以先按面值排序，再之后再按面值排序；也可以先按面值排序，再按花色排序。按花色排序。按花色排序。按花色排序。一般情况下，假定一个序列有一般情况下，假定一个序列有一般情况下，假定一个序列有一般情况下，假定一个序列有n n 个对象个对象个对象个对象 R R1 1,R R2 2,R Rn n ，且每个对象，且每个对象，且每个对象，且每个对象R Ri i 中含有中含有中含有中含有 d d 个关键字个关键字个关键字个关键字如果对于序列中任意两个对象如果对于序列中任意两个对象如果对于序列中任意两个对象如果对于序列中任意两个对象 R Ri i 和和和和 R Rj j (0(0 i i j j n-n-1)1)都满足：都满足：都满足：都满足：则称序列对关键字则称序列对关键字则称序列对关键字则称序列对关键字 (K K1 1,K K2 2,K Kd d)有序。其中，有序。其中，有序。其中，有序。其中，K K1 1 称为最高位关键字，称为最高位关键字，称为最高位关键字，称为最高位关键字，K Kd d 称为最低位关键字。称为最低位关键字。称为最低位关键字。称为最低位关键字。42课程代码：0600060设置设置设置设置 rd rd 个箱子个箱子个箱子个箱子首首首首先先先先按按按按 分分分分量量量量的的的的取取取取值值值值，将将将将记记记记录录录录“分分分分配配配配”到到到到不不不不同同同同箱箱箱箱子子子子中中中中去去去去。然然然然后后后后扫扫扫扫描描描描n n 个个个个纪纪纪纪录录录录，按按按按箱箱箱箱子子子子的的的的序序序序号号号号依依依依次次次次将将将将各各各各非非非非空空空空箱箱箱箱子子子子中中中中的的的的记记记记录录录录“收收收收集集集集”起起起起来来来来，这这这这样样样样所所所所有有有有对象按取值对象按取值对象按取值对象按取值 排序完成。排序完成。排序完成。排序完成。一趟箱排序一趟箱排序一趟箱排序一趟箱排序 依次按依次按依次按依次按 K Ki id-1d-1,K Ki id-2d-2,K Ki i1 1 的值重复上步，直到最后一趟的值重复上步，直到最后一趟的值重复上步，直到最后一趟的值重复上步，直到最后一趟对对对对K Ki i1 1“分配分配分配分配”、“收集收集收集收