数据结构.第10章.排序.1.插入排序和交换排序ppt课件

1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2021年3月12日.第第1010章章 内部排序内部排序选择排序 (直接排序、堆排序)概述插入排序 (直接排序、折半排序、希尔排序)交换排序 (冒泡排序、快速排序)归并排序基数排序.v概述概述10.1 概述概述排序：将数据元素的一个恣意序列，重新陈列成一个按关键字有序的序列。 例：将关键字序列：52, 49, 80, 36, 14, 58, 61, 23 调整为：14, 23, 36, 49, 52, 58, 61, 80 假设按主关键字排序那么结果独一假设按次关键字排序

2、那么结果可以不独一(因有一样关键字) .v概述概述10.1 概述概述 设 Ki、Kj (1in, 1jn, ij ) 分别为记录 Ri、Rj 的关键字，且 Ki = Kj ，在排序前的序列中 Ri 领先于 Rj (即 i j )。假设在排序后的序列中 Ri 仍领先于 Rj ，那么称所用的排序方法是稳定的；反之，那么称所用的排序方法是不稳定的。 例：设排序前的关键字序列为：52, 49, 80, 36, 14, 58, 36, 23 假设排序后的关键字序列为：14, 23, 36, 36, 49, 52, 58, 80， 那么排序方法是稳定的。 假设排序后的关键字序列为：14, 23, 36,

3、36, 49, 52, 58, 80， 那么排序方法是不稳定的。 .v概述概述10.1 概述概述内部排序和外部排序 假设整个排序过程不需求访问外存便能完成，那么称此类排序问题为内部排序； 反之，假设参与排序的记录数量很大，整个序列的排序过程不能够在内存中完成，那么称此类排序问题为外部排序。 .v插入排序插入排序10.2 插入排序插入排序.直接插入排序 初始形状4938659776132749 R0 R1 R2 R3 R4 R5 R6 R7 R8 i =2 i =3 3849659776132749 i =4 3849659776132749 i =5 384965769713274976i =

4、6 384965769713274913i =7 384965769713274927i =8 3849657697132749494938659776132749 3849387 趟 排序 1 趟 排序 2 趟 排序 排序过程：排序过程：先将序列中第先将序列中第 1 个记录看成是一个有序子序列，个记录看成是一个有序子序列， 然后从第然后从第 2 个记录开场，逐个进展插入，直至整个序列有序。个记录开场，逐个进展插入，直至整个序列有序。 .v直接插入排序直接插入排序10.2 插入排序插入排序void InsertSort ( SqList &L ) / 对顺序表对顺序表 L 作直接插入排

5、序。作直接插入排序。 for ( i = 2; i = L.length; + i ) 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; for ( j = i - 2; L.r0.key L.r j .key; - - j ) L.r j + 1 = L.r j ; / 记录后移 L.r j + 1 = L.r0; / 插入到正确位置

6、 .v直接插入排序性能分析直接插入排序性能分析 10.2 插入排序插入排序211nin2(2)(1)2ninni2(4)(1)(1)2ninni比较次数： 挪动次数： 0 最好的情况：待排序记录按关键字从小到大陈列正序 比较次数： 挪动次数： 最坏的情况：待排序记录按关键字从大到小陈列逆序 .v直接插入排序性能分析直接插入排序性能分析 10.2 插入排序插入排序 由于待排记录序列是随机的，取上述二值的平均值。所以直接插入排序的时间复杂度为O(n2)。 直接插入排序是“稳定的：关键码一样的两个记录，在整个排序过程中，不会经过比较而相互交换。.v折半插入排序折半插入排序10.2 插入排序插入排序(

7、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 36 42 53 69 10.2 插入排序插入排序(high36 )( 4253 ) high mid lowlow highmid high low折半插入排序在寻觅插入位置时，不是逐个比较而

8、是利用折半查找的原理寻觅插入位置。待排序元素越多，改良效果越明显。.v折半插入排序算法折半插入排序算法10.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) /比较，折半查找插入位置比较，折半查找插入位置 mid=(low+high)/2; / 折半折半 if (L.r0.key=low; j ) L.rj+1=L

