内蒙古大学《算法与数据结构》课件第7章排序

1 第第 7 章章 排排 序序7.1 内部排序方式内部排序方式7.2 插入排序插入排序7.3 选择排序选择排序7.4 交换排序交换排序 7.5 归并排序归并排序7.6 基数排序基数排序7.7 各种内部排序算法的比较各种内部排序算法的比较27.1 内部排序方式内部排序方式3 0 1 . 1 0 1 . 1K pK pK p nK pK pK p n或者456class /排序码排序码/其它数据成员其它数据成员/提取排序码提取排序码/修改修改 /数据表数据表/存储向量存储向量/最大元素个数与当前元素个数最大元素个数与当前元素个数/构造函数构造函数/交换元素交换元素97.2 插入排序插入排序1、直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）2、 折半插入排序折半插入排序（基于折半查找）（基于折半查找）3、 希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）10基本思想是：基本思想是：当插入第当插入第i (i 2) 个数据时，前面的处理个数据时，前面的处理R1, , Ri-1已经排好序。这时用已经排好序。这时用Ri的排序码与的排序码与Ri-1, Ri-2, 的的排序码顺序进行比较，直到排序码顺序进行比较，直到 Rj.key=Ri.key( 0 ji )将将Rj+1, Ri-1向后顺移向后顺移,将将Ri插入到插入到j+1位置处。位置处。 初始初始 50 22 45 80 08 45* 62 i=2 22 50 45 80 08 45* 62 i=3 22 45 50 80 08 45* 62 i=4 22 45 50 80 08 45* 62 i=5 08 22 45 50 80 45* 62 i=6 08 22 45 45* 50 80 62 i=7 08 22 45 45* 50 80 62 0 1 2 3 4 5 6 7例如：给出初始排序码序列例如：给出初始排序码序列 50 22 45 80 08 45* 62 的直接插入排序示意图。的直接插入排序示意图。 图图7.1 直接插入排序示例直接插入排序示例12 直接插入排序的算法如下：直接插入排序的算法如下：void InsertionSort( ) /按排序码按排序码Key 非递减顺序对数据表进行直接插入排序非递减顺序对数据表进行直接插入排序 for(i=2; i=CurrentSize; i+ ) if (Ri.KeyRi-1.Key) R0=Ri; for(j=i-1; R0.KeyRj.Key; j-) Rj+1=Rj; Rj+1=R0; / InsertionSort13最好的情况（排序码有序）：最好的情况（排序码有序）：“比较比较”的次数：的次数：最坏的情况（排序码逆序）：最坏的情况（排序码逆序）：“比较比较”的次数：的次数：112nni21412)n)(n()i (ni“移动移动”的次数：的次数：“移动移动”的次数：的次数：2) 1n)(2n(in2i 直接插入排序算法分析：直接插入排序算法分析：014 平均的情况平均的情况： 若待排序数据序列中出现各种可能排列的概率相同，则可若待排序数据序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的排取上述最好情况和最坏情况的平均情况。在平均情况下的排序码比较次数和数据移动次数约为序码比较次数和数据移动次数约为 因此，直接插入排序的时间复杂度为因此，直接插入排序的时间复杂度为 O(n2)。 空间效率：空间效率：因为仅占用因为仅占用1个缓冲单元个缓冲单元R0 直接插入排序是一种直接插入排序是一种稳定稳定的排序方法。的排序方法。4n4) 1n)(4n(21i2n2i直接插入排序算法分析：直接插入排序算法分析：151614 36 49 52 80 58 61 23 97 75ileftrightmmleftleftmrightileftrightmrightmrightmleft例如例如:插入插入位置位置插入插入位置位置R再如再如:14 36 49 52 58 61 80 23 97 75R折半插入排序示例折半插入排序示例17折半插入排序的算法如下：折半插入排序的算法如下：void BinaryInsertSort ( ) for (i = 2; i =CurrentSize; i+) left = 1, right = i-1; R0=Ri; flag=1; while ( left = right ) & flag middle = ( left + right )/2; if (R0. Key Rmiddle. Key) left = middle + 1; else flag=0; / 遇到有相同排序码的元素时，停止寻找遇到有相同排序码的元素时，停止寻找 if (!flag) / 当当flag0时，说明序列中存在有相同排序码的元素时，说明序列中存在有相同排序码的元素 left=middle; / 此时元素需从此时元素需从Rmiddle到到Ri-1 向后顺移元素向后顺移元素 for ( k = i-1; k = left; k- ) / 元素后移元素后移 Rk+1 = Rk; Rleft = R0;/for/ BinaryInsertSort203515455025102030折半插入排序的算法分析折半插入排序的算法分析:21时间效率：时间效率：比较次数比较次数: 在插入第在插入第 i 个数据时个数据时,最多需要经过最多需要经过 log2 (i+1) 次排序码次排序码比较，才能确定它应插入的位置。因此，将比较，才能确定它应插入的位置。因此，将 n 个数据用个数据用折半插入排序所进行的排序码比较次数为：折半插入排序所进行的排序码比较次数为：O(n*log2n)折半插入排序的算法分析折半插入排序的算法分析:空间效率：空间效率： O(1)O(1)( (R0 ) )但是移动次数并未减少，所以折半插入排序效率仍为但是移动次数并未减少，所以折半插入排序效率仍为O(nO(n2 2) ) 折半查找排序是不稳定的排序折半查找排序是不稳定的排序 2223其中，其中，d d 称为增量，它的值在排序过程中从大到小逐称为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序渐缩小，直至最后一趟排序减为减为 1 1。例如：例如：将将 n 个记录分成个记录分成 d 个子序列：个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 例：例：排序码序列排序码序列 T=(49，38，65，97, 76, 13, 27,49*,55,04）请写出希尔排序的具体实现过程。请写出希尔排序的具体实现过程。结论：结论：开始时开始时d 的值较大，子序列中的数据较少，排序速度较快；的值较大，子序列中的数据较少，排序速度较快；随着排序进展，随着排序进展，d 值逐渐变小，子序列中数据个数逐渐变多，值逐渐变小，子序列中数据个数逐渐变多，由于前面工作的基础，大多数数据已基本有序，所以由于前面工作的基础，大多数数据已基本有序，所以 排序速度仍然很快。排序速度仍然很快。380123456789104938659776132749*5504初态：初态：第第1趟趟 (d=5)第第2趟趟 (d=3)第第3趟趟 (d=1)4913134938276549*975576042738 65 49*9755135576045513270427044949*4949*763876 65 65 9797551327044949*3876 65 9713 27 0449* 76 97 25void Shellsort ( ) d = CurrentSize / 2; / d 是子序列间隔是子序列间隔 while ( d = 1 ) /当间隔当间隔d为零时，结束排序为零时，结束排序 ShellInsert (d ); /调用一趟直接插入排序调用一趟直接插入排序 d=d/2; /缩小增量缩小增量d / Shellsortvoid shellInsert (int d ) /一趟希尔排序，按间隔一趟希尔排序，按间隔d划分子序列划分子序列 for ( int i = d+1; i 0 & R0.Key Rj.Key; j - = d) Rj-d = Rj; Rj+d = Rj; / shellInsert2728 1) 2) 3)29 30例如：例如：初始排序码序列：初始排序码序列：50 45 80 62 08 45* 22 i=1 08 45 80 62 50 45* 22 i=2 08 22 80 62 50 45* 45 i=3 08 22 45* 62 50 80 45 i=4 08 22 45* 45 50 80 62 i=5 08 22 45* 45 50 80 62 i=6 08 22 45* 45 50 62 80 图图7.2 直接选择排序示例直接选择排序示例31 直接选择排序的算法如下：直接选择排序的算法如下：void SelectSort ( ) for (i = 1; i CurrentSize; i+ ) k = i; for (j = i+1; j =CurrentSize; j+) if ( Rj. Key Rk.Key ) k = j; / k记当前具有最小排序码的元素下标记当前具有最小排序码的元素下标 for if ( k != i ) swap（Ri，Rk）; for/SelectSort32 112)1()(ninninKCN 347.3.2 树形选择排序树形选择排序 36 形成初始胜者树（最小排序码上升到根）形成初始胜者树（最小排序码上升到根）38 输出冠军并调整胜者树后树的状态输出冠军并调整胜者树后树的状态39 输出亚军并调整胜者树后树的状态输出亚军并调整胜者树后树的状态40 输出第三名并调整胜者树后树的状态输出第三名并调整胜者树后树的状态41 输出第四名并调整胜者树后树的状态输出第四名并调整胜者树后树的状态42 输出第五名并调整胜者树后树的状态输出第五名并调整胜者树后树的状态43 全部比赛结果输出时树的状态全部比赛结果输出时树的状态4445467.3.3 堆排序堆排序 堆排序是对树形选择排序的改进，它的时间复杂度堆排序是对树形选择排序的改进，它的时间复杂度同树形选择排序，同树形选择排序，但但只需一个元素的附只需一个元素的附加空间加空间，从第四章可知，完全二叉树可以用一个数，从第四章可知，完全二叉树可以用一个数组表示，在这种表示法中，组表示，在这种表示法中，容易确定一个结点的双容易确定一个结点的双亲结点和左右子女的下标亲结点和左右子女的下标。47堆的定义：堆的定义： n个元素的排序码序列个元素的排序码序列k1, k2, , kn，当且仅当满，当且仅当满足如下关系时：足如下关系时： (i=1，2， n/2 ) 则称之为堆则称之为堆。222 12 1()()iiiiiikkkkkk小顶堆大顶堆48 例如例如: 初始排序码序列初始排序码序列 38 52 45 64 38* 18 下标下标 1 2 3 4 5 6不是堆不是堆例：例：序列序列T1=（08, 25, 49, 46, 58, 67）和）和 序列序列T2=（91, 85, 76, 66, 58, 55, 67 ） 判断它们是否判断它们是否 “堆堆”？2345617最大堆最大堆234561最小堆最小堆50堆排序的算法思想：堆排序的算法思想：首先建立最大堆。首先建立最大堆。将将heap1与与heapn交换，把剩余的元素交换，把剩余的元素heap1,heapn-1再整理成堆，新堆的根再整理成堆，新堆的根heap1是集合中具有第二大排序码的元素，是集合中具有第二大排序码的元素，将将heap1再与再与heapn-1交换交换, 再把剩余的元再把剩余的元素素heap1，heapn-2整理成堆，如此整理成堆，如此重复，直到全部元素有序。重复，直到全部元素有序。51 实现堆排序需要解决两个问题