第20讲插入和交换排序

《第20讲插入和交换排序》由会员分享，可在线阅读，更多相关《第20讲插入和交换排序（68页珍藏版）》请在金锄头文库上搜索。

1、1,Essential of Lecture Twenty：,一、排序的定义 二、插入排序 三、希尔排序 四、冒泡排序 五、快速排序,第20讲 排序,难点,2,排序的基本概念 各种排序方法 各种排序方法的比较,排序知识体系结构,排序,插入排序 选择排序 交换排序 归并排序 基数排序,直接插入排序折半插入排序链表插入排序希尔排序直接选择排序堆排序冒泡排序快速排序,3,一、排序的定义 Sorting,排序的基本概念,假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn ,这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 ： Kp1Kp2Kpn

2、,按此固有关系将上式记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。,4,一、排序的定义 Sorting,排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。,排序的基本概念,5,一、排序的定义 Sorting,排序的基本概念,单键排序：根据一个关键码进行的排序；多键排序：根据多个关键码进行的排序。,按学号排序单键排序按成绩（高数英语思想品德）排序多键排序,6,一、排序的定义 Sorting,

3、1. 内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中2. 外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。,排序的分类,外部排序：多路平衡归并、置换-选择。,7,一、排序的定义 Sorting,1. 基于比较：基本操作关键码的比较和记录的移动。 2. 不基于比较：根据关键码的分布特征。,基于比较的内排序1. 插入排序2. 交换排序3. 选择排序4. 归并排序5. 基数排序,排序的分类,8,一、排序的定义 Sorting,简单的排序方法：时间复杂度为O(n2)

4、 先进的排序方法：时间复杂度为O(nlogn) 基数排序：时间复杂度为O(d*n),排序的分类,按内排序过程中所需的工作量：,9,一、排序的定义 Sorting,排序算法的性能,1. 基本操作。内排序在排序过程中的基本操作：比较：关键码之间的比较；移动：记录从一个位置移动到另一个位置。 2. 辅助存储空间。辅助存储空间是指在数据规模一定的条件下，除了存放待排序记录占用的存储空间之外，执行算法所需要的其他存储空间。3.算法本身的复杂程度。,10,一、排序的定义 Sorting,排序算法的存储结构,从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。,假定2：将

5、待排序的记录序列排序为升序序列。,int elemn; /待排序记录存储在elem0elemn-1,假定1：采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。,11,二、插入排序 Insertion Sort,1、直接插入排序,排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。,基本思想：在插入第 i（i1）个记录时，前面的 i-1个记录已经排好序。,12,有序序列elem0.i-1,elemi,无序序列 elemi.n-1,一趟直接插入排序的基本思想：,有序序列elem0.i,无序序列elemi+

6、1.n-1,13,实现“一趟插入排序”可分三步进行：,3将elemi 插入(复制)到elemj+1的位置上。,2将elemj+1.i-1中的所有记录均后移 一个位置；,1在elem0.i-1中查找elemi的插入位置， elem0.j elemi elemj+1.i-1 ；,14,二、插入排序 Insertion Sort,1、直接插入排序,（1）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置?,需解决的关键问题?,15,二、插入排序 Insertion Sort,1、直接插入排序,elem 0 1 2 3 4 5,21,18,25,22,10,25*,21,18,16,二、插入排

7、序 Insertion Sort,解决方法：将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个有序表中，直到将第n个记录插入。,关键问题(1)如何构造初始的有序序列？,算法描述：for (i=1; i=0 & eelemj; j-) elemj+1=elemj;,二、插入排序 Insertion Sort,18,例如：,49 38 65 97 76 13 27,i=1 (38 49 ) 65 97 76 13 27,i=2 (38 49 65 ) 97 76 13 27,i=3 (38 49 65 97 ) 76 13 27,i=4 (38 49 65 76 97 ) 13 27,

8、i=5 (13 38 49 65 76 97 ) 27,i=0 ( ),i=6 (13 38 49 65 76 97 ) 27,97,76,65,49,38,27,0 1 2 3 4 5 6,19,直接插入排序算法,template void StraightInsertSort(ElemType elem, int n)/ 操作结果:对数组elem作直接插入排序序for ( int i = 1; i = 0 & e elemj; j-)/ 将比e大的计录都后移elemj + 1 = elemj;/ 后移elemj + 1 = e;/ j+1为插入位置,20,直接插入排序算法性能分析,最好情况

9、下（正序）： e,时间复杂度为O(n)。,二、插入排序 Insertion Sort,21,直接插入排序算法性能分析,最坏情况下（逆序或反序）： e,时间复杂度为O(n2)。,二、插入排序 Insertion Sort,22,平均情况下（随机排列）：,直接插入排序算法性能分析,时间复杂度为O(n2)。,二、插入排序 Insertion Sort,23,直接插入排序算法是一种稳定的排序算法。优缺点：,直接插入排序算法性能分析,直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。,二、插入排序 In

10、sertion Sort,24,如何改进直接插入排序?,注意到，在插入第 i（i1）个记录时，前面的 i-1 个记录已经排好序，则在寻找插入位置时，可以用折半查找来代替顺序查找，从而较少比较次数。,二、插入排序 Insertion Sort,25,排序过程：用折半查找方法确定插入位置的排序,二、插入排序 Insertion Sort,2、折半插入排序,26,i=0 (30) 13 70 85 39 42 6 20,i=1 13 (13 30) 70 85 39 42 6 20,i=6 6 (6 13 30 39 42 70 85) 20,.,i=7 20 (6 13 20 30 39 42 7

11、0 85),2、折半插入排序,27,二、插入排序 Insertion Sort,3、 2-路插入排序(略),4、表插入排序(略),在折半插入排序的基础上改进之,28,三、希尔排序 Shell Sort,又称缩小增量排序,改进的着眼点：（1）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高；（2）由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。,29,三、希尔排序 Shell Sort,（1）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？（2）子序列内如何进行直接插入排序？,需解决的关键问题?,基本思想：将整个待排序记录分割成若干个子序列，在子序列内分别

12、进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。,30,基本有序：接近正序，例如1, 2, 8, 4, 5, 6, 7, 3, 9；局部有序：部分有序，例如6, 7, 8, 9, 1, 2, 3, 4, 5。局部有序不能提高直接插入排序算法的时间性能。,分割待排序记录的目的?,1. 减少待排序记录个数；2. 使整个序列向基本有序发展。,子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个子序列。,启示?,三、希尔排序 Shell Sort,31,希尔插入排序过程示例,0 1 2 3 4 5 6 7 8,40,21,25,49,25*,16,初始

13、序列,30,08,13,32,三、希尔排序 Shell Sort,解决方法：将相隔某个“增量”的记录组成一个子序列。增量应如何取？希尔最早提出的方法是d1=n/2，di+1=di/2。,关键问题(1)应如何分割待排序记录？,算法描述：for (k=0; kt; k+) 以inck为增量，进行组内直接插入排序；,33,关键问题(2)子序列内如何进行直接插入排序？,三、希尔排序 Shell Sort,for (i=incr; i=0 & eelemj; j-=incr) elemj+incr=elemj; /记录后移d个位置 /然后j-incr比较同一子序列的前一个记录 elemj+incr=e; ,