数据结构排序.ppt

第第1010章章 内部排序内部排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 堆排序堆排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种排序方法的综合比较各种排序方法的综合比较10.1 概概 述述一、排序的定义一、排序的定义二、内部排序和外部排序二、内部排序和外部排序三、内部排序方法的分类三、内部排序方法的分类一、什么是排序？一、什么是排序？　排序是计算机内经常进行的一种操作，其目的是将一组“无序无序”的记录序列调的记录序列调整为整为“有序有序”的记录序列例如：将下列关键字序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为14, 23, 36, 49, 52, 58, 61 ,75, 80, 971. 什么是排序？什么是排序？ 将一组杂乱无章的将一组杂乱无章的数据数据按一定的按一定的规律规律顺次排列起来顺次排列起来 2. 排序的目的是什么？排序的目的是什么？存放在数据表中存放在数据表中按关键字排序按关键字排序3.3.排序算法的好坏如何衡量？排序算法的好坏如何衡量？•时间效率时间效率——排序速度（即排序所花费的全部比较次数）排序速度（即排序所花费的全部比较次数）•空间效率空间效率——占内存辅助空间的大小占内存辅助空间的大小•稳稳定定性性——若若两两个个记记录录A A和和B B的的关关键键字字值值相相等等，，但但排排序序后后A A、、B B的先后次序保持不变，则称这种排序算法是稳定的。

的先后次序保持不变，则称这种排序算法是稳定的 ——便于查找！便于查找！二、内部排序和外部排序二、内部排序和外部排序　若待排序记录都在内存中，整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序内部排序； 　 　 反之，若参加排序的记录数量很大， 整个序列的排序过程不可能在内存中 完成，则称此类排序问题为外部排序外部排序三、内部排序的方法三、内部排序的方法 内部排序的过程是一个逐步扩大逐步扩大记录的有序序列长度有序序列长度的过程经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区　基于不同的“扩大扩大” 有序序列长度的方法，内部排序方法方法，内部排序方法大致可分下列几种类型：插入类插入类交换类交换类选择类选择类 归并类归并类基数排序基数排序待排记录的数据类型定义如下待排记录的数据类型定义如下:#define MAXSIZE 1000 // 待排顺序表最大长度待排顺序表最大长度typedef int KeyType; // 关键字类型为整数类型关键字类型为整数类型typedef struct { KeyType key; // 关键字项关键字项 InfoType otherinfo; // 其它数据项其它数据项} RcdType; // 记录类型记录类型typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置闲置 int length; // 顺序表长度顺序表长度} SqList; // 顺序表类型顺序表类型1. 插入类插入类　　将无序子序列中的一个或几个记录“插入插入”到有序序列中，从而增加记录的有序子序列的长度。

2. 交换类交换类　　通过“交换交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度3. 选择类选择类　　从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度4. 归并类归并类　通过“归并归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度 10. 2 插插 入入 排排 序序插入排序的基本思想是：插入排序的基本思想是： 每步将一个待排序的对象，按其关键码大小，每步将一个待排序的对象，按其关键码大小，插入到前面插入到前面已经排好序的一组对象已经排好序的一组对象的的适当位置适当位置上上，直，直到对象全部插入为止到对象全部插入为止简言之，边插入边排序，保证子序列中随时都是排好序的简言之，边插入边排序，保证子序列中随时都是排好序的有序序列R[1..i-1]R[i]无序序列 R[i..n]一趟直接插入排序的基本思想：有序序列R[1..i]无序序列 R[i+1..n]实现实现“一趟插入排序一趟插入排序”可分三步进行：可分三步进行：3．．将R[i] 插入插入(复制)到R[j+1]的位置上。

2．．将R[j+1..i-1]中的所有记录记录均后移后移 一个位置；1．．在R[1..i-1]中查找查找R[i]的插入位置， R[1..j].key   R[i].key < R[j+1..i-1].key；直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）表插入排序表插入排序（基于链表存储）（基于链表存储）不同的具体实现方法导致不同的算法描述不同的具体实现方法导致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）小改进小改进大改进大改进1) 直接插入排序直接插入排序新元素插入到哪里？新元素插入到哪里？例例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, 9, 11，，13，，27, 31】】 在已形成的在已形成的有序表中有序表中线性查找线性查找，并在，并在适当位置插入，把原来位置上的元素向后适当位置插入，把原来位置上的元素向后顺移顺移。

最简单的排序法！最简单的排序法！最简单的排序法！最简单的排序法！一、直接插入排序一、直接插入排序　　利用 “顺序查找顺序查找”实现“在R[1..i-1]中查找查找R[i]的插入位置”算法的实现要点：算法的实现要点：从R[i-1]起向前进行顺序查找， 监视哨设置在R[0]；R[0] = R[i]; // 设置“哨兵”循环结束表明R[i]的插入位置为 j +1R[0]jR[i]for (j=i-1; R[0].key

