数据结构第10章内部排序

1、10.1 排序的定义和方法 什么是“排序”？ 简单说，排序是将无序的记录序列调整为有序记录序列的一种操作。 例如，将下列记录序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为序列 14, 23, 36, 49, 52, 58, 61, 75, 80, 97 一般情况下，对排序的定义为：假设含有n个记录的序列为： r1,r2,rn (10-1) 它们的关键字相应为 k1, k2,kn 对式（10-1）的记录序列进行排序就是要确定序号1,2,n的一种排列 P1,P2,Pn 使其相应的关键字满足如下的非递减（或非递增）的关系： (10-2) 就是使式(10-1

2、)的记录序列重新排列成一个按关键字有序的序列 rp1,rp2,rpn (10-3) 当待排序记录中的关键字 (i=1,2,n)都不相同时，则任何一个记录的无序序列经排序后得到的结果是唯一；若待排序的序列中存在两个或两个以上关键字相等的记录，则排序所得到的结果不唯一。 假设ki=kj (1in,1jn,ij)， 且在排序前的序列中，ri 领先于 rj(即ij)。 若在排序后的序列中 ri 仍领先于 rj， 则称所用的排序方法是稳定的稳定的；反之，若可能使排序后的序列中 rj领先于 ri ， 则称所用的排序方法是不稳定的不稳定的 根据涉及的存储器不同，将排序方法分为两大类：1）内部排序内部排序：在

3、排序进行的过程中不使用计算机外部 存储器的排序过程。2）外部排序外部排序：在排序进行的过程中需要对外存进行访 问的排序过程。内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程一趟排序 逐步扩大记录的有序序列长度排序的方法大致有一下几类 ：插入类、交换类、选择类、归并类、其他类将无序子序列中的一个或几个记录插入到有序序列中从而增加记录的有序子序列的长度通过交换无序序列中的记录，从而得到其中关键字最小或最大的记录，并将它加入有序子序列中，以此方法增加有序子序列的长度。从记录的无序子序列中选择关键字最小或最大的记录，并将它加入有序子序列中，以此方法增加有序子序列的长度。通过归并两个

4、或两个以上记录的有序子序列，逐步增加有序子序列的长度。 按排序过程中所需的工作量来分： 1)简单的排序方法 时间复杂度O（n2） 2)先进的排序方法 时间复杂度O（nlogn） 3)基数排序 时间复杂度O（dn）10.2 插入排序 插入排序的准则:在有序序列中插入新的记录以达到扩大有序区的长度的目的。一趟插入排序的基本思想： 由此实现一趟插入排序的步骤为：1) 在 R1.i-1 中查找 Ri 的插入位置，即确定j(0ji)使得 R1.j.keyRi.keyRj+1.i-1.key2) 将 Rj+1.i-1 中的记录后移一个位置；3) 将 Ri 插入到 j+1 的位置。 为了避免在查找过程中判别

5、循环变量是否出界，设置 R0 为监视哨，并在查找的同时进行记录后移，如动画flash10-2-2所示。 算法算法 10.1void InsertPass( SqList &L, int i ) /已知已知L.r1.i-1中的记录已按关键字非递减的顺序有序排列中的记录已按关键字非递减的顺序有序排列, /本算法实本算法实 现将现将L.ri插入其中插入其中,并保持并保持L.r1.i中记录按关键字非中记录按关键字非 /递减顺序有序递减顺序有序L.r0 = L.ri; / 复制为哨兵for ( j=i-1; L.r0.key L.rj.key; -j )L.rj+1 = L.rj; / 记录后移L.rj