9、.rj; / 记录后移记录后移 L.rlow=L.r0; / 插入插入 / BInsertSort.v折半插入排序算法分析折半插入排序算法分析10.2 插入排序插入排序 折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。 折半插入排序减少了关键字的比较次数，但记录的挪动次数不变，其时间复杂度与直接插入排序一样。 在插入第 i 个对象时，需求经过 log2i +1 次关键码比较，才干确定它应插入的位置。 折半插入排序是一个稳定的排序方法。.v2-路插入排序路插入排序10.2 插入排序插入排序(1) 根本思想 2-路插入排序是在折半插入排序的根底上改良的，目的是减少排序过程中

10、挪动记录的次数，但为此需求n个记录的辅助空间。.v2-路插入排序路插入排序10.2 插入排序插入排序(2) 详细做法 另设一个和 L.r 同类型的数组d，首先将 L.r1 赋值给d1 ，并将d1看成是在排好序的序列中处于中间位置的记录，然后从 L.r中第 2 个记录起依次插入到d1之前或之后的有序序列中。先将待插入记录的关键字和d1 的关键字进展比较。 假设 L.rid1.key，那么将 L.ri 插入到d1 之前的有序表中。反之，插入到d1 之后的有序表中。.【初始关键字】 49 38 65 97 76 13 27 49 排序过程中d 的形状如下：i=1: (49) i=2: (49) (3

11、8)i=3: (49 65) (38)i=4: (49 65 97) (38)i=5: (49 65 76 97) (38)i=6: (49 65 76 97) (13 38)i=7: (49 65 76 97) (13 27 38)i=8: (49 49 65 76 97) (13 27 38)finalfirst2路插入排序过程例如：firstfinalfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirst.void Path2Insertion(SqList &L, SqList &d) d0 = L1;/

12、L中D的第一个记录为d中排好序的记录。 int first = 0, final = 0;/first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 for (int i = 2; i = length; +i) /依次将L的第2个最后一个记录插入d中。 if (Li dfinal) /待插入记录大于d中最小值，插入到dfinal之后 final = final + 1; dfinal = Li; else /待插入记录大于d中最小值，小于d中最大值，插入到d的中间(需求挪动d数组) int j = final +;/挪动d尾部元素以便按序插入记录。 while (Li dj

13、) d(j + 1) % length = dj; j = (j - 1 + length) % length; dj + 1 = Li; for (int i = 1; i = length; i +) /循环把d赋给L。 Li = d(i + first - 1) % length;/线性关系。 .v2-路插入排序路插入排序10.2 插入排序插入排序 2-路插入排序只能减少挪动记录的次数，而不能绝对防止挪动记录。 2-路插入排序中，挪动记录的次数约为n2/8 。 当L.r1是待排序记录中关键字最小或最大的记录时，2-路插入排序就完全失去了它的优越性。.v表插入排序表插入排序10.2 插入排

14、序插入排序(1) 根本思想 经过改动排序过程中采用的存储构造，减少在排序过程中进展“挪动记录的操作。利用静态链表进展排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。.v表插入排序表插入排序10.2 插入排序插入排序#define MAXSIZE 100 /静态链表容量Typedef struct RcdType rc; /记录项 int next; /指针项 SLNode; /表结点类型Typedef struct SLNode rMAXSIZE+1; /0号单元为表头结点 int length; /链表当前长度 SLinkListType

