中国计量学院数据结构第10章 排序

1、第十章 内部排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 选择排序选择排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种排序方法的综合比较各种排序方法的综合比较10.1 概概 述述一、何为排序一、何为排序二、内部排序和外部排序二、内部排序和外部排序三、内部排序方法的分类三、内部排序方法的分类一、何为排序？一、何为排序？将一组“无序无序”的记录序列调整为“有序有序”的记录序列。例如：将如下序列52, 49, 80, 36, 14, 58, 61, 23, 97, 75调整为14, 23, 36, 49, 52, 58, 61 ,75, 8

2、0, 97二、内部排序和外部排序二、内部排序和外部排序 整个排序过程不需要访问外存不需要访问外存便能完成，则为内部排序内部排序； 反之，若参加排序的记录很多，整个排序过程不可能在内存中完成，称为外部排序外部排序。三、内部排序的方法三、内部排序的方法内部排序内部排序的过程实质是一个逐步逐步扩大有序序列长度扩大有序序列长度的过程。经过一趟排序经过一趟排序有序序列区无 序 序 列 区有序序列区无 序 序 列 区基于不同的“扩大扩大” 有序序列长度的方法，方法，内部排序内部排序大致可分下列几种类型：插入类插入类交换类交换类选择类选择类归并类归并类其它方法其它方法1. 插入类插入类将无序子序列中的一个（

3、或几个）“插入插入”到有序序列中，从而增加有序子序列的长度。2. 交换类交换类通过“交换交换”无序序列中的记录以得到其中最小或最大记录，将它加入到有序子序列中，从而增加有序子序列的长度。3. 选择类选择类从记录的无序子序列中“选择”最小或最大的记录，将它加入到有序子序列中，从而增加有序子序列的长度。4. 归并类归并类 通过“归并归并”两个或两个以上的记录有序子序列，逐步增加有序序列的长度。5. 其它方法其它方法 10. 2 插插 入入 排排 序序有序序列R1.i-1Ri无序序列 Ri.n插入排序的基本思想有序序列R1.i无序序列 Ri+1.n（一趟）（一趟）插入排序插入排序分三步走：分三步走：

4、3将Ri 插入插入到Rj+1的位置上。2将Rj+1.i-1中的所有记录所有记录均后移后移一个位置；1在R1.i-1中查找查找Ri的插入位置，即 R1.j.key Ri.key Rj+1.i-1.key；直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）不同的实现方法导致不同的算法不同的实现方法导致不同的算法折半插入排序折半插入排序（基于折半查找）（基于折半查找）希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）一、直接插入排序一、直接插入排序利用 “顺序查找顺序查找”实现在R1.i-1中查找查找Ri的插入位置。void InsertionSort ( SqList &L ) / 对

5、顺序表 L 作直接插入排序。 for ( i=2; i=L.length; +i ) if (L.ri.key L.ri-1.key) / InsertionSortL.r0 = L.ri; / 设置监视哨for ( j=i-1; L.r0.key L.rj.key; - j ) L.rj+1 = L.rj; / 记录后移L.rj+1 = L.r0; / 插入到正确位置 因为 R1.i-1 是一个有序序列，因此可以利用折半查找折半查找在R1.i-1中找出Ri的插入位置。称这种排序为折半插入排序折半插入排序。二、折半插入排序二、折半插入排序void BiInsertionSort ( SqLis

6、t &L ) / BiInsertionSort在在 L.r1.i-1中折半查找插入位置；中折半查找插入位置；for ( i=2; i=high+1; -j ) L.rj+1 = L.rj; / 记录后移L.rhigh+1 = L.r0; / 插入low = 1; high = i-1;while (low=high) m = (low+high)/2; / 折半if (L.r0.key L.rm.key) high = m-1; / 插入点在低半区else low = m+1; / 插入点在高半区三、希尔排序三、希尔排序(又称缩小增量排序又称缩小增量排序)也是一种插入排序方法，但时间复杂度也