6、+1 = L.r0; / 插入到正确位置 / InsertPass具体做法不同可分为以下几种插入排序方法：具体做法不同可分为以下几种插入排序方法：直接插入排序直接插入排序折半插入排序折半插入排序表插入排序表插入排序希尔排序希尔排序缩小增量插入排序10.2.1 直接插入排序直接插入排序直接插入排序利用直接插入排序利用顺序查找顺序查找实现在实现在R1.i-1中查找中查找Ri的插入位置的插入位置 算法算法 10.2void InsertSort( SqList &L, int i ) /对顺序表对顺序表L进行直接插入排序进行直接插入排序 for（i=2;i=L.length;+i） if (L.ri

7、 L.ri-1) L.r0 = L.ri; / 复制为哨兵 for ( j=i-1; L.r0.key L.rj.key; -j ) L.rj+1 = L.rj; / 记录后移 L.rj+1 = L.r0; / 插入到正确位置 / InsertSort最好的情况（关键字记录在序列中顺序有序 ）直接插入排序时间效率分析直接插入排序时间效率分析实现排序的基本操作有两个：实现排序的基本操作有两个：1）比较比较序列中两个关键字的大小序列中两个关键字的大小2）移动移动记录记录最坏的情况（关键字记录在序列中逆序有序 ）比较比较的次数的次数移动移动的次数的次数比较比较的次数的次数移动移动的次数的次数待排记录

8、待排记录序列状态序列状态比较比较次数次数移动移动次数次数正序n-10逆序一般情况下，直接插入排序的时间复杂度为O (n2)。 10.2.2 折半插入排序 由于插入排序的基本思想是在一个有序序列中插入一个新的记录，则可以利用“折半查找”查询插入位置，由此得到的插入排序算法为“折半插入排序”。 如动画flash10-2-3所示演示过程Void BInsertSort (SqList & L)/对顺序表L进行折半插入排序for(i=2;i=L.length;+i) L.r0=L.ri; /将L.ri暂存到 L.r0 low=1;high=i-1; /折半查找插入的位置 while(low=high)

9、 m=(low+high)/2; if (L.r0=high+1;-j) L.rj+1=L.rj; /记录后移 L.rhigh+1=L.r0; /插入/for/BInserSort在L.r1.i-1折半查找插入位置10.2.3 表插入排序表插入排序 为了减少在排序过程中进行移动记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们应该在的位置上 这个静态链表由存储记录的顺序表和附加的指针数组构成，静态链表中的指针实际上指的是数组的下标。 表插入排序分两步进行： 首先构造一个有序链表（循环链表）； 然后按

10、照“附加指针”的指示将结点中的记录重新排列成一个有序序列。 如动画flsh10-2-4 表插入排序的过程举例R1.i-1 已经形成循环链表，Ri为要插入的记录，插入位置为Rj 与Rk之间，k指示为j的指针域所指示单元Ri.next=k; Rj.next=i; Ri.next=k; Rj.next=i; 完成表插入之后，调整重新排列pi为止。10.2.4 希尔排序 希尔排序又称“缩小增量排序”，它的基本思想是，先对待排序列进行“宏观调整”，待序列中的记录“基本有序”时再进行直接插入排序 。 例如一个含11个关键字的序列 (16,25,12,30,47,11,23,36,9,18,31),先对它进

11、行“增量为5”的插入排序 (r1,r6,r11)(r2,r7)(r5,r10)然后将增量“缩小到3”， (r1,r4,r7,r10)(r2,r5,r8,r11) (r3,r6,r9)之后经过最后一趟插入排序即得到有序序列 希尔排序举例 之后经过最后一趟插入排序即得到有序序列 (16,25,12,30,47,11,23,36,9,18,31)(11,23,12,9,18,16,25,36,30,47,31)先对它进行“增量为5”的插入排序然后将增量“缩小到3”(9, 18,12, 11, 23,16,25,31,30,47,36)(9, 11, 12, 16,18, 23, 25, 30,31,

12、 36,47)过程如动画flash10-2-5算法参见教材P272 算法10.4-10.510.3 交换排序法 起泡排序是交换类排序方法中的一种简单排序方法。基本思想为：依次比较相邻两个记录的关键字，若和所期望的相反，则互换这两个记录。如动画flash10-3-1 10.3.1 起泡排序 起泡排序的过程： 首先第一个记录的关键字和第二个记录的关键字比较，若逆序，则两个记录交换，然后比较第二个记录和第三个记录的关键字。以此类推，直到第n-1个记录和第n个记录的关键字进行比较为止。上述这个过程称为第一趟气泡排序。结果是关键字最大的记录落在最后一个位置上。 整个排序过程需要进行K趟起泡排序。 结束的