15、; /静态链表类型(2) 待排记录序列的存储构造.v表插入排序表插入排序10.2 插入排序插入排序(3) 详细做法 首先将静态链表中数组下标为“1的分量(结点)和表头结点构成一个循环链表，然后依次将下标为“2至“n的分量(结点)按记录关键字非递减有序插入到循环链表中。.10.2 插入排序插入排序void TableSort(int *a, int n) nexthead = 0 = -1; for (i=1; in; i+) if (ai = ahead) nexti = head; head = i; else p = head; while (nextp!=-1 & anextpa

16、i) p = nextp; nexti = nextp; nextp = i; .初始形状012345678MAXINT493865977613274910-i=3012345678MAXINT4938659776132749201-key域next域i=2012345678MAXINT493865977613274910-38123650i=4012345678MAXINT49386597761327492310-9740.i=5012345678MAXINT493865977613274923140-i=6012345678MAXINT4938659776132749231504-i=70

17、12345678MAXINT49386597761327496315042-i=8012345678MAXINT493865977613274963150472-7645136227724938.v表插入排序表插入排序10.2 插入排序插入排序(4) 表插入排序性能分析 从表插入排序的过程可见，表插入排序的根本操作仍是将一个记录插入到已排好序的有序表当中。和直接插排序相比，不同之处仅是以修正2n次指针值替代挪动记录，排序过程中所需进展的关键字间的比较次数一样。因此表插入排序的时间复杂度仍是O(n2)。.v表插入排序表插入排序10.2 插入排序插入排序(4) 表插入排序性能分析 表插入排序的结果

18、只是求得一个有序链表，那么只能对它进展顺序查找，不能进展随机查找，为了能实现有序表的折半查找，尚需对记录进展重新陈列。.10.2 插入排序插入排序1.我们都能了解，优秀排序算法的首要条件就是2.于是人们想了许许多多的排序方法，目的就是为了提高排序的速度。3.而在很长的时间里，众人发现虽然各种排序算法花样繁多，但时间复杂度都是O(n2)，似乎没法超越了。4.计算机学术界充斥着“排序算法不能够突破O(n2)的声音？速度.10.2 插入排序插入排序 终于有一天，当一位科学家发布超越了O(n2)新排序算法后，紧接着就出现了好几种可以超越O(n2)的排序算法，并把内排序算法的时间复杂度提升到了O(nlo

19、g2n)。“不能够超越O(n2) 彻底成为了历史。.v希尔排序希尔排序10.2 插入排序插入排序根本思想：先将整个待排记录序列分割成假设干子序列,分别进展直接插入排序，待整个序列中的记录“根本有序时，再对全体记录进展一次直接插入排序。技巧：子序列的构成不是简单地“逐段分割，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短例如依次取5,3,1，直到dk1为止。优点：让关键字值小的元素能很快前移，且序列假设根本有序时，再用直接插入排序处置，时间效率会高很多。.312345665499725251321234562525136549971123456132525654997123456

20、132525496597增量3增量2增量1希尔排序过程.v希尔排序希尔排序10.2 插入排序插入排序38例：关键字序列 T=(49, 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

21、 0449* 76 97 ri算法分析：开场时dk 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐变多，由于前面任务的根底，大多数对象已根本有序，所以排序速度依然很快。.v希尔排序算法描画希尔排序算法描画10.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

22、.key L.rj.key);j -= dk) L.rj+dk = L.rj; / 记录后移，查找插入位置 L.rj+dk = L.r0; / 插入 /ShellInsert.v希尔排序算法描画希尔排序算法描画10.2 插入排序插入排序void ShellSort (SqList &L, int dlta , int t) / 按增量序列按增量序列dlta0.t-1对顺序表对顺序表L作希尔排序作希尔排序 for (k=0; k1; i-) /i表示趟数，最多表示趟数，最多n-1趟趟 flag=0; /开场时元素未交换开场时元素未交换 for (int j=2; j=i; j+) if

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

24、长度的过程，也是一个减少无序序列长度的过程，每经过一趟起泡，无序序列的长度只减少1。 试想象：假设能在经过一趟排序，使无序序列的长度减少一半，那么必能加快排序的速度。.v快速排序快速排序10.3 交换排序交换排序(1) 根本思想 经过一趟排序将待排序列以枢轴为规范划分成两部分，使其中一部分记录的关键字均比另一部分小，再分别对这两部分进展快速排序，以到达整个序列有序。 通常取第一个记录的值为基准值或枢轴。.v快速排序快速排序10.3 交换排序交换排序(2) 详细做法 附设两个指针low和high，初值分别指向第一个记录和最后一个记录，设枢轴为key； 1.从high 所指位置起向前搜索，找到第一

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

