插入排序及交换排序

1、第第9 9章章 内部排序内部排序选择排序 (直接排序、堆排序)概述插入排序 (直接排序、折半排序、希尔排序)交换排序 (冒泡排序、快速排序)通过例子消化概念通过例子消化概念v 在排序问题中，通常将在排序问题中，通常将数据元素数据元素称为称为记录记录。 显然输入的是一个记录集合，排序后输出的也是一个显然输入的是一个记录集合，排序后输出的也是一个记录集合。记录集合。 所以可以将排序看成是线性表的一种操作。所以可以将排序看成是线性表的一种操作。v 排序的依据是关键字之间的大小关系，那么对同一记录集排序的依据是关键字之间的大小关系，那么对同一记录集合，针对不同的关键字进行排序，可以得到不同序列。合，针

2、对不同的关键字进行排序，可以得到不同序列。v 请看例子：排序演示请看例子：排序演示.xls.xls9.1 概述概述排序的稳定性排序的稳定性通过例子消化概念通过例子消化概念编号编号姓名姓名总分总分1 1小贾小贾7312 2小刘小刘6593 3小张小张7254 4小王小王7315 5小胡小胡726编号编号姓名姓名总分总分1 1小贾小贾7314 4小王小王7315 5小胡小胡7263 3小张小张7252 2小刘小刘659编号编号姓名姓名总分总分4 4小王小王7311 1小贾小贾7315 5小胡小胡7263 3小张小张7252 2小刘小刘659稳定排序不稳定排序9.1 概述概述插入排序插入排序v插入排

3、序插入排序9.2 插入排序插入排序直接插入排序 初始状态4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7 R8 i =2 i =3 3849659776132749 i =4 3849659776132749 i =5 384965769713274976i =6 384965769713274913i =7 384965769713274927i =8 3849657697132749494938659776132749 3849387 趟 排序 1 趟 排序 2 趟 排序 排序过程：排序过程：先将序列中第 1 个记录看成是一个有序子序列， 然后从第 2 个记

4、录开始，逐个进行插入，直至整个序列有序。 v直接插入排序直接插入排序9.2 插入排序插入排序void InsertSort ( SqList &L ) / 对顺序表 L 作直接插入排序。 for ( i = 2; i = L.length; + i ) /将 L.ri 插入有序子表 if (L.ri.key L.ri -1.key) / InsertSort 在 r1. i-1中查找 ri 的插入位置; 对于在查找过程中找到的那些关键字 不小于 ri.key 的记录，在查找的同 时实现记录向后移动； 插入 ri ;L.r0 = L.ri; / 复制为监视哨 L.ri = L.ri -1; fo

