数据结构第章内部排序课件

第第10章章 内部排序内部排序 讨论各种内部排序方法：插入排序、交各种内部排序方法：插入排序、交换排序、排序、选择排序、排序、归并排序和基数排序的基本思想、并排序和基数排序的基本思想、算法特点、排序算法特点、排序过程以及程以及时间复复杂性的分析。比性的分析。比较各种内部排序方法。各种内部排序方法。1目目 录10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 选择排序排序10.5 归并排序并排序10.6 基数排序基数排序10.7 各种内部排序方法的比各种内部排序方法的比较讨论2 排序（排序（sorting）1.基本概念基本概念 将一个数据元素（或将一个数据元素（或记录）的任意序列，重新排列成）的任意序列，重新排列成一个按关一个按关键字有序的序列。字有序的序列。假假设含含n个个记录的序列的序列为 R1，R2，Rn (）其相其相应的关的关键字序列字序列为 K1，K2，Kn 10.1 概述概述3需确定需确定1，2，n的一种排列的一种排列p1，p2，pn，使其相，使其相应的关的关键字字满足如下的非足如下的非递减（或非减（或非递增）关系增）关系 Kp1 Kp2 Kpn即使序列即使序列(）成）成为一个按关一个按关键字有序的序列字有序的序列 Rp1，Rp2，Rpn这种操作种操作过程称程称为排序。排序。排序排序(接上接上页)基本概念基本概念4基本概念基本概念 排序方法是排序方法是稳定的定的 设 Ki=Kj（l i n，1 j n，ij），且在排序前），且在排序前的序列中的序列中 Ri领先于先于 Rj（即（即 ij），在排序后的序列中），在排序后的序列中 Ri仍仍领先于先于 Rj。排序方法是不排序方法是不稳定的定的 设 Ki=Kj（l i n，1 j n，ij），且在排序前），且在排序前的序列中的序列中 Ri领先于先于 Rj（即（即 ij），在排序后的序列中），在排序后的序列中 Rj领先于先于 Ri。52.排序方法分排序方法分类 按照文件所按照文件所处的位置不同：的位置不同：内部排序内部排序 待排序待排序记录存放在存放在计算机内存中算机内存中进行的排序行的排序过程。程。外部排序外部排序 排序排序过程中有内、外存程中有内、外存间信息的信息的传递及交及交换的排序的排序过程。程。6排序方法分排序方法分类 按排序按排序时使用的原理使用的原理 插入排序、交插入排序、交换排序、排序、选择排序、排序、归并排序、基数并排序、基数排序。排序。按照所需的工作量按照所需的工作量简单的排序方法，其的排序方法，其时间复复杂度度为O（n2）；）；先先进的排序方法，其的排序方法，其时间复复杂度度为O（nlogn）；）；基数排序，其基数排序，其时间复复杂度度为O（d n）。）。73.基本操作基本操作 比比较两个关两个关键字的大小；字的大小；将将记录从一个位置从一个位置移移动至另一个位置。至另一个位置。84.存存储结构构（1）以一）以一维数数组作作为存存储结构构（2）以静）以静态链表作表作为存存储结构（构（链表排序）表排序）（3）采用）采用辅助表排序（地址排序）助表排序（地址排序）待排序待排序记录存存储在数在数组中，同中，同时另另 设一个指示各个一个指示各个记录存存储位置的地址向量。在排序位置的地址向量。在排序过程中不移程中不移动记录本身，而本身，而移移动地址向量中地址向量中这些些记录的的 “地址地址”，排序，排序结束后再按照地束后再按照地址向量中的址向量中的值调整整记录的存的存储位置。位置。9 5.排序方法分析排序方法分析n n排序的排序的排序的排序的时间时间开开开开销销:排序的排序的排序的排序的时间时间开开开开销销是衡量算法好坏的最重要的是衡量算法好坏的最重要的是衡量算法好坏的最重要的是衡量算法好坏的最重要的标标志。排序的志。排序的志。排序的志。排序的时间时间开开开开销销可用算法可用算法可用算法可用算法执执行中的数据比行中的数据比行中的数据比行中的数据比较较次数与数据移次数与数据移次数与数据移次数与数据移动动次数来衡量。次数来衡量。次数来衡量。次数来衡量。n n一般都按平均情况一般都按平均情况一般都按平均情况一般都按平均情况进进行估算。行估算。行估算。行估算。对对于那些受于那些受于那些受于那些受对对象关象关象关象关键键字序列初始排列及字序列初始排列及字序列初始排列及字序列初始排列及对对象个数影响象个数影响象个数影响象个数影响较较大大大大的，需要按最好情况和最坏情况的，需要按最好情况和最坏情况的，需要按最好情况和最坏情况的，需要按最好情况和最坏情况进进行估算。行估算。行估算。行估算。n n衡量排序方法的衡量排序方法的衡量排序方法的衡量排序方法的标标准准准准 排序排序排序排序时时所需要的平均比所需要的平均比所需要的平均比所需要的平均比较较次数次数次数次数 排序排序排序排序时时所需要的平均移所需要的平均移所需要的平均移所需要的平均移动动 排序排序排序排序时时所需要的平均所需要的平均所需要的平均所需要的平均辅辅助存助存助存助存储储空空空空间间101.直接插入排序直接插入排序(Straight Insertion Sort)概念概念 将一个将一个记录插入到已排好序的有序表中，从而得到一插入到已排好序的有序表中，从而得到一个新的、个新的、记录数增数增 1 的有序表。的有序表。例：已排序的一例：已排序的一组记录排列如下：排列如下：12，33，45，57，76现将关将关键字字 40 记录插入上述序列中插入上述序列中12，33，40，45，57，7610.2 插入排序插入排序11 算法的基本思路算法的基本思路直接插入排序直接插入排序 设有有n个待排个待排记录存放在存放在r1.n中，将第中，将第i(2i n)个个记录插入到已排好序的有序表插入到已排好序的有序表r1.i-1中的中的过程程为：从：从ri-1 起往起往前搜索，若前搜索，若ri rj(1j i-1)，则将将rj 向后移向后移动，直至找，直至找到第到第i个个记录的位置。的位置。12 算法算法10.1直接插入排序直接插入排序void InsertSort（SqList&L）for(i=2;i=L.Length;+i)if LT(L.ri.key,L.ri-1.key L.r0=L.ri；L.ri=L.ri-1；for(j=i-2;LT(L.r0.key,L.rj.key);-j）L.rj+l=L.rj;L.rj+l=L.r0;13 例子例子直接插入排序直接插入排序初始关初始关键字：字：(42)41 33 67 74 23 37 33 i=2：(41)(41 42)33 67 74 23 37 33 i=3：(33)(33 41 42)67 74 23 37 33i=4：(33)(33 41 42 67)74 23 37 33i=5：(33)(33 41 42 67 74)23 37 33i=6：(23)(23 33 41 42 67 74)37 33 i=7：(37)(23 33 37 41 42 67 74)33 i=8：(33)(23 33 33 37 41 42 67 74)14时间复复杂性分析性分析直接插入排序直接插入排序n n若若若若设设待排序的待排序的待排序的待排序的对对象个数象个数象个数象个数为为L.lengthL.length=n n，则该则该算法的主程序算法的主程序算法的主程序算法的主程序执执行行行行n n-1-1趟。趟。趟。趟。n n关关关关键键字比字比字比字比较较次数和次数和次数和次数和对对象移象移象移象移动动次数与次数与次数与次数与对对象关象关象关象关键键字的初始排列有关。字的初始排列有关。字的初始排列有关。字的初始排列有关。n n最好情况下，排序前最好情况下，排序前最好情况下，排序前最好情况下，排序前对对象已象已象已象已经经按关按关按关按关键键字大小从小到大有序，每趟只需与前面的有序字大小从小到大有序，每趟只需与前面的有序字大小从小到大有序，每趟只需与前面的有序字大小从小到大有序，每趟只需与前面的有序对对象序象序象序象序列的最后一个列的最后一个列的最后一个列的最后一个对对象的关象的关象的关象的关键键字比字比字比字比较较 1 1 次，次，次，次，总总的关的关的关的关键键字比字比字比字比较较次数次数次数次数为为 n n-1-1，对对象移象移象移象移动动次数次数次数次数为为 0 0。n n最坏情况下，排序前最坏情况下，排序前最坏情况下，排序前最坏情况下，排序前对对象已象已象已象已经经按关按关按关按关键键字大小从大到小有序（逆序），需比字大小从大到小有序（逆序），需比字大小从大到小有序（逆序），需比字大小从大到小有序（逆序），需比较较和移和移和移和移动动次数次数次数次数为为多少？多少？多少？多少？15 直接插入排序直接插入排序时间复复杂性分析性分析n n若待排序若待排序若待排序若待排序对对象序列中出象序列中出象序列中出象序列中出现现各种可能排列的概率相同，各种可能排列的概率相同，各种可能排列的概率相同，各种可能排列的概率相同，则则可取上述最好情况和最坏情况的可取上述最好情况和最坏情况的可取上述最好情况和最坏情况的可取上述最好情况和最坏情况的平均情况。在平均情况下的关平均情况。在平均情况下的关平均情况。在平均情况下的关平均情况。在平均情况下的关键键字比字比字比字比较较次数和次数和次数和次数和对对象移象移象移象移动动次数次数次数次数约为约为 n n2 2/4/4。因此，直接插。因此，直接插。因此，直接插。因此，直接插入排序的入排序的入排序的入排序的时间时间复复复复杂杂度度度度为为 o(o(n n2 2)。n n直接插入排序是一种直接插入排序是一种直接插入排序是一种直接插入排序是一种稳稳定的排序方法。定的排序方法。定的排序方法。定的排序方法。162.其它插入排序其它插入排序 折半插入排序折半插入排序（Binary Insertion Sort）折半插入排序基本思想是：折半插入排序基本思想是：折半插入排序基本思想是：折半插入排序基本思想是：设设在在在在顺顺序表中有一序表中有一序表中有一序表中有一 个个个个对对象序列象序列象序列象序列 V0,V1,vn-1V0,V1,vn-1。其中，其中，其中，其中，v0,V1,vi-1 v0,V1,vi-1 是已是已是已是已经经排好序的排好序的排好序的排好序的对对象。在插入象。在插入象。在插入象。在插入 vivi 时时，利用折半搜索法，利用折半搜索法，利用折半搜索法，利用折半搜索法寻寻找找找找 vivi 的插入位置。的插入位置。的插入位置。的插入位置。2-路插入排序路插入排序 表插入排序表插入排序17n n折半插入排序的算法折半插入排序的算法折半插入排序的算法折半插入排序的算法10.210.2nvoid BInsertSort(SqList&L)n int low,high,mid;n for(int i=2;i=L.length;+i)n L.r0=L.ri;n low=1;high=i-1;n while(low=high+1;-j)L.rj+1=L.rj;n L.rhigh+1=L.r0;nnn说明：low 或者 high+1为插入点 稳定排序18n n算法分析算法分析算法分析算法分析折半折半折半折半查查找比找比找比找比顺顺序序序序查查找快，所以找快，所以找快，所以找快，所以折半折半折半折半插入排序就平均性能来插入排序就平均性能来插入排序就平均性能来插入排序就平均性能来说说比直接插入排序要比直接插入排序要比直接插入排序要比直接插入排序要快。快。快。快。它所需要的关它所需要的关它所需要的关它所需要的关键键字比字比字比字比较较次数与待排序次数与待排序次数与待排序次数与待排序对对象序列的初始排列无关，象序列的初始排列无关，象序列的初始排列无关，象序列的初始排列无关，仅仅依依依依赖赖于于于于对对象象象象个数。在插入第个数。在插入第个数。在插入第个数。在插入第 i i 个个个个对对象象象象时时，需要，需要，需要，需要经过经过 log2ilog2i +1 +1 次关次关次关次关键键字比字比字比字比较较，才能确定它，才能确定它，才能确定它，才能确定它应应插入的位置。因此，将插入的位置。因此，将插入的位置。因此，将插入的位置。因此，将 n n 个个个个对对象（象（象（象（为为推推推推导导方便，方便，方便，方便，设为设为 n=2k)n=2k)用用用用折半折半折半折半插入排序所插入排序所插入排序所插入排序所进进行的关行的关行的关行的关键键字比字比字比字比较较次数次数次数次数为为：1920n n当当当当 n n 较较大大大大时时，总总关关关关键键字字字字比比比比较较次次次次数数数数比比比比直直直直接接接接插插插插入入入入排排排排序序序序的的的的最最最最坏坏坏坏情情情情况况况况要要要要好好好好得得得得多多多多，但但但但比比比比其其其其最最最最好好好好情情情情况要差。况要差。况要差。况要差。n n在在在在对对象象象象的的的的初初初初始始始始排排排排列列列列已已已已经经按按按按关关关关键键字字字字排排排排好好好好序序序序或或或或接接接接近近近近有有有有序序序序时时，直直直直接接接接插插插插入入入入排排排排序序序序比比比比折折折折半半半半插插插插入入入入排排排排序序序序执执行行行行的的的的关关关关键键字字字字比比比比较较次次次次数数数数要要要要少少少少。折折折折半半半半插插插插入入入入排排排排序序序序的的的的对对象象象象移移移移动动次次次次数数数数与与与与直直直直接接接接插插插插入入入入排排排排序序序序相相相相同同同同，依依依依赖赖于于于于对对象的初始排列。象的初始排列。象的初始排列。象的初始排列。n n折半折半折半折半插入排序是一个插入排序是一个插入排序是一个插入排序是一个稳稳定的排序方法。定的排序方法。定的排序方法。定的排序方法。213.希希尔排序排序(Shells Sort)基本思想基本思想 先将整个待排先将整个待排记录序列分割成序列分割成为若干子序列分若干子序列分别进行行直接插入排序，待整个序列中的直接插入排序，待整个序列中的记录“基本有序基本有序”时，再，再对全体全体记录进行一次直接插入排序。行一次直接插入排序。概念概念 希希尔排序又称排序又称“缩小增量排序小增量排序”(Diminishing Increment Sort)属于插入排序属于插入排序类的方法，其的方法，其时间效率上效率上优于前述几种方法。于前述几种方法。22例，初始关例，初始关键字序列字序列为：43 41 33 67 74 23 37 33 47 35d=5 43 2341 3733 3367 4774 35一趟排序的一趟排序的结果：果：23 37 33 47 35 43 41 33 67 74希希尔排序排序 例子例子23 23 37 33 47 35 43 41 33 67 74d=3 23 47 41 7437 35 3333 43 67二趟排序的二趟排序的结果：果：23 33 33 41 35 43 47 37 67 74三趟排序三趟排序(直接插入排序直接插入排序)的的结果：果：23 33 33 35 37 41 43 47 67 74希希尔排序排序24 10.3 交交换排序排序n n交交换换排序排序(Exchange Sort)(Exchange Sort)交交交交换换排序的基本思想是两两比排序的基本思想是两两比排序的基本思想是两两比排序的基本思想是两两比较较待排序待排序待排序待排序对对象的关象的关象的关象的关键键字，如果字，如果字，如果字，如果发发生逆序生逆序生逆序生逆序(即排列即排列即排列即排列顺顺序序序序与排序后的次序正好相反与排序后的次序正好相反与排序后的次序正好相反与排序后的次序正好相反)，则则交交交交换换之，直到所有之，直到所有之，直到所有之，直到所有对对象都排好序象都排好序象都排好序象都排好序为为止。止。止。止。25 基本思想基本思想 将第将第1个个记录的关的关键字和第字和第2个个记录的关的关键字字进行比行比较，若，若为逆序（即逆序（即r1.keyr2.key），），则将两个将两个记录交交换之，然后比之，然后比较第第2个个记录和第和第3个个记录的关的关键字。依次字。依次类推，直至第推，直至第n-1个个记录和第和第n个个记录的关的关键字字进行行过比比较为止。第一趟冒泡排序后，关止。第一趟冒泡排序后，关键字最大的字最大的记录被放到最后一个被放到最后一个记录的位置上。的位置上。对前前n-1个个记录进行同行同样操作，其操作，其结果是使关果是使关键字次大字次大的的记录被安置到第被安置到第 n-1个个记录的位置上。的位置上。1.冒泡排序冒泡排序(Bubble Sort)26 一般地，第一般地，第 i 趟冒泡排序是从趟冒泡排序是从 r1到到 rn-i+1依次比依次比较相相邻两个两个记录的关的关键字，并在字，并在“逆序逆序”时交交换相相邻记录，其，其结果是果是这n-i+1个个记录中关中关键字最大的字最大的记录被交被交换到第到第n-i+1 的位置上。整的位置上。整个排序个排序过程需程需进行行k（1 k 1&change;-I)change=false;for(j=0;jaj+1)aj aj+1;change=TURE 算法复杂性分析：最好情况（正序）：一趟排序，n-1次比较，移动0个记录 最坏情况（逆序）：n-1趟排序，n-1+n-2+1=n(n-1/)/2 次比较,移动n(n-1/)/2个记录 时间复杂度：O(n2)292.快速排序快速排序(Quick Sort)基本思想基本思想 根根据据选定定的的支支点点L，通通过一一趟趟排排序序将将待待排排记录分分割割成成独独立立的的两两部部分分，其其中中一一部部分分记录的的关关键字字均均小小于于L，而而另另一一部部分分记录的的关关键字字均均大大于于等等于于L。分分别对这两两部部分分记录继续进行行排排序，以达到整个序列有序序，以达到整个序列有序。支点的支点的选择方法方法 取第一个取第一个记录；最后一个；最后一个记录；第一个、最后一个和；第一个、最后一个和中中间记录三者中，关三者中，关键字居中的那个字居中的那个记录。30 具体做法具体做法 设待排序的序列待排序的序列为rs，rs+1，rt。附。附设两个指两个指针i和和j，它，它们的初的初值分分别为s和和t，设支点支点记录pivot=rs，x=pivotkey。则首先从首先从j所指位置起向前搜索找到第所指位置起向前搜索找到第一个关一个关键字小于字小于x的的记录和和pivot互相交互相交换，然后从，然后从i所指位置所指位置起向后搜索，找到第一个关起向后搜索，找到第一个关键字大于字大于x的的记录和和pivot互相交互相交换，重复，重复这两步直至两步直至i=j为止。止。快速排序快速排序31 举例例 例，初始关例，初始关键字序列字序列为：43 41 33 67 74 23 37 33 47 35 x=43 初始初始 43 41 33 67 74 23 37 33 47 35 i j 1次次 35 41 33 67 74 23 37 33 47 43 i i j 快速排序快速排序322次次 35 41 33 43 74 23 37 33 47 67 i j 3次次 35 41 33 33 74 23 37 43 47 67 i j j 4次次 35 41 33 33 43 23 37 74 47 67 i i j快速排序快速排序335次次 35 41 33 33 37 23 43 74 47 67 i j j快速排序快速排序5次次 35 41 33 33 37 23 43 74 47 67 i j完成一趟完成一趟 35 41 33 33 37 23 43 74 47 6734快速排序的算法快速排序的算法void QSort(SqList&L,int low,int high)if(low high)int pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);PrintST(L);QSort(L,pivotloc+1,high);PrintST(L);void QuickSort(SqList&L)QSort(L,1,L.length);35int Partition(SqList&L,int low,int high)L.r0=L.rlow;int pivotkey=L.rlow.key;while(low high)while(low=pivotkey)-high;L.rlow=L.rhigh;while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rlow=L.r0;return low;36 算法分析算法分析n n从快速排序算法的从快速排序算法的从快速排序算法的从快速排序算法的递归树递归树可知，快速排序的趟数取决于可知，快速排序的趟数取决于可知，快速排序的趟数取决于可知，快速排序的趟数取决于递归树递归树的深度。的深度。的深度。的深度。n n如果每次划分如果每次划分如果每次划分如果每次划分对对一个一个一个一个对对象定位后，象定位后，象定位后，象定位后，该对该对象的左象的左象的左象的左侧侧子序列与右子序列与右子序列与右子序列与右侧侧子序列的子序列的子序列的子序列的长长度相同，度相同，度相同，度相同，则则下下下下一步将是一步将是一步将是一步将是对对两个两个两个两个长长度减半的子序列度减半的子序列度减半的子序列度减半的子序列进进行排序，行排序，行排序，行排序，这这是最理想的情况。是最理想的情况。是最理想的情况。是最理想的情况。n n在在在在n n个元素的序列中，个元素的序列中，个元素的序列中，个元素的序列中，对对一个一个一个一个对对象定位所需象定位所需象定位所需象定位所需时间为时间为 O(O(n n)。若。若。若。若设设 t(t(n n)是是是是对对 n n 个元素的序列个元素的序列个元素的序列个元素的序列进进行排序所需的行排序所需的行排序所需的行排序所需的时间时间，而且每次，而且每次，而且每次，而且每次对对一个一个一个一个对对象正确定位后，正好把序列划分象正确定位后，正好把序列划分象正确定位后，正好把序列划分象正确定位后，正好把序列划分为长为长度相等的度相等的度相等的度相等的两个子序列，此两个子序列，此两个子序列，此两个子序列，此时时，总总的的的的计计算算算算时间为时间为：37T(T(n n)cncn+2 t(+2 t(n n/2)/2)/c c是一个常数是一个常数是一个常数是一个常数 CnCn+2(+2(cncn/2+2t(/2+2t(n n/4)=2/4)=2cn cn+4t(+4t(n n/4)/4)2 2cn cn+4(+4(cncn/4+2t(/4+2t(n n/8)=3/8)=3cncn+8t(+8t(n n/8)/8)CnCn log log2 2n n+n nt(1)=o(t(1)=o(n n log log2 2n n)n n可可可可以以以以证证明明明明，函函函函数数数数quicksortquicksort的的的的平平平平均均均均计计算算算算时时间间也也也也是是是是o(o(n nloglog2 2n n)。实实验验结结果果果果表表表表明明明明：就就就就平平平平均均均均计计算算算算时时间间而言，快速排序是我而言，快速排序是我而言，快速排序是我而言，快速排序是我们们所所所所讨论讨论的所有内排序方法中最好的一个的所有内排序方法中最好的一个的所有内排序方法中最好的一个的所有内排序方法中最好的一个。38n n快速排序是快速排序是快速排序是快速排序是递归递归的，需要有一个的，需要有一个的，需要有一个的，需要有一个栈栈存放每存放每存放每存放每层递归调层递归调用用用用时时的指的指的指的指针针和参数。和参数。和参数。和参数。n n最最最最大大大大递递归归调调用用用用层层次次次次数数数数与与与与递递归归树树的的的的深深深深度度度度一一一一致致致致，理理理理想想想想情情情情况况况况为为 loglog2 2(n n+1)+1)。因因因因此此此此，要要要要求求求求存存存存储储开开开开销为销为 o(log o(log2 2n n)。n n在在在在最最最最坏坏坏坏的的的的情情情情况况况况，即即即即待待待待排排排排序序序序对对象象象象序序序序列列列列已已已已经经按按按按其其其其关关关关键键字字字字从从从从小小小小到到到到大大大大排排排排好好好好序序序序的的的的情情情情况况况况下下下下，其其其其递递归归树树成成成成为为单单支支支支树树，每每每每次次次次划划划划分分分分只只只只得得得得到到到到一一一一个个个个比比比比上上上上一一一一次次次次少少少少一一一一个个个个对对象象象象的的的的子子子子序序序序列列列列。这这样样，必必必必须须经经过过 n n-1-1 趟趟趟趟才才才才能能能能把把把把所所所所有有有有对对象象象象定定定定位位位位，而而而而且且且且第第第第 i i 趟趟趟趟需需需需要要要要经经过过 n n-i i 次次次次关关关关键键字字字字比比比比较较才才才才能能能能找找找找到到到到第第第第 i i 个个个个对对象的安放位置，象的安放位置，象的安放位置，象的安放位置，总总的关的关的关的关键键字比字比字比字比较较次数将达到次数将达到次数将达到次数将达到39其排序速度退化到其排序速度退化到其排序速度退化到其排序速度退化到简单简单排序的水平，比直接插入排序排序的水平，比直接插入排序排序的水平，比直接插入排序排序的水平，比直接插入排序还还慢。占用附加存慢。占用附加存慢。占用附加存慢。占用附加存储储(即即即即栈栈)将达将达将达将达到到到到o(o(n n)。若能更合理地若能更合理地若能更合理地若能更合理地选择选择基准基准基准基准对对象，使得每次划分所得的两个子序列中的象，使得每次划分所得的两个子序列中的象，使得每次划分所得的两个子序列中的象，使得每次划分所得的两个子序列中的对对象个数尽可能地象个数尽可能地象个数尽可能地象个数尽可能地接近，可以加速排序速度，但是由于接近，可以加速排序速度，但是由于接近，可以加速排序速度，但是由于接近，可以加速排序速度，但是由于对对象的初始排列次序是随机的，象的初始排列次序是随机的，象的初始排列次序是随机的，象的初始排列次序是随机的，这这个要求很个要求很个要求很个要求很难办难办到。到。到。到。有一种改有一种改有一种改有一种改进办进办法：取每个待排序法：取每个待排序法：取每个待排序法：取每个待排序对对象序列的第一个象序列的第一个象序列的第一个象序列的第一个对对象、最后一个象、最后一个象、最后一个象、最后一个对对象和位置接近正象和位置接近正象和位置接近正象和位置接近正中的中的中的中的3 3个个个个对对象，取其关象，取其关象，取其关象，取其关键键字居中者作字居中者作字居中者作字居中者作为为基准基准基准基准对对象。象。象。象。快速排序是一种不快速排序是一种不快速排序是一种不快速排序是一种不稳稳定的排序方法。定的排序方法。定的排序方法。定的排序方法。对对于于于于 n n 较较大的平均情况而言，快速排序是大的平均情况而言，快速排序是大的平均情况而言，快速排序是大的平均情况而言，快速排序是“快速快速快速快速”的，但是当的，但是当的，但是当的，但是当 n n 很小很小很小很小时时，这这种排序方种排序方种排序方种排序方法往往比其它法往往比其它法往往比其它法往往比其它简单简单排序方法排序方法排序方法排序方法还还要慢。要慢。要慢。要慢。40 基本思想基本思想 每一趟在每一趟在 n-i+1（i=1，2，n-1）个）个记录中中选取关取关键字最小的字最小的记录作作为有序序列中第有序序列中第 i 个个记录。分分类 简单选择排序排序 树形形选择排序排序 堆排序堆排序10.4 选择排序排序411.简单选择排序排序(Simple Selection Sort)基本思想基本思想 通通过 n-i次关次关键字字间的比的比较，从，从 n-i+1个个记录中中选出关出关键字最小的字最小的记录，并和第，并和第i（1 i n）个）个记录交交换之（称之（称为一趟一趟简单选择排序）。具体排序）。具体实现时令令 i 从从1至至n-1，进行行n-1次次选择操作。操作。42 算法算法void SelectSort（SqList&L）for(i=1;iL.Length;+i)k=i;for(j=i+1;j=L.Length;+j)if (L.rj.keyL.rk.key)k=j；if(i!=k)L.r0=L.ri;L.ri=L.rk;L.rk=L.r0;简单选择排序排序43简单选择排序排序 举例例4938659776132749初始关键字1338659776492749第一趟排序后1327659776493849第二趟排序后1327389776496549第三趟排序后1327384976976549第四趟排序后1327384949976576第五趟排序后1327384949659776第六趟排序后1327384949657697第七趟排序后44 算法分析算法分析n n直接直接直接直接选择选择排序的关排序的关排序的关排序的关键键字比字比字比字比较较次数次数次数次数KCNKCN与与与与对对象的初始排列无关。第象的初始排列无关。第象的初始排列无关。第象的初始排列无关。第 i i 趟趟趟趟选择选择具有最具有最具有最具有最小关小关小关小关键键字字字字对对象所需的比象所需的比象所需的比象所需的比较较次数次数次数次数总总是是是是 n n-i i-1 1 次，此次，此次，此次，此处处假定整个待排序假定整个待排序假定整个待排序假定整个待排序对对象序列有象序列有象序列有象序列有 n n 个个个个对对象。因此，象。因此，象。因此，象。因此，总总的关的关的关的关键键字比字比字比字比较较次数次数次数次数为为45n n对对象的移象的移象的移象的移动动次数与次数与次数与次数与对对象序列的初始排列有关。当象序列的初始排列有关。当象序列的初始排列有关。当象序列的初始排列有关。当这组对这组对象的初始状象的初始状象的初始状象的初始状态态是按其关是按其关是按其关是按其关键键字从小字从小字从小字从小到大有序的到大有序的到大有序的到大有序的时时候，候，候，候，对对象的移象的移象的移象的移动动次数次数次数次数RMN RMN=0=0，达到最少。，达到最少。，达到最少。，达到最少。n n最坏情况是每一趟都要最坏情况是每一趟都要最坏情况是每一趟都要最坏情况是每一趟都要进进行交行交行交行交换换，总总的的的的对对象移象移象移象移动动次数次数次数次数为为RMNRMN=3(=3(n n-1)1)。n n直接直接直接直接选择选择排序是一种不排序是一种不排序是一种不排序是一种不稳稳定的排序方法。定的排序方法。定的排序方法。定的排序方法。462.锦标赛排序排序(Tournament Tree Sort)树形形选择排序排序(Tree Selection Sort)n n它的思想与体育比它的思想与体育比它的思想与体育比它的思想与体育比赛时赛时的淘汰的淘汰的淘汰的淘汰赛类赛类似。首先取得似。首先取得似。首先取得似。首先取得 n n 个个个个对对象的关象的关象的关象的关键键字，字，字，字，进进行两两比行两两比行两两比行两两比较较，得到得到得到得到 n n/2/2 个比个比个比个比较较的的的的优胜优胜者者者者(关关关关键键字小者字小者字小者字小者)，作，作，作，作为为第一步比第一步比第一步比第一步比较较的的的的结结果保留下来。然后果保留下来。然后果保留下来。然后果保留下来。然后对这对这 n n/2/2 个个个个对对象再象再象再象再进进行关行关行关行关键键字的两两比字的两两比字的两两比字的两两比较较，如此重复，直到，如此重复，直到，如此重复，直到，如此重复，直到选选出一个关出一个关出一个关出一个关键键字最小的字最小的字最小的字最小的对对象象象象为为止。止。止。止。47n n锦标赛锦标赛排序构成的排序构成的排序构成的排序构成的树树是是是是满满的完全二叉的完全二叉的完全二叉的完全二叉树树，其深度，其深度，其深度，其深度为为 loglog2 2(n n+1)+1)，其中，其中，其中，其中 n n 为为待排序元素待排序元素待排序元素待排序元素个数。个数。个数。个数。n n除第一次除第一次除第一次除第一次选择选择具有最小关具有最小关具有最小关具有最小关键键字的字的字的字的对对象需要象需要象需要象需要进进行行行行 n n-1-1 次关次关次关次关键键字比字比字比字比较较外，重构外，重构外，重构外，重构胜胜者者者者树选择树选择具具具具有次小、再次小关有次小、再次小关有次小、再次小关有次小、再次小关键键字字字字对对象所需的关象所需的关象所需的关象所需的关键键字比字比字比字比较较次数均次数均次数均次数均为为 O(log O(log2 2n n)。总总关关关关键键字比字比字比字比较较次数次数次数次数为为O(O(n nloglog2 2n n)。n n对对象的移象的移象的移象的移动动次数不超次数不超次数不超次数不超过过关关关关键键字的比字的比字的比字的比较较次数，所以次数，所以次数，所以次数，所以锦标赛锦标赛排序排序排序排序总总的的的的时间时间复复复复杂杂度度度度为为O(O(n nloglog2 2n n)。n n这这种排序方法种排序方法种排序方法种排序方法虽虽然减少了然减少了然减少了然减少了许许多排序多排序多排序多排序时间时间，但是使用了，但是使用了，但是使用了，但是使用了较较多的附加存多的附加存多的附加存多的附加存储储。算法分析算法分析48 胜者者树的概念的概念n n每每每每次次次次两两两两两两两两比比比比较较的的的的结结果果果果是是是是把把把把关关关关键键字字字字小小小小者者者者作作作作为为优优胜胜者者者者上上上上升升升升到到到到双双双双亲亲结结点点点点，称称称称这这种种种种比比比比赛赛树树为为胜胜者者者者树树。n n位位位位于于于于最最最最底底底底层层的的的的叶叶叶叶结结点点点点叫叫叫叫做做做做胜胜者者者者树树的的的的外外外外结结点点点点，非非非非叶叶叶叶结结点点点点称称称称为为胜胜者者者者树树的的的的内内内内结结点点点点。每每每每个个个个结结点点点点除除除除了了了了存存存存放放放放对对象象象象的的的的关关关关键键字字字字 key key 外外外外，还还存存存存放放放放了了了了此此此此对对象象象象是是是是否否否否要要要要参参参参选选的的的的标标志志志志 Active Active 和和和和此此此此对对象象象象在在在在满满二二二二叉叉叉叉树树中的序号中的序号中的序号中的序号indexindex。n n胜胜者者者者树树最最最最顶层顶层是是是是树树的根，表示最后的根，表示最后的根，表示最后的根，表示最后选择选择出来的具有最小关出来的具有最小关出来的具有最小关出来的具有最小关键键字的字的字的字的对对象。象。象。象。49n n如果有如果有如果有如果有 n n 个个个个对对象，必象，必象，必象，必须须使用至少使用至少使用至少使用至少 2 2n n-1-1 个个个个结结点来存放点来存放点来存放点来存放胜胜者者者者树树。最多需要找到。最多需要找到。最多需要找到。最多需要找到满满足足足足 2 2k k-1 1 n n 2 2k k 的的的的k k，使用，使用，使用，使用 2*2 2*2k k-1 1 个个个个结结点。每个点。每个点。每个点。每个结结点包括关点包括关点包括关点包括关键键字、字、字、字、对对象序号和比象序号和比象序号和比象序号和比较标较标志三种信息。志三种信息。志三种信息。志三种信息。n n锦标赛锦标赛排序是一个排序是一个排序是一个排序是一个稳稳定的排序方法。定的排序方法。定的排序方法。定的排序方法。50 堆的定堆的定义 n个元素的序列个元素的序列k1，k2，kn当且当且仅当当满足下关系足下关系 ki k2i ,ki k2i+1 或或 ki k2i ,ki k2i+1 其中其中 i=1,2,n/23.堆排序堆排序 (Heap Sort)9683382711091236852447305391例如，下列两个序列例如，下列两个序列为堆：堆：96，83，27，38，11，0912，36，24，85，47，30，53，9151堆排序堆排序 基本思想基本思想 首先首先对n个个记录的关的关键字按堆的定字按堆的定义建堆，建堆，输出堆出堆顶的元素（最小关的元素（最小关键字），以堆中最后一个元素代替之。然字），以堆中最后一个元素代替之。然后后对剩余的关剩余的关键字再建堆（重新字再建堆（重新调整成堆），整成堆），输出堆出堆顶的的元素（次小关元素（次小关键字），如此重复，直至全部关字），如此重复，直至全部关键字排成有字排成有序序列序序列为止。止。实现堆排序需解决两个堆排序需解决两个问题：(1)如何将一个无序序列建成一个堆？如何将一个无序序列建成一个堆？(2)如何在如何在输出堆出堆顶元素之后，元素之后，调整剩余元素成整剩余元素成为一个新的堆？一个新的堆？52堆排序堆排序 将一个无序序列建成一个堆将一个无序序列建成一个堆(1)先将一个无序序列按先将一个无序序列按层次关系建成一个完全二叉次关系建成一个完全二叉树。(2)从第从第 n/2 个元素开始。即从完全二叉个元素开始。即从完全二叉树的最后一个非的最后一个非终端端结点开始，按照堆的定点开始，按照堆的定义，与其子，与其子结点交点交换，直至全部序列，直至全部序列成成为一个堆。一个堆。53建堆建堆 举例例例如，有一个无序序列49 38 65 97 76 13 27 4949389765761327494938496576132797493849137665279713384949766527971338492776654997堆堆54 输出堆出堆顶元素，用最后一个元素代替之，然后元素，用最后一个元素代替之，然后调整剩余元素整剩余元素成成为一个新的堆一个新的堆堆排序堆排序1338492776654997堆堆9738492776654913输出13并用97代替之4927384997766513调整2738494976659713调整成一个新堆3849974976652713输出27并用97代替之，然后调整成一个新堆55 练习堆排序堆排序有一个无序序列33，25，46，13，58，95，18，63(1)将该序列建成一个堆。(2)按序输出元素，并写出调整成一个新堆的过程56 最大堆的向下最大堆的向下调整算法整算法nvoid HeapAdjust(HeapType&H,int s,int m)nElemType rc=H.rs;nfor(int j=2*s;j=m;j*=2)nif(j0;-i)nHeapAdjust(H,i,H.length);nfor(i=H.length;i1;-i)ntemp=H.r1;nH.r1=H.ri;nH.ri=temp;nHeapAdjust(H,1,i-1);nn59 算法分析算法分析n n若若若若设设堆中有堆中有堆中有堆中有 n n 个个个个结结点，且点，且点，且点，且 2 2k k-1 1 n n 2 2k k，则对应则对应的完全二叉的完全二叉的完全二叉的完全二叉树树有有有有 k k 层层。在第。在第。在第。在第 i i 层层上的上的上的上的结结点数点数点数点数 2 2i-1 i-1 (i i=1,=1,k k)。在第一个形成初始堆的。在第一个形成初始堆的。在第一个形成初始堆的。在第一个形成初始堆的forfor循循循循环环中中中中对对每一个非叶每一个非叶每一个非叶每一个非叶结结点点点点调调用了用了用了用了一次堆一次堆一次堆一次堆调调整算法整算法整算法整算法HeapAdjust HeapAdjust()()，因此，因此，因此，因此该该循循循循环环所用的所用的所用的所用的计计算算算算时间为时间为：n n其中，其中，其中，其中，i i 是是是是层层序号，序号，序号，序号，2 2i-1 i-1 是第是第是第是第 i i 层层的最大的最大的最大的最大结结点数，点数，点数，点数，(k k-i+i+1)1)是第是第是第是第 i i 层结层结点的高度点的高度点的高度点的高度,(,(k k-i i)是是是是第第第第 i i 层结层结点能点能点能点能够够移移移移动动的最大距离。的最大距离。的最大距离。的最大距离。60n n在第二个在第二个在第二个在第二个forfor循循循循环环中，中，中，中，调调用了用了用了用了n n-1 1次次次次HeapAdjust HeapAdjust()()算法，算法，算法，算法，该该循循循循环环的的的的计计算算算算时间为时间为O(O(n nloglog2 2n n)()(见见教材教材教材教材283283页页)。因此，堆排序的因此，堆排序的因此，堆排序的因此，堆排序的时间时间复复复复杂杂性性性性为为O(O(n nloglog2 2n n)。n n该该算法的附加存算法的附加存算法的附加存算法的附加存储储主要是在第二个主要是在第二个主要是在第二个主要是在第二个forfor循循循循环环中用来中用来中用来中用来执执行行行行对对象交象交象交象交换时换时所用的一个所用的一个所用的一个所用的一个临时对临时对象。因此，象。因此，象。因此，象。因此，该该算法算法算法算法的空的空的空的空间间复复复复杂杂性性性性为为O(1)O(1)。n n堆排序是一个不堆排序是一个不堆排序是一个不堆排序是一个不稳稳定的排序方法。定的排序方法。定的排序方法。定的排序方法。6110.5 归并排序并排序 归并排序的基本思想并排序的基本思想 假假设初始序列有初始序列有n个个记录，则可看成是可看成是n个有序的子序列，个有序的子序列，每个子序列的每个子序列的长度度为1，然后两两，然后两两归并，得到并，得到n/2个个长度度为2的的或或 1 的有序子序列；再两两的有序子序列；再两两归并，并，如此重复，直至得到，如此重复，直至得到一个一个长度度为n的有序序列的有序序列为止，止，这种方法称种方法称为2-路路归并排序。并排序。归并并 将两个或两个以上的有序表将两个或两个以上的有序表组合成一个新的有序表。合成一个新的有序表。62归并排序 举例例初始关键字 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 9763n n两路两路两路两路归归并算法并算法并算法并算法(教材教材教材教材283283页页)nvoid Merge(ElemType SR,ElemType TR,int i,int m,int n)nfor(int j=m+1,k=i;i=m&j=n;+k)nif(LQ(SRi.key,SRj.key)nTRk=SRi+;nelse TRk=SRj+;n64n if(i=m)nfor(int n1=k,n2=i;n1=n&n2=m;n1+,n2+)nTRn1=SRn2;nif(j=n)nfor(int n1=k,n2=j;n1=n&n2=n;n1+,n2+)nTRn1=SRn2;n65n递归形式的两路形式的两路归并算法并算法(教材教材284页)nvoid MSort(ElemType SR,ElemType TR1,int s,int t)nElemType TR2MAXSIZE;nif(s=t)TR1s=SR s;nelse nint m=(s+t)/2;nMSort(SR,TR2,s,m);nMSort(SR,TR2,m+1,t);nMerge(TR2,TR1,s,m,t);nnnvoid MergeSort(SqList&L)nMSort(L.r,L.r,1,L.length);n66n n在在在在归归并并并并排排排排序序序序算算算算法法法法中中中中，递递归归深深深深度度度度为为O(logO(log2 2n n)，对对象象象象关关关关键键字字字字的的的的比比比比较较次次次次数数数数为为O(O(n nloglog2 2n n)。算算算算法法法法总总的的的的时间时间复复复复杂杂度度度度为为O(O(n nloglog2 2n n)。n n归归并并并并排排排排序序序序占占占占用用用用附附附附加加加加存存存存储储较较多多多多，需需需需要要要要另另另另外外外外一一一一个个个个与与与与原原原原待待待待排排排排序序序序对对象象象象数数数数组组同同同同样样大大大大小小小小的的的的辅辅助助助助数数数数组组。这这是是是是这这个算法的缺点。个算法的缺点。个算法的缺点。个算法的缺点。n n归归并排序是一个并排序是一个并排序是一个并排序是一个稳稳定的排序方法。定的排序方法。定的排序方法。定的排序方法。算法分析6710.6 基数排序基数排序n n基数排序是采用基数排序是采用基数排序是采用基数排序是采用“分配分配分配分配”与与与与“收集收集收集收集”的的的的办办法，用法，用法，用法，用对对多关多关多关多关键键字字字字进进行排序的思想行排序的思想行排序的思想行排序的思想实实现对单现对单关关关关键键字字字字进进行排序的方法。行排序的方法。行排序的方法。行排序的方法。68n 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 An n如果我如果我如果我如果我们们把所有扑克牌排成以下次序：把所有扑克牌排成以下次序：把所有扑克牌排成以下次序：把所有扑克牌排成以下次序：n n 2,2,A,A,2,2,A,A,2,2,A,A,2,2,A A 多关键字排序69 多关键字排序n n这这就是多关就是多关就是多关就是多关键键字排序。排序后形成的有序序列叫做字排序。排序后形成的有序序列叫做字排序。排序后形成的有序序列叫做字排序。排序后形成的有序序列叫做词词典有序序列。典有序序列。典有序序列。典有序序列。n n对对于上例两关于上例两关于上例两关于上例两关键键字的排序，可以先按花色排序，之后再按面字的排序，可以先按花色排序，之后再按面字的排序，可以先按花色排序，之后再按面字的排序，可以先按花色排序，之后再按面值值排序；也可以先按面排序；也可以先按面排序；也可以先按面排序；也可以先按面值值排序，再按花色排序。排序，再按花色排序。排序，再按花色排序。排序，再按花色排序。n n一般情况下，假定有一个一般情况下，假定有一个一般情况下，假定有一个一般情况下，假定有一个 n n 个个个个对对象的序列象的序列象的序列象的序列 V V0 0,V V1 1,V Vn n-1-1 ，且每个，且每个，且每个，且每个对对象象象象V Vi i 中含有中含有中含有中含有 d d 个关个关个关个关键键字字字字n n如果如果如果如果对对于序列中任意两个于序列中任意两个于序列中任意两个于序列中任意两个对对象象象象 V Vi i 和和和和 V Vj j (0(0 i i j j n-n-1)1)都都都都满满足：足：足：足：70 多关键字排序n n则则称序列称序列称序列称序列对对关关关关键键字字字字(K K1 1,K K2 2,K Kd d)有序。其中，有序。其中，有序。其中，有序。其中，K K1 1 称称称称为为最高位关最高位关最高位关最高位关键键字，字，字，字，K Kd d 称称称称为为最低最低最低最低位关位关位关位关键键字。字。字。字。n n如果关如果关如果关如果关键键字是由多个数据字是由多个数据字是由多个数据字是由多个数据项组项组成的数据成的数据成的数据成的数据项组项组，则则依据它依据它依据它依据它进进行排序行排序行排序行排序时时就需要利用多关就需要利用多关就需要利用多关就需要利用多关键键字字字字排序。排序。排序。排序。n n实现实现多关多关多关多关键键字排序有两种常用的