26、Rlow.key; while (low high) /从两端交替向中间扫描从两端交替向中间扫描 while (low = pivotkey) - - high; Rlow = Rhigh; /将比枢轴记录小的移到低端将比枢轴记录小的移到低端 while (low high & Rlow.key = pivotkey) + + low; Rhigh = Rlow; /将比枢轴记录大的移到高端将比枢轴记录大的移到高端 Rlow = R0; /枢轴记录到位枢轴记录到位 return low; /前往枢轴位置前往枢轴位置 / Partition.v快速排序算法过程快速排序算法过程 10.3

27、交换排序交换排序无 序 的 记 录 序 列无序记录子序列 (1)无序子序列 (2) 枢轴 一次划分 分别进展一趟快速排序 有 序 的 记 录 序 列 .v快速排序算法描画快速排序算法描画10.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); /对低子表递归排序，对低子表递归排序，p

28、ivo是枢轴是枢轴 QSort(L, pivot+1, high); / 对高子表递归排序对高子表递归排序 / QSortvoid QuickSort(Elem R, int n) /对记录序列进展快速排序对记录序列进展快速排序 QSort(R, 1, n); / QuickSort.076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742，751，863，937076，129，256，751，937，863，742，694，301，438076，129，256，438，301，694，742，694，863，9372

29、56，301，751，129，937，863，742，694，076，438例：以关键字序列256，301，751，129，937，863，742，694，076，438为例，写出执行快速算法的各趟排序终了时，关键字序列的形状。原始序列： 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) 由于每趟确定的元素呈指数添加空间效

30、率：O(log2n)由于算法的递归性，要用到栈空间稳 定 性：不稳定 由于可选任一元素为支点。.v快速排序算法详细分析快速排序算法详细分析10.3 交换排序交换排序可以证明，函数Quicksort的平均计算时间是O(nlog2n)。实验结果阐明：就平均计算时间而言，快速排序是我们所讨论的一切内排序方法中最好的一个。快速排序是递归的，需求有一个栈存放每层递归调用时的指针和参数(新的low和high)。最大递归调用层次数与递归树的深度一致，理想情况为 log2(n+1) 。因此，要求存储开销为 O(log2n)。.v快速排序算法详细分析快速排序算法详细分析10.3 交换排序交换排序最好情况：假设每

31、次划分对一个对象定位后，该对象的左侧子序列与右侧子序列的长度一样，那么下一步将是对两个长度减半的子序列进展排序，这是最理想的情况。此时，快速排序的趟数最少。最坏情况：即待排序对象序列曾经按其关键码从小到大排好序的情况下，其递归树成为单支树，每次划分只得到一个比上一次少一个对象的子序列。这样，必需经过 n-1 趟才干把一切对象定位，而且第 i 趟需求经过 n-i 次关键码比较才干找到第 i 个对象的安放位置，总的关键码比较次数将到达n2/2.v快速排序能否真的比任何排序算法都快？快速排序能否真的比任何排序算法都快？10.3 交换排序交换排序设每个子表的支点都在中间比较平衡，那么：第1趟比较，可以确定1个元素的位置；第2趟比较2个子表，可以再确定2个元素的位置；第3趟比较4个子表，可以再确定4个元素的位置；第4趟比较8个子表，可以再确定8个元素的位置； 只需log2n 1趟便可排好序。根本上是！由于每趟可以确定的数据元素是呈指数添加的！而且，每趟需求比较和挪动的元素也呈指数下降，加上编程时运用了交替逼近技巧，更进一步减少了挪动次数，所以速度特别快。.vn