7、是一种插入排序方法，但时间复杂度有较大改进有较大改进基本思想基本思想对无序序列先作对无序序列先作“宏观宏观”调整，后作调整，后作“微观微观”调整调整所谓所谓“宏观宏观”调整，指的是，调整，指的是，“跳跃式跳跃式”的插入排序的插入排序将序列分成若干子序列，对每个子序列进行插入排序。其中，d 称为增量，它的值在排序过程中逐渐缩小，直至为 1 例如：将 n 个记录分成 d 个子序列： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 增量为增量为5 5原始序列原始序列81819494111196961212353517179

8、59528285858414175751515子序列子序列1 18181 3535 4141 子序列子序列2 29494 1717 7575 子序列子序列3 31111 9595 1515子序列子序列4 49696 2828 子序列子序列5 51212 5858 结果结果子序列子序列1 13535 4141 8181 子序列子序列2 21717 7575 9494 子序列子序列3 31111 1515 9595子序列子序列4 42828 9696 子序列子序列5 51212 5858 原始序列原始序列35351717111128281212414175751515969658588181949

9、49595增量为增量为3 3原始序列原始序列35171128124175159658819495子序列子序列1 135 28 75 58 95子序列子序列2 217 12 15 81 子序列子序列3 311 41 96 94 结果结果子序列子序列1 128 35 58 75 95子序列子序列2 212 15 17 81 子序列子序列3 311 41 94 96 原始序列原始序列28121135154158179475819695增量为增量为1 1原始序列原始序列28121135154158179475819695子序列子序列1 111121517283441587581949596void S

10、hellInsert ( SqList &L, int d ) for ( i=d+1; i=n; +i ) if ( L.ri.key0&(L.r0.keyL.rj.key); j-=d) L.rj+d = L.rj; / 记录后移，查找插入位置 L.rj+d = L.r0; / 插入 / if / ShellInsertvoid ShellSort (SqList &L, int delta, int t) / 增量为delta的希尔排序 for (k=0; kt; +t) ShellInsert(L, deltak); /一趟增量为deltak的插入排序 / ShellSort 首先对无

11、序序列进行“划分划分”，之后将两个子序列“递归递归”进行快速排序进行快速排序。无 序 的 记 录 序 列无序子序列 1无序子序列 2枢轴枢轴划分分别进行快速排序10.3 快快 速速 排排 序序int partition(int a, int left, int right) /划分划分 int low = left; int high = right; int key = alow; /第一个记录作为枢轴第一个记录作为枢轴 while(low high) while(low = key) high-; alow = ahigh; /将比枢轴小的移到低端将比枢轴小的移到低端 while(low

12、high & alow = right) return; s=partition(a, left, right); Qsort(a, left, s-1); /排序前半部分排序前半部分 Qsort(a, s+1, right); /排序后半部分排序后半部分10.4 选选 择择 排排 序序简 单 选 择 排 序堆 排 序树 形 选 择 排 序一、简单选择排序一、简单选择排序有序序列R1.i-1无序序列 Ri.n 第第 i 趟趟从中选出最小的记录有序序列R1.i无序序列 Ri+1.nvoid SelectSort (Elem R, int n ) / 对记录序列R1.n作简单选择排序。 for (

13、i=1; in; +i) / SelectSortj = SelectMinKey(R, i); / 在 Ri.n 中选择最小的记录if (i!=j) RiRj; /交换交换二、树形选择排序二、树形选择排序按照锦标赛思想进行的选择排序。三、堆排序三、堆排序堆满足下列性质的序列r1, r2, ，rn：或或122iiiirrrr122iiiirrrr12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49例如例如:是是小顶堆小顶堆12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49不是堆不是堆(小顶堆小顶堆)(大顶堆大顶堆)rir2i r

14、2i+1 若将该序列视作完全二叉树，则 r2i 是 ri 的左孩子， r2i+1 是 ri 的右孩子。1236276549817355403498例如例如:是堆是堆14不不堆排序堆排序 小顶（根）堆 堆顶是最小值，输出并从堆上删除， 调整剩余的n-1个数据元素序列，使之再次成为小顶堆，即可得到次小值 如此反复执行，便能得到一个有序序列 大顶（根）堆 堆排序的步骤 建立堆 删除根（具有最小/大值） 根和最后一个元素交换（不再是堆） 筛选：调整完全二叉树，使之成为堆所谓“筛选筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整调整”根结点根结点使整个二叉树也成为一个堆。堆堆筛选筛选988149

