《数据结构第10章内部排序》由会员分享，可在线阅读，更多相关《数据结构第10章内部排序（52页珍藏版）》请在金锄头文库上搜索。
1、2018/10/16,1,第10章 内部排序,2018/10/16,2,1 概述 2 插入排序（直接插入排序、希尔排序） 3直接选择排序 4交换排序(起泡排序、快速排序） 5归并排序 6内部排序方法的比较 习题,2018/10/16,3,1 概述,基本概念 定义：将文件中的数据记录按关键字值的递增或递减的顺序排列起来。 R1, R2,., Rn Ri1, Ri2,., Rin 其中关键字k1, k2,., kn 有序序列ki1, ki2,., kin 排序方法的稳定性：对于kikj的记录RiRj（ Ri在Rj之前）,排序后： Ri仍在Rj之前，则排序方法是稳定的； Ri在Rj之后， 则排序方法
2、是不稳定的；,2018/10/16,4,基本概念 方法分类： 内部排序：在内存中进行，适于小文件 外部排序：使用内存和外存，适于大文件，内存不够用 内部排序：文件可有三种存储结构 (1)一维数组：对记录的物理位置重排 (2)链表：修改指针 (3)索引表：对索引进行物理重排，记录位置不动（由于不方便移动等原因） 本章仅考虑：记录数组Rn，关键字key为整数 标准： 执行时间(最重要的标志)，所需空间，算法复杂度排序的时间代价主要指：算法中关键字的比较次数和记录的 移动次数,2018/10/16,5,以记录数组作为文件的存储结构，关键字为整数，文件类型说明如下： typedef struct /*
3、 定义记录为结构类型 */ int key; /* 关键字域 */datatype other; /* 记录的其他域 */ rectype; rectype Rn; /* R为记录类型的数组 */ 其中：n为文件的记录总数。,2018/10/16,6,2 插入排序,将记录分为有序区和无序区，每次将无序区的第一个记录插入到有序区的适当位置，使之保持有序。 2.1 直接插入排序(最简单) 具体做法：把第i个记录Ri插入到有序区R1, R2, , Ri-1;将关键字ki依次与关键字ki-1, ki-2, , k1进行比较，从而找到应该插入的位置，然后将ki插入。,2018/10/16,7,假设R1R
4、n为待排序的记录区，下面给出算法描述：INSERTSORT(rectype R) / 对数组R按递增序进行插入排序 / R0是监视哨 */ int i, j; for (i=2; i=n; i+) /* 依次插入R2, , Rn */ R0=Ri; j=i1; while (R0.keyRj.key) /* 查找Ri的插入位置 */Rj+1=Rj; j-; / 将关键字大于Ri.key的记录后移Rj+1=R0; /* 插入Ri */ /* INSERTSORT */,2018/10/16,8,算法采用的是查找比较操作和记录移动操作交替进行的方法 具体做法是：将待插入记录Ri的关键字依次与有序区
5、中记录Rj(j=i1, i2, , 1)的关键字进行比较，若Rj的关键字大于Ri的关键字，则将Rj后移一个位置；若Rj的关键字小于或等于Ri的关键字，则查找过程结束，j+1即为Ri的插入位置。因为关键字比Ri大的记录均已后移，故只要将Ri插入该位置即可。附加记录R0，其作用有两个： 进入查找循环之前，它保存了Ri的副本，使得不致于因记录的后移而丢失Ri中的内容； 在while循环中“监视”下标变量j是否越界，以避免循环内每次都要检测j是否越界。因此，我们将R0称为“监视哨”，这使得测试循环条件的时间大约减少一半。,2018/10/16,9,根据上述算法，我们用一例子来说明直接插入排序的过程。设
6、待排序的文件有八个记录，其关键字分别为47, 33, 61, 82, 72, 11, 25, 47，直接插入排序过程如图14.1所示。,2018/10/16,10,直接插入排序的算法分析：整个排序过程只有两种运算，即比较关键字和移动记录。外循环：n1趟插入排序； 内循环：每一趟排序所需进行的关键字的比较和记录的后移。 文件正序时：每趟排序的关键字比较次数为1，总的比较次数Cmin=n1；每趟记录移动次数是2次，总的移动次数Mmin=2(n1)； 文件逆序时：关键字的比较次数和记录移动次数均取最大值。每趟进行i次比较:与前i1个记录及“监视哨” 进行比较每趟排序中除了上面提到的两次移动外，还需将
7、关键字大 于Ri的记录后移一个位置。 因此，总的比较次数和记录的移动次数为:,2018/10/16,11,在随机情况下: 关键字各种排列出现的概率相同，则可取上述两种情况的平均值作为比较和记录移动的平均次数，约为n2/4。由此，直接插入排序的时间复杂度为 O(n2)，空间复杂度为O(1)。直接插入排序是稳定的排序方法。,2018/10/16,12,2.2 希尔排序希尔排序（Shells method）又称为“缩小增量排序”（Diminishing Increment Sort）。 基本思想：先取一个小于n的整数d1并作为第一个增量，将文件的全部记录分成d1个组，所有距离为d1倍数的记录放在同一
8、个组中，在各组内进行直接插入排序；然后取第二个增量d2d1，重复上述的分组和排序，直至所取的增量dt=1(dtdt1d2d1)为止，此时，所有的记录放在同一组中进行直接插入排序。,2018/10/16,13,例：设待排序文件共有10个记录，其关键字分别为47, 33, 61, 82, 71, 11, 25, 47, 57, 02，增量序列取值依次为5, 3, 1。排序过程如下：,2018/10/16,14,算法设计：如何设置监视哨？设某一趟希尔排序的增量为h，则整个文件被分成h组：(R1, Rh+1, R2h+1, ), (R2, Rh+2, R2h+2, ), ，(Rh, R2h, R3h,
9、 )，因为各组中记录之间的距离均是h，故第1组至第h组的哨兵位置依次为1h, 2h, , 0。 如果像直接插入排序算法那样，将待插入记录Ri(h+1in)在查找插入位置之前保存到监视哨中，那么必须先计算Ri属于哪一组，才能决定使用哪个监视哨来保存Ri。为了避免这种计算，我们可以将Ri保存到另一个辅助记录x中，而将所有监视哨R1h, R2h, , R0的关键字设置为小于文件中任何关键字即可。因为增量是变化的，所以各趟排序中所需的监视哨数目也不同，但是我们可以按最大增量d来设置监视哨。具体算法描述如下：,2018/10/16,15,rectype Rn+d; /* R0Rd1为d个监视哨 ，d=d
10、0 */ int dt; /* d0dt1为增量序列 */ SHELLSORT(rectype R , int d ) int i, j, k, h; rectype temp; int maxint=32767; /* 机器中的最大整数 */for (i=0; id0; i+) Ri.key= maxint; /* 设置哨兵 */k=0 ; do h=dk; /* 取本趟增量 */for (i=d+h; in+d; i+) /* Rh+dRn+d1插入当前有序区 */ temp=Ri; /* 保存待插入记录 */j=ih; while (temp.keyRj.key) /* 查找正确的插入位
11、置 */ Rj+h=Rj; /* 后移记录 */j=jh; /* 得到前一记录位置 */Rj+h=temp; /* 插入Ri */ /* 本趟排序完成 */k+; while (h!=1); /* 增量为1排序后终止算法 */ /* SHELLSORT,具体算法描述如下：,2018/10/16,16,分析：实质是一种插入排序，比直接插入排序快，但不稳定； 主要特点： 每一趟以不同的增量进行排序。例如第一趟增量为5，第二趟增量为3，第三趟增量为1。在前两趟的插入排序中，记录的关键字是和同一组中的前一个关键字进行比较，由于此时增量取值较大，所以关键字较小的记录在排序过程中就不是一步一步地向前移动，
12、而是作跳跃式的移动。 开始时，增量取值较大，每组中记录较少，故排序比较快； 随后，增量值变小，每组中记录变多，但此时记录已基本有序了，因次在进行最后一趟增量为1的插入排序时，只需作少量的比较和移动便可完成排序，从而提高了排序速度。 如何选择增量序列？希尔本人最初提出取d1=n/2，di+1=di/2，dt=1，t=log2n。后来又有人提出其他选择增量序列的方法，如di+1=(di1)/3，dt=1，t=log3n1 以及di+1=(di1)/2，dt=1，t=log2n1。,2018/10/16,17,3 选择排序（Select Sort）,基本思想：每一趟在待排序的记录中选出关键字最小的记
13、录，依次放在已排序的记录序列的最后，直至全部记录排完为止。直接选择排序和堆排序都归属于此类排序。 本节主要介绍直接选择排序。,2018/10/16,18,直接选择排序基本思想： 第一趟排序是在无序区R0Rn1中选出最小的记录，将它与R0交换； 第二趟排序是在无序区R1Rn1中选关键字最小的记录，将它与R1交换； 第i趟排序时R0Ri2已是有序区，在当前的无序区Ri1Rn1中选出关键字最小的记录Rk，将它与无序区中第1个记录Ri1交换，使R1Ri1变为新的有序区。因为每趟排序都使有序区中增加了一个记录，且有序区中的记录关键字均不大于无序区中记录的关键字，所以，进行n1趟排序后，整个文件就是递增有
14、序的。其排序过程如图14.3所示。,2018/10/16,19,直接选择排序过程,2018/10/16,20,直接选择排序的算法如下： SELECTSORT(rectype R ) /对R0Rn1进行直接选择排序 int i, j, k; rectype temp; for (i=0; in1; i+) / 进行n1趟选择排序 k=i; for (j=i+1; jn; j+) / 在当前无序区选关键字最小的记录Rkif (Rj.keyRk.key) / 稳定性 =？k=j; if (k!=i) /* 交换Ri和Rk */ temp=Ri; Ri=Rk; Rk=temp; /* SELECTSORT */,2018/10/16,21,结论：直接选择排序的比较次数与关键字的初始排列状态无关，第一趟找出最小关键字需要进行n1次比较，第二趟找出次小关键字需要进行n2次比较。因此，总的比较次数为,另外，由于每趟选择后要进行两个记录的交换，而每次交换要进行三次记录的移动，因此，对n个记录进行直接选择排序时，记录移动次数的最大值为3(n1)，最小值为0。综上所述，直接选择排序的时间复杂度为O(n2)。这种排序方法是不稳定的。,