for ( i=2; i<=L.length; ++i ) if (L.r[i].key < L.r[i-1].key) { }} // InsertSortL.r[0] = L.r[i]; // 复制为监视哨for ( j=i-1; L.r[0].key < L.r[j].key; -- j ) L.r[j+1] = L.r[j]; // 记录后移L.r[j+1] = L.r[0]; // 插入到正确位置例例2 2：：关键字序列关键字序列T= （（21，，25，，49，，25*，，16，，08），），请写出直接插入排序的具体实现过程请写出直接插入排序的具体实现过程 *表示后一个表示后一个2525i i=1=121212525494925*25*161608080 1 2 3 4 5 6哨哨兵兵2121i i=2=2i i=3=3i i=5=5i i=4=4i i=6=62525494925*25*25*494916161625*25*0808084949解：解：假设该序列已存入一维数组假设该序列已存入一维数组r[7]r[7]中，将中，将r[0]r[0]作为哨兵作为哨兵（（TempTemp）。

则程序执行过程为：）则程序执行过程为：21212525494925*25*2121初态：初态：1616494925*25*2525212116160808完成!时间效率：时间效率： 因为在最坏情况下，所有元素的比较次数总和为因为在最坏情况下，所有元素的比较次数总和为（（0 0＋＋1 1＋＋…＋＋n-1)→O(nn-1)→O(n2 2) )其他情况下也要考虑其他情况下也要考虑移动元素的次数移动元素的次数 故时间复杂度为故时间复杂度为O(nO(n2 2) ) 空间效率：空间效率：仅占用仅占用1 1个缓冲单元个缓冲单元——O O O O（（（（1 1 1 1））））算法的稳定性：算法的稳定性：因为因为2525* *排序后仍然在排序后仍然在2525的后面的后面——稳定稳定稳定稳定内部排序的时间分析时间分析：实现内部排序的基本操作基本操作有两个：（2）“移动移动”记录1）“比较比较”序列中两个关键字的 大小；对于直接插入排序：最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记录序列中顺序有序）：“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）：“比较”的次数：0“移动”的次数：“移动”的次数：时间复杂度为时间复杂度为O(nO(n2 2) )2）） 折半插入排序折半插入排序优点：优点：比较次数大大减少，全部元素比较次数仅为比较次数大大减少，全部元素比较次数仅为O O( (n nloglog2 2n)n)。

时时间间效效率率：：虽虽然然比比较较次次数数大大大大减减少少，，可可惜惜移移动动次次数数并并未未减减少少，， 所以排序效率仍为所以排序效率仍为O(nO(n2 2) ) 空间效率：空间效率：仍为仍为 O O（（1 1））稳稳 定定 性：性： 稳定稳定一个的改进方法：一个的改进方法：思考：折半插入排序还可以改进吗？思考：折半插入排序还可以改进吗？ 能否减少移动次数？能否减少移动次数？ 既然子表有序且为顺序存储结构，既然子表有序且为顺序存储结构，则插入时采用则插入时采用折半查找折半查找定可加速定可加速3）希尔（）希尔（shell）排序）排序基本思想基本思想：先将整个待排记录序列分割成若干子序列：先将整个待排记录序列分割成若干子序列, ,分别进分别进行直接插入排序，待整个序列中的记录行直接插入排序，待整个序列中的记录“基本有序基本有序”时，再时，再对全体记录进行一次直接插入排序对全体记录进行一次直接插入排序技巧：技巧：子序列的构成不是简单地子序列的构成不是简单地“逐段分割逐段分割”，而是将相隔，而是将相隔某个增量某个增量dkdk的记录组成一个子序列的记录组成一个子序列, ,让增量让增量dkdk逐趟缩短（例如逐趟缩短（例如依次取依次取5,3,15,3,1），直到），直到dkdk＝＝1 1为止。

