数据结构第10章内部排序.ppt

《数据结构第10章内部排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章内部排序10/1/202111概述2插入排序（直接插入排序、希尔排序）3直接选择排序4交换排序(起泡排序、快速排序）5归并排序6内部排序方法的比较习题10/1/202121概述基本概念定义：将文件中的数据记录按关键字值的递增或递减的顺序排列起来。{R1,R2,...,Rn}{Ri1,Ri2,...,Rin}其中关键字{k1,k2,...,kn}有序序列{ki1,ki2,...,kin}排序方法的稳定性：对于ki＝kj的记录Ri＝Rj（Ri在Rj之前）,排序后：Ri仍在Rj之前，则排序方法是稳定的；Ri在Rj之

2、后，则排序方法是不稳定的；10/1/20213基本概念方法分类：内部排序：在内存中进行，适于小文件外部排序：使用内存和外存，适于大文件，内存不够用内部排序：文件可有三种存储结构(1)一维数组：对记录的物理位置重排(2)链表：修改指针(3)索引表：对索引进行物理重排，记录位置不动（由于不方便移动等原因）本章仅考虑：记录数组R[n]，关键字key为整数标准：执行时间(最重要的标志)，所需空间，算法复杂度排序的时间代价主要指：算法中关键字的比较次数和记录的移动次数10/1/20214以记录数组作为文件的存储结构，关键字为整数

3、，文件类型说明如下：typedefstruct/*定义记录为结构类型*/{intkey;/*关键字域*/datatypeother;/*记录的其他域*/}rectype;rectypeR[n];/*R为记录类型的数组*/其中：n为文件的记录总数。10/1/202152插入排序将记录分为有序区和无序区，每次将无序区的第一个记录插入到有序区的适当位置，使之保持有序。2.1直接插入排序(最简单)具体做法：把第i个记录Ri插入到有序区{R1,R2,…,Ri-1};将关键字ki依次与关键字ki-1,ki-2,…,k1进行比较，从而

4、找到应该插入的位置，然后将ki插入。10/1/20216假设R[1]～R[n]为待排序的记录区，下面给出算法描述：INSERTSORT(rectypeR[])//对数组R按递增序进行插入排序//R[0]是监视哨*/{inti,j;for(i=2;i<=n;i++)/*依次插入R[2],…,R[n]*/{R[0]=R[i];j=i1;while(R[0].key

5、[i]*/}}/*INSERTSORT*/10/1/20217算法采用的是查找比较操作和记录移动操作交替进行的方法具体做法是：将待插入记录R[i]的关键字依次与有序区中记录R[j](j=i1,i2,…,1)的关键字进行比较，若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置；若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j+1即为R[i]的插入位置。因为关键字比R[i]大的记录均已后移，故只要将R[i]插入该位置即可。附加记录R[0]，其作用有两个：进入查找循环之前，它保存了R[i]的副

6、本，使得不致于因记录的后移而丢失R[i]中的内容；在while循环中“监视”下标变量j是否越界，以避免循环内每次都要检测j是否越界。因此，我们将R[0]称为“监视哨”，这使得测试循环条件的时间大约减少一半。10/1/20218根据上述算法，我们用一例子来说明直接插入排序的过程。设待排序的文件有八个记录，其关键字分别为47,33,61,82,72,11,25,47，直接插入排序过程如图14.1所示。10/1/20219直接插入排序的算法分析：整个排序过程只有两种运算，即比较关键字和移动记录。外循环：n1趟插入排序；内循

7、环：每一趟排序所需进行的关键字的比较和记录的后移。文件正序时：每趟排序的关键字比较次数为1，总的比较次数Cmin=n1；每趟记录移动次数是2次，总的移动次数Mmin=2(n1)；文件逆序时：关键字的比较次数和记录移动次数均取最大值。每趟进行i次比较:与前i1个记录及“监视哨”进行比较每趟排序中除了上面提到的两次移动外，还需将关键字大于R[i]的记录后移一个位置。因此，总的比较次数和记录的移动次数为:10/1/202110在随机情况下:关键字各种排列出现的概率相同，则可取上述两种情况的平均值作为比较和记录移动的平均次

8、数，约为n2/4。由此，直接插入排序的时间复杂度为O(n2)，空间复杂度为O(1)。直接插入排序是稳定的排序方法。10/1/2021112.2希尔排序希尔排序（Shell’smethod）又称为“缩小增量排序”（DiminishingIncrementSort）。基本思想：先取一个小于n的整数d1并作为第一个增量，将