5、r ( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 记录后移 L.r j + 1 = L.r0; / 插入到正确位置 v直接插入排序性能分析直接插入排序性能分析 9.2 插入排序插入排序211nin2(2)(1)2ninni2(4)(1)(1)2ninni比较次数： 移动次数： 0 最好的情况：待排序记录按关键字从小到大排列（正序） 比较次数： 移动次数： 最坏的情况：待排序记录按关键字从大到小排列（逆序） v直接插入排序性能分析直接插入排序性能分析 9.2 插入排序插入排序 由于待排记录序列是随机的，取上述二值的

6、平均值。所以直接插入排序的时间复杂度为O(n2)。 直接插入排序是“稳定的”：关键码相同的两个记录，在整个排序过程中，不会通过比较而相互交换。v折半插入排序折半插入排序9.2 插入排序插入排序(1) 基本思想 考虑到 L.r1,.,i-1 是按关键字有序的有序序列，则可以利用折半查找实现“L.r1,i-1中查找 L.ri 的插入位置”如此实现的插入排序为折半插入排序。例：有例：有6个记录，前个记录，前5个已排序的基础上，对第个已排序的基础上，对第6个记录排序。个记录排序。 15 27 36 53 69 42 15 27 36 53 69 42 15 27 36 53 69 42 15 27 3

7、6 42 53 69 9.2 插入排序插入排序(high36 )( 4253 ) high mid lowlow highmid high low折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。v折半插入排序算法折半插入排序算法9.2 插入排序插入排序void BinsertSort(SqList &L) / 折半插入排序 int i,low,high,mid; for(i=2; i= L.length; +i) L.r0=L.ri; /将L.r i 暂存到L.r0 low=1; high=i-1; While(low=high)

8、/比较，折半查找插入位置 mid=(low+high)/2; / 折半 if (L.r0.key=low; j ) L.rj+1=L.rj; / 记录后移 L.rlow=L.r0; / 插入 / BInsertSortL.r1,i- -1v折半插入排序算法分析折半插入排序算法分析9.2 插入排序插入排序 折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。 折半插入排序减少了关键字的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。 在插入第 i 个对象时，需要经过 log2i +1 次关键码比较，才能确定它应插入的位置。 折半插入排序是一个稳定的排序方法。9

9、.2 插入排序插入排序1.我们都能理解，优秀排序算法的首要条件就是2.于是人们想了许许多多的排序办法，目的就是为了提高排序的速度。3.而在很长的时间里，众人发现尽管各种排序算法花样繁多，但时间复杂度都是O(n2)，似乎没法超越了。4.计算机学术界充斥着“排序算法不可能突破O(n2)”的声音？速度9.2 插入排序插入排序 终于有一天，当一位科学家发布超越了O(n2)新排序算法后，紧接着就出现了好几种可以超越O(n2)的排序算法，并把内排序算法的时间复杂度提升到了O(nlog2n)。“不可能超越O(n2) ”彻底成为了历史。v希尔排序希尔排序9.2 插入排序插入排序基本思想：先将整个待排记录序列分

10、割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。技巧：子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短（例如依次取5,3,1），直到dk1为止。优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。312345665499725251321234562525136549971123456132525654997123456132525496597增量3增量2增量1希尔排序过程v希尔排序希尔排序9.2 插入排序插入排序38例：关键字序列 T=(49

11、, 38, 65, 97, 76, 13, 27, 49*, 55, 04) 请写出希尔排序的具体实现过程。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 ri算法分析：开始时dk 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk 值逐渐变小，子

12、序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。v希尔排序算法描述希尔排序算法描述9.2 插入排序插入排序void ShellInsert ( SqList &L, int dk ) /一趟希尔插入排序 /1.前后记录位置的增量是dk； /2.L.r0只是暂存单元，不是哨兵。当j=0时，插入位置已找到 for ( i=dk+1; i=L.length; +i ) if ( L.ri.key0 & (L.r0.key1; i-) /i表示趟数，最多n-1趟 flag=0; /开始时元素未交换 for (int j=2; j=i; j+) if (RjRj-

13、1) /发生逆序 temp=Rj; Rj=Rj-1; Rj-1=temp; flag=1; if(flag=0) return; / Bubblesortv冒泡排序算法分析冒泡排序算法分析9.3 交换排序交换排序正序： 只需进行一趟排序，在排序过程中进行n-1次关键字间的比较，且不移动记录；时间复杂度为O(n) 。逆序： 需要进行n-1趟排序，需要进行n(n-1)/2次比较，并作等数量级的记录移动。总的时间复杂度为O(n2) 。 起泡排序方法是稳定的。适合于数据较少的情况。v快速排序快速排序9.3 交换排序交换排序背景 起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序

14、序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。 试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。v快速排序快速排序9.3 交换排序交换排序(1) 基本思想 通过一趟排序将待排序列以枢轴为标准划分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分进行快速排序，以达到整个序列有序。 通常取第一个记录的值为基准值或枢轴。v快速排序快速排序9.3 交换排序交换排序(2) 具体做法 附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设枢轴为key； 1.从high 所指位置起向前搜索，找到第一个不大于基准值的记录与枢轴记录相互交换；

15、 2.从low 所指位置起向后搜索，找到第一个不小于基准值的记录与枢轴记录相互交换。 3.重复这两步直至low=high为止。v快速排序快速排序9.3 交换排序交换排序lowhigh设Rs=52 为枢轴例： 52 52 49 80 36 14 58 61 97 23 75 high23 lowlow80highhighhighhigh14lowlow52v一趟快速排序算法描述一趟快速排序算法描述9.3 交换排序交换排序int Partition (Elem R , int low, int high) R0 = Rlow; pivotkey = Rlow.key; while (low hig

16、h) /从两端交替向中间扫描 while (low = pivotkey) - - high; Rlow = Rhigh; /将比枢轴记录小的移到低端 while (low high & Rlow.key = pivotkey) + + low; Rhigh = Rlow; /将比枢轴记录大的移到高端 Rlow = R0; /枢轴记录到位 return low; /返回枢轴位置 / Partitionv快速排序算法过程快速排序算法过程 9.3 交换排序交换排序无 序 的 记 录 序 列无序记录子序列 (1)无序子序列 (2) 枢轴 一次划分 分别进行一趟快速排序 有 序 的 记 录 序 列 v

17、快速排序算法描述快速排序算法描述9.3 交换排序交换排序void QSort ( Elem R , int low, int high ) /对序列Rlow.high进行快速排序 if (low high-1) /长度大于1 pivot = Partition( L,low,high); /将Rlow.high一分为二 QSort(L,low, pivot-1); /对低子表递归排序，pivo是枢轴 QSort(L, pivot+1, high); / 对高子表递归排序 / QSortvoid QuickSort(Elem R, int n) /对记录序列进行快速排序对记录序列进行快速排序 Q

18、Sort(R, 1, n); / QuickSort076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742，751，863，937076，129，256，751751，937，863，742，694，301，438076，129，256，438，301，694，742，694，863，937256，301，751，129，937，863，742，694，076，438例：以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的各趟排序结束时，关键字序列的状

19、态。原始序列： 256，301，751，129，937，863，742，694，076，438第1趟第2趟第3趟第4趟要求模拟算法实现步骤256256076076301301129129751751256256751751438438076，129，256，301，438，694，742，751，863，937时间效率：O(nlog2n) 因为每趟确定的元素呈指数增加空间效率：O(log2n)因为算法的递归性，要用到栈空间稳 定 性：不稳定 因为可选任一元素为支点。v快速排序算法详细分析快速排序算法详细分析9.3 交换排序交换排序可以证明，函数Quicksort的平均计算时间是O(nlog2n)。实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中