为止优点：优点：让关键字值小的元素能很快前移，且序列若基本有序让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多时，再用直接插入排序处理，时间效率会高很多又称缩小增量排序又称缩小增量排序38例：例：关键字序列关键字序列 T=(49，，38，，65，，97, 76, 13, 27, 49*，，55, 04），），请写出希尔排序的具体实现过程请写出希尔排序的具体实现过程(dk=5,3,1) 0123456789104938659776132749*5504初态：初态：第第1趟趟 (dk=5)第第2趟趟 (dk=3)第第3趟趟 (dk=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 算法分析：算法分析：开始时开始时dk 的值较大，子序列中的对象较少，排序速度的值较大，子序列中的对象较少，排序速度较快；随着排序进展，较快；随着排序进展，dk 值逐渐变小，子序列中对象个数值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。

所以排序速度仍然很快r[i]r[i]时间效率：时间效率：空间效率：空间效率： O O O O（（（（1 1 1 1））））——因为仅占用因为仅占用1 1个缓冲单元个缓冲单元算法的稳定性：算法的稳定性：不稳定不稳定不稳定不稳定——因为因为4949* *排序后却到了排序后却到了4949的前面的前面O(O(O(O(n n1.251.25）～）～）～）～O O O O（（（（1.61.6n n1.251.25））））——由经验公式得到由经验公式得到10.3 10.3 交换排序交换排序 两两比较待排序记录的关键码，如果发生逆序两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止直到所有记录都排好序为止交换排序的主要算法有：交换排序的主要算法有： 1) 冒泡排序冒泡排序 2) 快速排序快速排序交换排序的基本思想是：交换排序的基本思想是：一、起泡排序一、起泡排序二、一趟快速排序二、一趟快速排序三、快速排序三、快速排序四、快速排序的时间分析四、快速排序的时间分析一、起泡排序一、起泡排序　　假设在排序过程中，记录序列R[1..n]的状态为：第 i 趟起泡排序无序序列R[1..n-i+1]有序序列 R[n-i+2..n]n-i+1无序序列R[1..n-i]有序序列 R[n-i+1..n]比较相邻记录，将关关键字最大的记录键字最大的记录交换交换到 n-i+1 的位置上 1) 冒泡排序冒泡排序基本思路：基本思路：每趟不断将记录两两比较，并按每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。

规则交换优点：优点：每趟结束时，能挤出一个最大值到最后面位置，一每趟结束时，能挤出一个最大值到最后面位置，一旦下趟没有交换发生，还可以旦下趟没有交换发生，还可以提前结束排序提前结束排序前提：前提：顺序存储结构顺序存储结构 例：例：关键字序列关键字序列 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趟趟void BubbleSort(Elem R[ ], int n) { { while (i >1) { { } // while} // BubbleSorti = n;i = lastExchangeIndex; // 本趟进行过交换的 // 最后一个记录的位置 if (R[j+1].key < R[j].key) { { Swap(R[j], R[j+1]); lastExchangeIndex = j; //记下进行交换的记录位置 } } //iffor (j = 1; j < i; j++)lastExchangeIndex = 1;冒泡排序的算法分析冒泡排序的算法分析•最好情况：最好情况：初始排列已经有序，只执行一趟起泡，做初始排列已经有序，只执行一趟起泡，做 n- -1 次关键码比较，不移动对象。

次关键码比较，不移动对象•最坏情形最坏情形：：初始排列逆序，初始排列逆序，算法要执行算法要执行n-1 1趟起泡，第趟起泡，第i趟趟(1  i  n) 做了做了n- i 次关键码比较，执行了次关键码比较，执行了n-i 次对象交换次对象交换因此：因此：时间效率：时间效率：O O（（n n2 2) ) —因为要考虑最坏情况因为要考虑最坏情况空间效率：空间效率：O O（（1 1）） —只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元稳稳 定定 性：性： 稳定稳定 —2525和和2525* *在排序前后的次序未改变在排序前后的次序未改变时间分析时间分析: :最好的情况（关键字在记录序列中顺序有序）：最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡只需进行一趟起泡“比较比较”的次数：的次数：最坏的情况（关键字在记录序列中逆序有序）：最坏的情况（关键字在记录序列中逆序有序）： 需进行需进行n-1趟起泡趟起泡“比较比较”的次数：的次数：0“移动移动”的次数：的次数：“移动移动”的次数：的次数：n-1 冒泡排序的优点：冒泡排序的优点：冒泡排序的优点：冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一每一趟整理元素时，不仅可以完全确定一个元素的位置（挤出一个泡到表尾），个元素的位置（挤出一个泡到表尾），一旦下趟没有交换一旦下趟没有交换发生，还可以提前结束排序。

发生，还可以提前结束排序有没有比冒泡排序更快的算法？有没有比冒泡排序更快的算法？有！有！快速排序法快速排序法——全球公认！全球公认！因为它每趟都能准确定位不止因为它每趟都能准确定位不止1 1个个元素！元素！2）） 快速排序快速排序从待排序列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素 ( ( ( (例如取第一个例如取第一个例如取第一个例如取第一个) ) ) ) 作为中心，作为中心，作为中心，作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，所有比它小的元素一律前放，所有比它大的元素一律后放，所有比它小的元素一律前放，所有比它大的元素一律后放，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；形成左右两个子表；形成左右两个子表；形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直然后再对各子表重新选择中心元素并依此规则调整，直然后再对各子表重新选择中心元素并依此规则调整，直然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个此时便为有序序列了到每个子表的元素只剩一个此时便为有序序列了。

到每个子表的元素只剩一个此时便为有序序列了到每个子表的元素只剩一个此时便为有序序列了基本思想：基本思想：优点：优点：因为每趟可以确定不止一个元素的位置，而且呈指数增因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！加，所以特别快！ 前提：前提：顺序存储结构顺序存储结构 stlowhigh设设 R[s]=52 为枢轴为枢轴 将 R[high].key 和 枢轴的关键字进行比较，要求R[high].key ≥ 枢轴的关键字 将 R[low].key 和 枢轴的关键字进行比较，要求R[low].key ≤ 枢轴的关键字high23low80high14low52例如例如R[0]52lowhighhighhighlow 可见，经过“一次划分一次划分” ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整过程中，设立了两个指针： low 和high，它们的初值分别为： s 和 t， 之后逐渐减小 high，增加 low，并保证 R[high].key≥52，和 R[low].key≤52,否则进行记录的“交换”。

int Partition (RedType& R[], int low, int high) { pivotkey = R[low].key; while (low=pivotkey) --high; R[low]←→R[high]; while (low

pivotkey=21pivotkey=21( 08 ，，16 ）） 21 （（ 25* ，， 49，， 25 ））Low=high=Low=high=3 3，，本趟停止，将本趟停止，将中枢点定位并返回位置信息中枢点定位并返回位置信息例例1：：关键字序列关键字序列 T=(21，，25，，49，，25*，，16，，08），计算），计算机如何实现快速排序算法的某机如何实现快速排序算法的某一趟一趟过程？过程？r[i]0123456初态初态21254925*1608第第1趟趟highhighlowlow2125*321082516492525* *跑到了前面，跑到了前面，不稳定不稳定！！设计技巧：设计技巧：交替交替/振荡式逼近振荡式逼近例例2：：以关键字序列（以关键字序列（256，，301，，751，，129，，937，，863，，742，，694，，076，，438）为例，写出执行快速算法的）为例，写出执行快速算法的各趟各趟排排序结束时，关键字序列的状态序结束时，关键字序列的状态原始序列：原始序列： 256256，，301301，，751751，，129129，，937937，，863863，，742742，，694694，，076076，，438438第第1趟趟第第2趟趟第第3趟趟第第4趟趟256256，，301301，，751751，，129129，，937937，，863863，，742742，，694694，，076076，，438438076076076076，，129129，，256256256256，，751751751751，，937937，，863863，，742742，，694694，，301301，，438438意即模拟算法实现步骤意即模拟算法实现步骤256256256256076076301301129129751751256256256256076076076076，，129129，，256256256256，，438438，，301301，，694694，，742742，，694694，，863863，，937937751751751751076076076076，，129129129129，，256256256256，，438438438438，，301301，，694694，，742742，，751751751751，，863863863863，，937937076076076076，，129129129129，，256256256256，，301301，，301301，，694694，，742742，，751751751751，，863863863863，，937937438438438438076076076076，，129129129129，，256256256256，，301301301301，，438438438438，，694694694694，，742742，，751751751751，，863863863863，，937937937937时间效率：时间效率：时间效率：时间效率：O(nlogO(nlogO(nlogO(nlog2 2 2 2n) n) n) n) ——因为每趟确定的元素呈指数增加因为每趟确定的元素呈指数增加因为每趟确定的元素呈指数增加因为每趟确定的元素呈指数增加空间效率：空间效率：空间效率：空间效率：O O O O（（（（loglogloglog2 2 2 2n n n n））））——因为递归要用栈因为递归要用栈因为递归要用栈因为递归要用栈( (存每层存每层lowlow，，highhigh和和pivot)pivot)稳稳稳稳 定定定定 性：性：性：性： 不不不不 稳稳稳稳 定定定定 ——因为有跳跃式交换。

因为有跳跃式交换因为有跳跃式交换因为有跳跃式交换四、快速排序的时间分析四、快速排序的时间分析　　假设一次划分所得枢轴位置 i=k，则对n 个记录进行快排所需时间：　其中 Tpass(n)为对 n 个记录进行一次划分所需时间 若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中任意一值的可能性相同T(n) = Tpass(n) + T(k-1) + T(n-k)设 Tavg(1)≤b则可得结果：结论结论: 快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)由此可得快速排序所需时间的平均值为：10.4 10.4 选择排序选择排序选择排序的基本思想是：选择排序的基本思想是：每一趟在后面每一趟在后面n-i n-i 个个待排记录中选取关键字最小的记录作为有序序待排记录中选取关键字最小的记录作为有序序列中的第列中的第i i 个记录个记录10.4 选择选择 排排 序序简简 单单 选选 择择 排排 序序堆堆 排排 序序树树 形形 选选 择择 排排 序序一、简单选择排序一、简单选择排序思思思思路路路路异异异异常常常常简简简简单单单单：：：：每每每每经经经经过过过过一一一一趟趟趟趟比比比比较较较较就就就就找找找找出出出出一一一一个个个个最最最最小小小小值值值值，，，，与待排序列最前面的位置互换即可。

与待排序列最前面的位置互换即可与待排序列最前面的位置互换即可与待排序列最前面的位置互换即可——首首先先，，在在n个个记记录录中中选选择择最最小小者者放放到到r[1]位位置置；；然然后后，，从从剩剩余余的的n-1个个记记录录中中选选择择最最小小者者放放到到r[2] ]位位置置；；…如如此此进进行行下下去去，，直到全部有序为止直到全部有序为止优点：优点：优点：优点：实现简单实现简单实现简单实现简单缺点：缺点：缺点：缺点：每趟只能确定一个元素，表长为每趟只能确定一个元素，表长为每趟只能确定一个元素，表长为每趟只能确定一个元素，表长为n n n n时需要时需要时需要时需要n-1n-1n-1n-1趟趟趟趟前提：前提：前提：前提：顺序存储结构顺序存储结构顺序存储结构顺序存储结构 一、简单选择排序一、简单选择排序假设排序过程中，待排记录序列的状态为：有序序列R[1..i-1]无序序列 R[i..n] 第 i 趟简单选择排序从中选出关键字最小的记录有序序列R[1..i]无序序列 R[i+1..n]例：例：关键字序列关键字序列T= （（21，，25，，49，，25*，，16，，08），请），请给出简单选择排序的具体实现过程。

给出简单选择排序的具体实现过程原始序列：原始序列： 21，，25，，49，，25*，，16，，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，，25，，49，，25*，，16，，2108，，16, 49，，25*，，25，，2108，，16, 21，，25*，，25，，4908，，16, 21，，25*，，25，，4908，，16, 21，，25*，，25，，49时间效率：时间效率： O(nO(nO(nO(n2 2 2 2) ) ) )——虽移动次数较少，但比较次数仍多虽移动次数较少，但比较次数仍多 空间效率：空间效率：O O O O（（（（1 1 1 1））））——没有附加单元（仅用到没有附加单元（仅用到1 1个个temp)temp)算法的稳定性：算法的稳定性：不稳定不稳定不稳定不稳定——因为排序时，因为排序时，25*25*到了到了2525的前面最小值最小值 0808 与与r[1]r[1]交换位置交换位置讨论讨论：：能否利用（能否利用（或记忆或记忆）首趟的）首趟的n-1n-1次比较次比较所得信息，从而尽量减少后续比较次所得信息，从而尽量减少后续比较次数呢？数呢？ 答答：：能！能！请看请看——锦标赛排序和堆锦标赛排序和堆排序排序二、堆排序二、堆排序堆是满足下列性质的数列{r1, r2, …，rn}：或或堆的定义堆的定义:{12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49}例如例如:是是小顶堆小顶堆{12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49}不是堆不是堆(小顶堆小顶堆)(大顶堆大顶堆)解释：解释：如果让满足以上条件的元素序列如果让满足以上条件的元素序列 （（k1，，k2，，…，，kn）顺次排成一棵）顺次排成一棵完全二叉树，完全二叉树，则则此树的特点是：此树的特点是： 树中所有结点的值均大于（或小于）其左树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（右孩子，此树的根结点（即堆顶即堆顶））必最大必最大（或最小）。

或最小）rir2i r2i+1 若将该数列视作完全二叉树，则 r2i 是 ri 的左孩子； r2i+1 是 ri 的右孩子1236276549817355403498例如例如:是堆是堆14不不08082525464649495858676723456191918585666676765858676723456155557例：例：有序列有序列T1=（（08, 25, 49, 46, 58, 67）和序列）和序列T2=（（91, 85, 76, 66, 58, 67, 55））,判断它们是否判断它们是否 “堆堆”？？堆顶元素取最小值堆顶元素取最小值堆顶元素取最堆顶元素取最大大值值终端结点（即叶子）没有任何子女，无需单独调整终端结点（即叶子）没有任何子女，无需单独调整终端结点（即叶子）没有任何子女，无需单独调整终端结点（即叶子）没有任何子女，无需单独调整步骤：步骤：步骤：步骤：从最后一个从最后一个从最后一个从最后一个非终端结点非终端结点非终端结点非终端结点开始往前逐步调整，让每个双开始往前逐步调整，让每个双开始往前逐步调整，让每个双开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。

亲大于（或小于）子女，直到根结点为止亲大于（或小于）子女，直到根结点为止亲大于（或小于）子女，直到根结点为止2121252525*25*494916160808123456例：例：关键字序列关键字序列T= (21，，25，，49，，25*，，16，，08），请建），请建大根堆大根堆2. 2. 怎样建堆？怎样建堆？解：解：为便于理解，先将原始序列画成完全二叉树的形式：为便于理解，先将原始序列画成完全二叉树的形式： 这样可以很清晰地从这样可以很清晰地从   n/2n/2n/2n/2   开始调整开始调整完全二叉树的第一个非终端结点完全二叉树的第一个非终端结点完全二叉树的第一个非终端结点完全二叉树的第一个非终端结点编号必为编号必为编号必为编号必为   n/2n/2n/2n/2    ！！！！！！！！( ( ( (性质性质性质性质5)5)5)5)2121i=3:i=3:4949而且而且21还应当向下比较！！还应当向下比较！！ 49大于大于08，不必调整；，不必调整；i=2:i=2: 25大于大于25*和和16，也不必调整；，也不必调整；i=1:i=1: 21小于小于25和和49，要调整！，要调整！　堆排序即是利用堆排序即是利用堆的特性堆的特性对记录序列对记录序列进行排序的一种排序方法。

进行排序的一种排序方法例如：例如：建大顶堆{ 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 }{ 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 }交换 98 和 12重新调整为大顶堆{ 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 }{ 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 }经过筛选难点：难点：将堆的当前顶点输出后，如何将剩余序列将堆的当前顶点输出后，如何将剩余序列将堆的当前顶点输出后，如何将剩余序列将堆的当前顶点输出后，如何将剩余序列重新调整为堆？重新调整为堆？重新调整为堆？重新调整为堆？方法：方法：将当前顶点将当前顶点将当前顶点将当前顶点与堆尾记录交换与堆尾记录交换，然后，然后，然后，然后仿建堆仿建堆仿建堆仿建堆动作动作动作动作重新调整，如此反复直至排序结束重新调整，如此反复直至排序结束重新调整，如此反复直至排序结束重新调整，如此反复直至排序结束3. 3. 怎样进行整个序列的堆排序？怎样进行整个序列的堆排序？即：将任务转化为即：将任务转化为—>H.r[i…m]中除中除r[i]外，其他都具有堆特征。

外，其他都具有堆特征现调整现调整r[i]的值的值 ，使，使H.r[i…m]为堆基于初始堆进行堆排序的算法步骤：基于初始堆进行堆排序的算法步骤：堆的第一个对象堆的第一个对象堆的第一个对象堆的第一个对象r r[0][0]具有最大的关键码，将具有最大的关键码，将具有最大的关键码，将具有最大的关键码，将r r[0][0]与与与与r r[ [n n] ]对调，把具有最大关键码的对象交换到对调，把具有最大关键码的对象交换到对调，把具有最大关键码的对象交换到对调，把具有最大关键码的对象交换到最后最后最后最后; ;再对前面的再对前面的再对前面的再对前面的n n-1-1个对象，使用堆的调整算法，个对象，使用堆的调整算法，个对象，使用堆的调整算法，个对象，使用堆的调整算法，重新建立堆结果具有次最大关键码的对象又上重新建立堆结果具有次最大关键码的对象又上重新建立堆结果具有次最大关键码的对象又上重新建立堆结果具有次最大关键码的对象又上浮到堆顶，即浮到堆顶，即浮到堆顶，即浮到堆顶，即r r[0][0]位置位置位置位置; ;再对调再对调再对调再对调r r[0][0]和和和和r r[ [n-n-1 1] ]，然后对前，然后对前，然后对前，然后对前n n-2-2个对象重新个对象重新个对象重新个对象重新调整，调整，调整，调整，……如此反复，最后得到全部排序好的对象如此反复，最后得到全部排序好的对象如此反复，最后得到全部排序好的对象如此反复，最后得到全部排序好的对象序列序列序列序列。

如何如何“建堆建堆”？？两个问题两个问题:如何如何“筛选筛选”？？定义堆类型为定义堆类型为:typedef SqList HeapType; // 堆采用顺序表表示之所谓“筛选筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整调整”根结根结点点使整个二叉树也成为一个堆堆堆筛筛选选98814973556412362740例如例如:是大顶堆是大顶堆12但在 98 和 12 进行互换之后，它就不不是堆了，因此，需要对它进行“筛选”98128173641298比较比较比较void HeapAdjust (RcdType &R[], int s, int m){ // 已知 R[s..m]中记录的关键字除 R[s] 之外均 // 满足堆的特征，本函数自上而下调整 R[s] 的 // 关键字，使 R[s..m] 也成为一个大顶堆} // HeapAdjustrc = R[s]; // 暂存 R[s] for ( j=2*s; j<=m; j*=2 ) { // j 初值指向左孩子 自上而下的筛选过程自上而下的筛选过程;}R[s] = rc; // 将调整前的堆顶记录插入到 s 位置if ( rc.key >= R[j].key ) break; // 再作“根”和“子树根”之间的比较， // 若“>=”成立，则说明已找到 rc 的插 // 入位置 s ，不需要继续往下调整R[s] = R[j]; s = j; // 否则记录上移，尚需继续往下调整if ( j

的过程40554973816436122798例如例如: 排序之前的关键字序列为123681734998817355 现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可98494064361227堆排序的时间复杂度分析：堆排序的时间复杂度分析：1. 对深度为 k 的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；3. 调整“堆顶” n-1 次，总共进行的关键 字比较的次数不超过 2 ( log2(n-1) +  log2(n-2) + …+log22) < 2n( log2n ) 因此，堆排序的时间复杂度为O(nlogn)2. 对 n 个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多 4n；堆排序算法分析：堆排序算法分析：•空间效率：空间效率：O(1)仅在第二个仅在第二个for循环中交循环中交换记录时用到一个临时变量换记录时用到一个临时变量temptemp•稳定性：稳定性： 不稳定•优点：优点：对小文件效果不明显，但对大文件对小文件效果不明显，但对大文件有效10.5 归归 并并 排排 序序　　归并排序的过程基于下列基本思想基本思想进行： 将两个或两个以上的有序子序列 “归并” 为一个有序序列。

　　在内部排序中，通常采用的是2-路归并排序即：将两个位置相邻位置相邻的记录有序子序列归并为一个一个记录的有序序列有有 序序 序序 列列 R[l..n]有序子序列有序子序列 R[l..m]有序子序列有序子序列 R[m+1..n]这个操作对顺序表而言，是轻而易举的void Merge (RcdType SR[], RcdType &TR[], int i, int m, int n) { // 将有序的记录序列 SR[i..m] 和 SR[m+1..n] // 归并为有序的记录序列 TR[i..n]} // Mergefor (j=m+1, k=i; i<=m && j<=n; ++k) { // 将SR中记录由小到大地并入TR if (SR[i].key<=SR[j].key) TR[k] = SR[i++]; else TR[k] = SR[j++]; } … … if (i<=m) TR[k..n] = SR[i..m]; // 将剩余的 SR[i..m] 复制到 TRif (j<=n) TR[k..n] = SR[j..n]; // 将剩余的 SR[j..n] 复制到 TR更实际的意义：更实际的意义：可以把一个长度为可以把一个长度为n n 的无序序列看的无序序列看成是成是 n n 个长度为个长度为 1 1 的有序子序列的有序子序列 ，首先做两两，首先做两两归并，得到归并，得到  n n / 2/ 2  个长度为个长度为 2 2 的有序子序列的有序子序列 ；；再做两两归并，再做两两归并，…，如此重复，直到最后得到一个，如此重复，直到最后得到一个长度为长度为 n n 的有序序列。

的有序序列例：例：例：例：关键字序列关键字序列T= （（21，，25，，49，，25*，，93，，62，，72，，08，，37，，16，，54），请给出归并排序的具体实），请给出归并排序的具体实现过程lenlen=1=1lenlen=2=2lenlen=4=4lenlen=8=8lenlen=16=16整个归并排序仅需整个归并排序仅需整个归并排序仅需整个归并排序仅需   loglog2 2n n    趟趟趟趟归并排序算法分析：归并排序算法分析：• 时间效率：时间效率： O(O(n nloglog2 2n n) )因为在递归的归并排序算法中，函数因为在递归的归并排序算法中，函数Merge( )做一趟两路归做一趟两路归并排序，需要调用并排序，需要调用merge ( )函数函数  n/(2len)    O(n/len) 次，而次，而每次每次merge( )要执行比较要执行比较O(len)次，另外整个归并过程有次，另外整个归并过程有 log2n  “层层” ，所以算法总的时间复杂度为，所以算法总的时间复杂度为O(nlog2n)• 空间效率：空间效率： O(O(n n) ) 因为需要一个与原始序列同样大小的辅助序列（因为需要一个与原始序列同样大小的辅助序列（TR）。

这）这正是此算法的缺点正是此算法的缺点• 稳定性：稳定性：稳定稳定稳定稳定10.6 基基 数数 排排 序序　基数排序基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法多关键字的排序多关键字的排序链式基数排序链式基数排序一、多关键字的排序一、多关键字的排序 n 个记录的序列个记录的序列 { R1, R2, …，，Rn}对关键字对关键字 (Ki0, Ki1,…, ,Kid-1) ) 有序有序是指： 其中其中: : K0 被称为被称为 “最主最主”位关键字位关键字Kd-1 被称为被称为 “最次最次”位关键字位关键字 对于序列中任意两个记录 Ri 和 Rj(1≤i

 先对 Kd-1 进行排序，然后对 Kd-2 进行排序，依次类推，直至对最主位直至对最主位关键字关键字 K0 排序完成为止排序完成为止 排序过程中不需要根据 “前一个” 关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列　　　　例如例如: :学生记录含三个关键字:系别系别、班号班号和班内的序列号班内的序列号，其中以系别为最主位关键字 无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下:二、链式基数排序二、链式基数排序　　假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配分配- -收集收集”的方法，其好处是不需要进行关键字间的比较　　对于数字型或字符型的单关键字单关键字，可以看成看成是由多个数位或多个字符构成的多多关键字关键字，此时可以采用采用这种“分配分配- -收集收集”的办法进行排序进行排序，称作基数排序法称作基数排序法。

例如：例如：对下列这组关键字 {209, 386, 768, 185, 247, 606, 230, 834, 539 } 首先按其 “个位数” 取值分别为 0, 1, …, 9　 “分配分配” 成 10 组，之后按从 0 至 9 的顺序将 它们 “收集收集” 在一起； 然后按其 “十位数” 取值分别为 0, 1, …, 9 “分配分配” 成 10 组，之后再按从 0 至 9 的顺序将它们 “收集收集” 在一起；最后按其“百位数”重复一遍上述操作　　在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为： １．１．待排序记录以指针相链，构成一个链表；２２．．“分配” 时，按当前“关键字位”所取值，将记录分配到不同的 “链队列” 中，每个队列中记录的 “关键字位” 相同；３３．．“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表;４．４．对每个关键字位均重复 2) 和 3) 两步例如：p→369→367→167→239→237→138→230→139进行第一次分配进行第一次分配进行第一次收集进行第一次收集f[0] r[0]f[7] r[7]f[8] r[8]f[9] r[9]p→230→230←→367 ←→167→237→367→167→237→138→368→239→139→369 ←→239→139→138←进行第二次分配进行第二次分配p→230→237→138→239→139p→230→367→167→237→138→368→239→139f[3] r[3]f[6] r[6]→230 ←→237→138→239→139→367 ←→167→368→367→167→368进行第二次收集 进行第三次收集之后便得到记录的有序序列进行第三次收集之后便得到记录的有序序列f[1] r[1]p→230→237→138→239→139→367→167→368进行第三次分配进行第三次分配f[2] r[2]f[3] r[3]→138 ←→139→167→230 ←→237→239→367 ←→368p→138→139→167→230→237→239→367→368提醒注意：提醒注意：１．１．“分配分配”和和“收集收集”的实际操作的实际操作仅为修改链表中的指针和设置队列的仅为修改链表中的指针和设置队列的头、尾指针；头、尾指针；２．为查找使用，该链表尚需应用算２．为查找使用，该链表尚需应用算法法Arrange 将它调整为有序表。

将它调整为有序表 基数排序的时间复杂度为基数排序的时间复杂度为O(d(n+rd))其中：分配为O(n) 　 收集为O(rd)(rd为“基”) 　 d为“分配-收集”的趟数10.7 各种排序方法的综合比较各种排序方法的综合比较一、时间性能一、时间性能1. 平均的时间性能平均的时间性能基数排序基数排序时间复杂度为时间复杂度为 O(nlogn)：：快速排序、堆排序和归并排序快速排序、堆排序和归并排序时间复杂度为时间复杂度为 O(n2)：：直接插入排序、起泡排序和直接插入排序、起泡排序和简单选择排序简单选择排序时间复杂度为时间复杂度为 O(n):2. 当待排记录序列按关键字顺序有序时当待排记录序列按关键字顺序有序时3. 简单选择排序、堆排序和归并排序简单选择排序、堆排序和归并排序的时间性能不随不随记录序列中关键字的分布而改变 直接插入排序直接插入排序和起泡排序起泡排序能达到O(n)的时间复杂度， 快速排序快速排序的时间性能蜕化为O(n2) 二、空间性能二、空间性能指的是排序过程中所需的辅助空间大小1. 所有的简单排序方法简单排序方法(包括：直接插入、起泡和简单选择) 和堆排序堆排序的空间复杂度为为O(1)；2. 快速排序为快速排序为O(logn)，，为递归程序执行过程中，栈所需的辅助空间；3. 归并排序归并排序所需辅助空间最多，其空间复杂度为 O(n);4. 链式基数排序链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。

三、排序方法的稳定性能三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法排序之前 : { · · · · · Ri(K) · · · · · Rj(K) · · · · · }排序之后 : { · · · · · Ri(K) Rj(K) · · · · ·· · · · · }例如：例如： 排序前 ( 56, 34, 47, 23, 66, 18, 82, 47 )若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )则称该排序方法是稳定稳定的;若排序后得到结果 ( 18, 23, 34, 47, 47, 56, 66, 82 )则称该排序方法是不稳定不稳定的 3. 对于不稳定的排序方法，只要能举出一个实例说明即可 4. 快速排序、堆排序和希尔排序是不稳快速排序、堆排序和希尔排序是不稳定的排序方法定的排序方法例如例如 : 对 { 4, 3, 4, 2 } 进行快速排序， 得到 { 2, 3, 4, 4 }四、关于四、关于“排序方法的时间复杂度的下限排序方法的时间复杂度的下限” 本章讨论的各种排序方法，除基数排序外，其它方法都是基于基于“比较关键字比较关键字”进进行排序的排序方法。

行排序的排序方法 可以证明， 这类排序法可能达到的最可能达到的最快的时间复杂度为快的时间复杂度为O(nlogn) (基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制) 例如:对三个关键字进行排序的判定树如下：K1

 １．１．按可用内存大小，利用内部排序 方法，构造若干( 记录的) 有序子序列，通常称外存中这些记录有序子序列为 “归并段归并段”；二、外部排序的基本过程二、外部排序的基本过程由相对独立的两个步骤组成： ２．２．通过“归并归并”，逐步扩大 (记录的)有序子序列的长度，直至外存中整个记录序列按关键字有序为止例如：例如：假设有一个含10,000个记录的磁盘 文件，而当前所用的计算机一次只 能对1000个记录进行内部排序，则 首先利用内部排序的方法得到10个 初始归并段，然后进行逐趟归并假设进行2路归并(即两两归并)，则第一趟第一趟由10个归并段得到5个归并段；最后一趟最后一趟归并得到整个记录的有序序列第三趟第三趟由 3 个归并段得到2个归并段；第二趟第二趟由 5 个归并段得到3个归并段；假设“数据块”的大小为200，即每一次访问外存可以读/写200个记录则对于10,000个记录，处理一遍需访问外存100次(读和写各50次)分析上述外排过程中访问外存(对外存进行读/写)的次数：由此，对上述例子而言，•1)求得10个初始归并段需访问外存100次；•2)每进行一趟归并需访问外存100次；•3)总计访问外存 100 + 4  100 = 500次。

 外排总的时间还应包括内部排序所需时间和逐趟归并时进行内部归并的时间，显然，除去内部排序的因素外，外部排序的时间取决于逐趟归并外部排序的时间取决于逐趟归并所需进行的所需进行的“趟数趟数”例如例如，若对上述例子采用5路归并，则只需进行2趟归并，总的访问外存的次数将压缩到 100 + 2  100 = 300 次 一般情况下，假设待排记录序列含含 m 个初始归并段个初始归并段，外排时采用 k 路路归并归并，则归并趟数归并趟数为  logkm ，显然，随之k的增大归并的趟数将减少，因此对外排而言，通常采用多路归并k 的大小可选，但需综合考虑各种因素 1. 了解排序的定义定义和各种排序方法的特点熟悉各种方法的排序过程及其依方法的排序过程及其依据的原则据的原则基于“关键字间的比较关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序插入排序、交换排序交换排序、选选择排序择排序、归并排序归并排序和计数排序等五类 2. 掌握各种排序方法的时间复杂度时间复杂度的分析方法能从“关键字间的比较关键字间的比较次数次数”分析排序算法的平均平均情况和最最坏坏情况的时间性能。

按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(nlogn)的高效排序方法 和 O(dn)的基数排序方法 3．．理解排序方法“稳定稳定”或“不稳定不稳定”的含义，弄清楚在什么情况下什么情况下要求应用的排序方法必须是稳定的 4. 了解外部排序的基本过程及其时间分析 衷心感谢全体同学的支持和配合，衷心感谢全体同学的支持和配合，使我能圆满完成本课程的教学任务使我能圆满完成本课程的教学任务 希望大家顺利通过课程考试希望大家顺利通过课程考试。