13、条件是： 在一趟排序过程中没有进行交换记录的操作。例如：如动画flash10-3-210.3.2 快速排序快速排序 快速排序则是通过一趟排序选定一个关键字介于中间的记录，从而使剩余记录可以分成两个子序列分别继续排序，通常称该记录为枢轴。 一趟快速排序的具体做法： 附设两个指针low和high，初始值分别为low和high，枢轴记录的关键字为piovtkey，首次从high所指位置向前搜索到第一个关键字小于piovtkey的记录和枢轴记录互相交换，然后从low向后搜索第一个关键字大于piovtkey的记录和枢轴记录互相交换。重复这两步，直至low=high为止。 算法参见教材P274 算法10.

14、6例如，关键字序列 ( 52, 49, 80, 36, 14, 75, 58, 97, 23, 61 )经第1趟快速排序之后为 ( 23, 49, 14, 36) 52 (75, 58, 97, 80, 61 )经第2趟快速排序之后为 ( 14) 23 (49, 36) 52 (61, 58) 75 (80, 97 )经第3趟快速排序之后为 ( 14, 23, 36, 49, 52, 58, 61, 75, 80, 97 )一趟快排也称“一次划分”，即将待排序列 Rs.t“划分”为两个子序列Rs.i-1 和 Ri+1.t，i 为一次划分之后的枢轴位置。 如动画flsah10-3-410.4 选

15、择排序法 10.4.1 简单选择排序 选择排序的基本思想：在待排区段的记录序列中选出关键字最大或最小的记录，并将它移动到法定位置。 第 i趟简单选择排序的作法：在后 n-i+1 个记录中选出关键字最小的记录，并将它和第 i 个记录进行互换。如图所示。 时间性能：对n个记录的关键字进行简单选择排序，所需进行的关键字比较次数总计为移动记录的次数最小值为0 ，最大值为3(n-1)时间复杂度为O（n2）10.4.2 堆排序 何谓“堆”？堆是满足下列性质的n个元素的序列 k1,k2,kn 满足下列关系则称作小顶堆 或大顶堆“堆顶” 元素为序列中的“最小值”或“最大值“小顶堆大顶堆 利用堆的特性进行的排序

16、方法即为“堆排序” 其排序过程如下：假设待排关键字序列为： 34, 39, 20, 65, 47, 12, 98, 73, 81, 56 1）先将它调整为大顶堆： 98, 81, 34, 73, 56, 12, 20, 39, 65, 47 2）互换“堆顶”和待排序列中 的最后的关键字： 47, 81, 34, 73, 56, 12, 20, 39, 65, 98 3）在待排序列中舍去最大关键字，将其余部 分重新调整为堆 81, 73, 34, 65, 56, 12, 20, 39, 47 98 4）重复2）和3）直至待排序列中只剩一个关键字为止。可见，堆排序的两个关键问题是：1） 如何将一个

17、无序序列调整为堆？2）如何在互换堆顶之后重新调整为堆？ 先讨论第二个问题:只要 “从上到下” 进行 “筛选” 可将该序列重新调整为大顶堆。如动画flash10-4-2如何建堆？建堆的过程是一个从下到上调整堆的过程。 例如动画 flash10-4-4所示对无序序列进行建堆的过程。教材p282 算法10.10 调整堆的过程教材p282 算法10.11 堆排序过程堆排序的时间复杂度分析 1）对深度为k的堆，筛选所进行的关键字比较的次数至多为2(k-1)。2）对n个关键字建成深度为h的堆，所需进行的关键字比较的次数至多为4(n)。3）调整堆顶n-1次，总共进行的关键字比较次数不超过堆排序的时间复杂度为

