排序概述

《排序概述》由会员分享，可在线阅读，更多相关《排序概述（110页珍藏版）》请在金锄头文库上搜索。

1、10. 排序110.1 概述 1、排序的定义：排序是将一个数据元素的任意序列，重新排列 成一个按关键字有序的序列。（升序、降序） 2、排序的稳定性：如任何关键字相同的记录的先后次序不因排序 而发生改变，则称所用的排序方法是稳定的。否则 是不稳定的。 排序前：9 5 9 1 6 排序后：1 5 6 9 9 （稳定的） 排序后：1 5 6 9 9 （不稳定的）23、排序的分类： 按排序所使用的存储器不同可把排序分为： (1)内部排序：整个排序过程都在内存进行的排序。 (2)外部排序：当文件很大以致内存不足以存放全部 记录，需要对外存进行存取访问的排序。 4、排序方法的分类： (共五大类，12种)

2、(1)插入排序：直接插入排序、折半插入排序、2-路插入排序、表插入排序、希尔排序。 (2)交换排序：起泡排序、快速排序。 (3)选择排序：简单选择排序、树形选择排序、堆排序。 (4)归并排序：2-路归并排序。 (5)基数排序：链式基数排序。 35、按排序所需工作量的分类： (1)简单的排序方法：T(n)=O(n) (2)先进的排序方法：T(n)=O(nlogn) (3)基数排序：T(n)=O(d.n) 6、排序所需的两种基本操作 (1)比较：比较两个关键字的大小 (2)交换：将记录从一个位置移动到另一个位置 7、存储空间的存储方式 (1)顺序存储方式：把待排记录存放到数组中。 (2)静态链表方

3、式：把待排记录存放到静态链表中 。(表排序) (3)链式存储方式：把待排记录存放到链表中。（ 地址排序）4待排记录的数据类型定义如下:#define MAXSIZE 1000 / 待排顺序表最大长度typedef int KeyType; / 关键字类型为整数类型typedef struct KeyType key; / 关键字项InfoType otherinfo; / 其它数据项 RcdType; / 记录类型typedef struct RcdType rMAXSIZE+1; / r0闲置int length; / 顺序表长度 SqList; / 顺序表类型510.2 插入排序6有序序列

4、R1.i-1Ri无序序列 Ri.n一趟直接插入排序的基本思想：有序序列R1.i无序序列 Ri+1.n7实现“一趟插入排序”可分三步进行：3将Ri 插入(复制)到Rj+1的位置上。2将Rj+1.i-1中的所有记录均后移一个位置；1在R1.i-1中查找Ri的插入位置，R1.j.key Ri.key =high+1; -j )L.rj+1 = L.rj; / 记录后移L.rhigh+1 = L.r0; / 插入17low = 1; high = i-1;while (low0 iL.rj+1) t=L.rj; L.rj=L.rj+1; L.rj+1=t; flag=1; if (flag=0) br

5、eak; 30时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡“比较”的次数：0“移动”的次数：“移动”的次数：n-1311、一趟快速排序（一次划分）目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之 ，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列Rs.t将分割 成两部分：Rs.i-1和Ri+1.t，且 Rj.key Ri.key Rj.key(sji-1) 枢轴 (i+1jt)。10.3.2 快速排序32stlowhigh设

6、Rs=52 为枢轴将 Rhigh.key 和 枢轴的关键字进行比较，要求 Rhigh.key 枢轴的关键字将 Rlow.key 和 枢轴的关键字进行比较，要求 Rlow.key 枢轴的关键字high23low80high14low52例如R052lowhighhighhighlow33可见，经过“一次划分” ，将关键字序列52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75在调整过程中，设立了两个指针： low 和 high，它们的初值分别为： s 和 t， 之后逐渐减小 high