15、73556412362740例如例如:是大顶堆是大顶堆12但在 98 和 12 进行互换之后，它就不不是堆了，因此，需要对它进行“筛选”。98128173641298比较交换建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。的过程。40554973816436122798例如例如: 排序之前的关键字序列为123681734998817355 现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。98494064361227从哪个结点开始筛选？从哪个结点开始筛选？最后一个非叶子结点最后一个非叶子结点堆排序即是利用堆排序即是利用堆的特性堆的特性对记录序列对记

16、录序列进行排序的一种排序方法。进行排序的一种排序方法。例如：例如：建大顶堆 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 交换 98 和 12重新调整为大顶堆 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 经过筛选定义堆类型为定义堆类型为:typedef SqList HeapType; / 采用顺序表表示 void HeapAdjust (RcdType &R, int s,

17、 int m) / 已知 Rs.m中记录的关键字除 Rs 之外均 / 满足堆的特征，本函数自上而下调整 Rs 的 / 关键字，使 Rs.m 也成为一个大顶堆 / HeapAdjustrc = Rs; / 暂存 Rs for ( j=2*s; j= Rj.key ) break; / 再作“根”和“子树根”之间的比较， / 若“=”成立，则说明已找到 rc 的插 / 入位置 s ，不需要继续往下调整 Rs = Rj; s = j; / 否则记录上移，尚需继续往下调整if ( jm & Rj.key0; -i ) HeapAdjust ( H.r, i, H.length ); / 建大顶堆for

18、 ( i=H.length; i1; -i ) H.r1H.ri; / 将堆顶记录和当前无序序列 / H.r1.i中最后一个记录相互交换 HeapAdjust(H.r, 1, i-1); / 对 H.r1 进行筛选10.5 归归 并并 排排 序序归并排序的过程基于下列基本思基本思想想： 将两个或两个以上的有序子序列 “归并”为一个有序序列。通常采用的是2-路归并排序。即：将两个位置相邻位置相邻的有序子序列归并为一个一个有序序列。有有 序序 序序 列列 Ri.n有序子序列有序子序列 Ri.m有序子序列有序子序列 Rm+1.n这个操作对顺序表而言，是轻而易举的。SRmm+1nTR12ikj1529

19、2240 516063418470for (k=i, j=m+1; i=m & j=n; +k) / 将SR中记录由小到大地并入TR if (SRi.key=SRj.key) TRk = SRi+; else TRk = SRj+; void Merge (RcdType SR, RcdType &TR, int i, int m, int n) / 将有序的记录序列 SRi.m 和 SRm+1.n / 归并为有序的记录序列 TRi.n / Mergefor (k=i, j=m+1; i=m & j=n; +k) / 将SR中记录由小到大地并入TR if (SRi.key=SRj.key) T

20、Rk = SRi+; else TRk = SRj+; if (i=m) TRk.n = SRi.m; / 将剩余的 SRi.m 复制到 TRif (j=n) TRk.n = SRj.n; / 将剩余的 SRj.n 复制到 TR归并排序的算法归并排序的算法如果无序序列 Rs.t 的两部分 Rs. (s+t)/2 和 R (s+t)/2 +1.t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个序列是一个有序序列。 因此，应该先分别对这两部分进行 2-路归并排序。例如：例如：52, 23, 80, 36, 68, 14 (s=1, t=6) 52, 23, 80 36, 68, 14 5