18、O(nlogn)10.5 归并排序法 10.5.1 2-路归并排序 归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。 2-路归并排序则是归并排序中的一种最简单的情况，它的基本操作是将两个相邻的有序子序列“归并”为一个有序序列 如动画flash10-5-2所示void MSort (RcdType SR, RcdType TR1, int s,int t)/将SRs.t归并序列为TR1s.tif (s=t) TR1s= SRs;else m=(s+t)/2; /将SRs.t平分为和SRm+1.t MSort(SR,TR2,s,m); /递归的将SRs.m归并为有序的TR2s

19、.m MSort(SR,TR2, m+1,s);/递归的将SRm+1.t归并为有序的TR2m+1.t Merge(TR2, TR1, s,m,t);/将TR2s.mTR2m+1.t归并到TR1s.t/else/MSortvoid MergSort (SqList &L) /对顺序表L作归并排序 MSort（L.r，L.r,1,L.length）; / MergSort10.6 基数排序 10.6.1 多关键字的排序 一般情况下，对多关键字排序的定义为： 假设含有 n 个记录的序列为：（R1,R2,Rn） 每个记录 Ri 中含有 d 个关键字(Ki0,Ki1,Kid-1)则称该记录序列对关键字

20、(Ki0,Ki1,Kid-1 )有序是指： 对于序列中任意两个记录 Ri 和 Rj（1ijn）都满足下列有序关系 (Ki0,Ki1,Kid-1) ( Kj0,Kj1,Kjd-1 ) 其中 K0 为最主位关键字，Kd-1 为最次位关键字。 假如你手中有一副扑克牌，若要将它们排列成一个有序序列，你准备怎么做？ 通常实现多关键字排序可以有两种策略： 一是最主位优先主位优先（MSD法） 一是最次位优先最次位优先（LSD法） 你可能是先按不同“花色” 分成有次序的四堆，然后分别对每一堆按“面值” 大小（23A）排列有序。若将花色视作K0，将 面值 视作K1，这种整理方法即为MSD的作法。 例如，对含（系

21、别、班号和班内序列号）三个关键字的记录序列按“最低位优先”进行排序。 过程 如动画flash10-6-1所示 10.7 各种排序方法的综合比较 一、 时间性能 1. 按平均的时间性能来分，有三类排序方法：时间复杂度为O (nlogn) 的方法有： 快速排序、堆排序和归并排序时间复杂度为O (n2) 的有： 插入排序、起泡排序和选择排序，时间复杂度为O (n) 的排序方法只有基数排序一种。其中快速排序目前被认为是最快的一种排序方法，后两者之比较，在 n 值较大的情况下，归并排序较堆排序更快；其中以插入排序为最常用，特别是对于已按关键字基本有序排列的记录序列尤为如此，选择排序过程中记录移动次数最少

22、 2. 当待排记录序列按关键字顺序有序时，插入排序和起泡排序能达到O (n)的时间复杂度；而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O (n2)，因此应尽量避免。3. 选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。 4. 以上对排序的时间复杂度的讨论主要考虑排序过程中所需进行的关键字间的比较次数，当待排序记录中其它各数据项比关键字占有更大的数据量时，还应考虑到排序过程中移动记录的操作时间，有时这种操作的时间在整个排序过程中占的比例更大，从这个观点考虑，简单排序的三种排序方法中起泡排序效率最低。二、空间性能二、空间性能指的是排序过程中所需的辅助空间大小。 1. 所有的简单排序方法（包括：插入、起泡和选择排序）和堆排序的空间复杂度均为O (1)。2. 快速排序为O (logn)，为递归程序执行过程中栈所需的辅助空间。3.