7、，增加 low，并保证 Rhigh.key52，和 Rlow.key52,否则进行记录的“交换”。34int Partition (RedTypewhile (low=pivotkey) -high;RlowRhigh; while (low=pivotkey)- high; / 从右向左搜索Rlow = Rhigh;while (low= H.rj.key) break; H.rs = H.rj; s = j;H.rs = rc; 74算法10.11 void HeapSort(HeapType i0; -i) HeapAdjust ( H, i, H.length );for (i=H.l

8、ength; i1; -i) temp=H.ri;H.ri=H.r1;H.r1=temp; HeapAdjust(H, 1, i-1); 7510.5 归 并 排 序归并排序的过程基于下列基 本思想进行：将两个或两个以上的有序子序 列 “归并” 为一个有序序列。76在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录的有序序列。有 序 序 列 Rl.n有序子序列 Rl.m有序子序列 Rm+1.n这个操作对顺序表而言，是轻而易举的。772-路归并排序排序过程：设初始序列含有n个记录，则可 看成n个有序的子序列，每个子序列长度为1。两 两合并，得到n/2个长度

9、为2或1的有序子序列。 再两两合并，如此重复，直至得到一个长度 为n的有序序列为止。78例: 初始关键字： 49 38 65 97 76 13 27一趟归并后： 38 49 65 97 13 76 27二趟归并后： 38 49 65 97 13 27 76三趟归并后： 13 27 38 49 65 76 9779void Merge (RcdType SR, RcdType i=m +k) / 将SR中记录由小到大地并入TRif (SRi.key=SRj.key) TRk = SRi+;else TRk = SRj+; 80if (i=m) TRk.n = SRi.m;/ 将剩余的 SRi.m

10、 复制到 TRif (j=n) TRk.n = SRj.n;/ 将剩余的 SRj.n 复制到 TR81归并排序的算法如果记录无序序列 Rs.t 的两部分 Rs.(s+t)/2 和 R(s+t)/2+1.t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列。由此，应该先分别对这两部分进行 2-路归并排序。82void Msort ( RcdType SR, RcdType else / Msort 83m = (s+t)/2;/ 将SRs.t平分为SRs.m和SRm+1.tMsort (SR, TR2, s, m);/ 递归地将SRs.m归并为有序的TR2s.m M

11、sort (SR, TR2, m+1, t);/递归地SRm+1.t归并为有序的TR2m+1.tMerge (TR2, TR1, s, m, t);/ 将TR2s.m和TR2m+1.t归并到TR1s.t84void MergeSort (SqList / MergeSort容易看出，对 n 个记录进行归并排序的时间 复杂度为(nlogn)。即：每一趟归并的时间复杂度为 O(n)，总共需进行 log2n 趟。8510.6 基 数 排 序86例: 对52张扑克牌按以下次序排序： 23A23A 23A23A 两个关键字：花色（ ）面值（23A） 并且“花色”地位高于“面值”。1、定义：87基数排序是

12、一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。多关键字的排序链式基数排序88一、多关键字的排序n 个记录的序列 R1, R2, ，Rn对关键字 (Ki0, Ki1,Kid-1) 有序是指：其中: K0 被称为 “最主”位关键字Kd-1 被称为 “最次”位关键字对于序列中任意两个记录 Ri 和 Rj(1ijn) 都满足下列(词典)有序关系：(Ki0, Ki1, ,Kid-1) (Kj0, Kj1, ,Kjd-1)89实现多关键字排序通常有两种作法:最低位优先LSD法最高位优先MSD法先对K0进行排序，并按 K0 的不同值将记录序列分成若干子序列之后，分别对 K1 进行排序，

13、.， 依次类推，直至最后对最次位关键字排序完成为止。90先对 Kd-1 进行排序，然后对 Kd-2 进行排序，依次类推，直至对最主位关键字 K0 排序完成为止。排序过程中不需要根据 “前一个” 关键字的排序结果，将记录序列分割成若干个(“前一个”关键字不同的)子序列。最低位优先LSD法91例如:学生记录含三个关键字: 系别、班号和班内的序列号，其中以系别为最主 位关键字。无序序列对K2排序对K1排序对K0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,181,2,

14、152,1,202,3,183,1,203,2,30LSD的排序过程如下:92二、链式基数排序假如多关键字的记录序列中，每个关键字 的取值范围相同，则按LSD法进行排序时，可 以采用“分配-收集”的方法，其好处是不需要进行关键字间的比较。对于数字型或字符型的单关键字，可以看成 是由多个数位或多个字符构成的多关键字，此时 可以采用这种“分配-收集”的办法进行排序，称作基数排序法。93例如：对下列这组关键字209, 386, 768, 185, 247, 606, 230, 834, 539 首先按其 “个位数” 取值分别为 0, 1, , 9 “分配” 成 10 组，之后按从 0 至 9 的顺序将 它们 “收集” 在一起；然后按其 “十位数” 取值分别为 0, 1, , 9 “分配” 成 10 组，之后再按从 0 至 9 的顺序将它们 “收集” 在一起；最后按其