21、2, 2380 52 23, 52 23, 52, 8036, 6814366836, 6814, 36, 68 14, 23, 36, 52, 68, 80 23归归并并归归并并void Msort ( RcdType SR, RcdType &TR1, int s, int t ) / 将SRs.t 归并排序为 TR1s.t if (s= =t) TR1s=SRs; else / Msort m = (s+t)/2; / 将SRs.t平分为SRs.m和SRm+1.tMsort (SR, TR2, s, m); / 递归地将SRs.m归并为有序的TR2s.mMsort (SR, TR2, m

22、+1, t); /递归地SRm+1.t归并为有序的TR2m+1.tMerge (TR2, TR1, s, m, t); / 将TR2s.m和TR2m+1.t归并到TR1s.tvoid MergeSort (SqList &L) / 对顺序表 L 作2-路归并排序 MSort(L.r, L.r, 1, L.length); / MergeSort容易看出，对 n 个记录进行归并排序的时间复杂度为(nlogn)。即： 每一趟归并的时间复杂度为 O(n)， 总共需进行 log2n 趟。10.6 基基 数数 排排 序序基数排序基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法

23、。多关键字的排序多关键字的排序链式基数排序链式基数排序一、多关键字的排序一、多关键字的排序 n 个记录的序列个记录的序列 R1, R2, ，Rn对关键字对关键字 (Ki0, Ki1, ,Kid-1) ) 有序有序是指： 其中其中: : K0 被称为被称为 “最主最主”位关键字位关键字Kd-1 被称为被称为 “最次最次”位关键字位关键字 对于序列中任意两个记录 Ri 和 Rj(1ijn) 都满足满足下列(词典词典)有序有序关系： (Ki0, Ki1, , ,Kid-1) ) (Kj0, Kj1, , ,Kjd-1) )多关键字排序通常有两种做法最低位优先最低位优先LSD法法最高位优先最高位优先M

24、SD法 先对先对K0进行排序进行排序，并按 K0 的不同值将记录序列分成若干子序列之后，分别对 K1 进行排序，.， 依次类推，直至最后对最次位关键字排序完直至最后对最次位关键字排序完成为止成为止。 先对 Kd-1 进行排序，然后对 Kd-2 进行排序， .，依次类推，直至对直至对最主位关键字最主位关键字 K0 排序完成为止排序完成为止。假设假设学生记录含三个关键字:系别系别、班号班号和班内的序列号班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下: 无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,301,2,153,1,202,3,182,1,201,2,1

25、52,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30二、链式基数排序二、链式基数排序假如多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配分配- -收集收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字单关键字，可以看成看成是由多个数位或多个字符构成的多关键多关键字字，采用采用这种“分配分配- -收集收集”的办法进行排序进行排序，称作基数排序法称作基数排序法。例如：例如：对下列这组关键字 209, 386, 768

26、, 185, 247, 606, 230, 834, 539 首先按其 “个位数”取值分别为 0, 1, , 9“分配分配” 成 10 组，之后按从 0 至 9 的顺序将它们 “收集” 在一起； 然后按其 “十位数”取值分别为 0, 1, , 9 “分配分配” 成 10 组，之后再按从 0 至 9 的顺序将它们 “收集收集” 在一起；最后按其“百位数”重复一遍上述操作。实现基数排序时，为减少辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为： 待排序记录以指针相链，构成一个链表；“分配” 时，按当前“关键字位”取值，将记录分配到不同的 “链队列” 中，每个队列中的“关键字位” 相同

27、；“收集”时，按当前关键字位取值从小到大将各队列首尾相链，构成一个链表;对每个关键字位均重复 2 和 3 两步。例如：p369367167239237138230139进行第一次分配进行第一次分配进行第一次收集进行第一次收集f0 r0f7 r7f8 r8f9 r9p230230367 167237367167237138368239139369 239139138进行第二次分配进行第二次分配p230237138239139p230367167237138368239139f3 r3f6 r6230 237138239139367 167368367167368进行第二次收集 进行第三次收集之后便得到记录的有序序列进行第三次收集之后便得到记录的有序序列f1 r1p230237138239139367167368进行第三次分配进行第三次分配f2 r2f3 r3138 139167230 237239367 368p138139167230237239367368 基数排序的时间复杂度为基数排序的时间复杂度为O(d(n+rd)其中：分配为O(n) 收集为O(rd)(rd为“基”) d为“分配-收集”的趟数10.7 各种排序方法的