数据结构及应用算法教程（修订版） 第3章 排序.ppt

《数据结构及应用算法教程（修订版） 第3章 排序.ppt》由会员分享，可在线阅读，更多相关《数据结构及应用算法教程（修订版） 第3章 排序.ppt（50页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第3章 排序 3.1 概述 3.2 简单排序 3.3 先进排序 3.4 基数排序 3.5 各种排序方法的综合比较,3.1 概 述 排序的定义 排序的稳定性 排序的分类 内部排序方法的分类 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 ,其相应的关键字序列为 K1, K2, ，

2、 Kn 对上述的记录序列排序就是确定序号1, 2, ,n的一种排列, p1, p2, , pn,使其相应的关键字满足如下的非递减的关系： Kp1Kp2Kpn 也就是使上述的记录序列成为一个按关键字有序的序列 Rp1, Rp2, ，Rpn 的操作称作排序。,2、排序的稳定性 当待排序记录中的各关键字ki ( i=1,2,n )都不相同时，排序结果惟一；当待排序记录中存在两个或两个以 上关键字相等的记录时，排序结果不惟一。 稳定性： 假设关键字ki=kj(ni1, 1jn,ij),并且在排序前记录ri领先rj, 若在排序后ri仍领先rj，则称排序是稳定 的；否则，称排序是不稳定的。,3、排序的分类

3、：内部排序和外部排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之, 若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类 排序问题为外部排序。 4、内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。通常在排序的过程中，参与排序的记录序列中可 划分为两个区域： 1.有序序列区：其中的记录按关键字非递减有序。 2.无序序列区,一趟排序：使有序序列区中记录的数目增加一个或几个的操作，称为一趟排序。 基于不同的“扩大” 有序序列长度的方法，内部排序方法大致可分下列几种类型： 简单排序 先进排序 基数排序,待排记录的数据类型定义如下:

4、const MAXSIZE=20; / 待排顺序表最大长度 typedef int KeyType; / 关键字类型为整数类型 typedef struct KeyType key; / 关键字项 InfoType otherinfo; / 其它数据项 RcdType; / 记录类型 typedef struct RcdType rMAXSIZE+1; / r0闲置 int length; / 顺序表长度 SqList; / 顺序表类型,3.2 简单排序 选择排序 插入排序 起泡排序 希尔排序 各种排序方法的学习要点： 掌握基本思想 举例说明排序过程 书写算法 稳定性的判断 时间复杂度的分析,

5、3.2.1 选择排序 1、基本思想：从无序序列区Ri到Rn的n-i+1个记录中选出关键字最小的记录Rj和Ri交换，从而使有序序列区从R1到Ri-1扩大至R1到Ri。 2、举例： 一组关键字(491,38,65,492,76,13,27,52)进行选择排序。 初始( ) i=1 (13), 38, 65, 492, 76, 491, 27, 52 i=2 (13, 27), 65, 492, 76, 491, 38, 52 i=3 (13, 27, 38), 492, 76, 491, 65, 52 i=4 (13, 27, 38, 492) ,76, 491, 65, 52 i=5 (13,

6、27, 38, 492, 491) 76, 65, 52 i=6 (13, 27, 38, 492, 491, 52), 65, 76 i=7 (13, 27, 38, 492, 491, 52, 65),76,3、一趟选择排序算法（算法 3.1） void SelectPass( SqList k+ ) if ( L.rk.key L.rj.key ) j = k ； / 暂不进行记录交换，只记录位置 if ( i != j ) W=L.rj；L.rj =L.ri；L.ri = W； / 最后互换记录Rj 和Ri / SelectPass,算法 3.2 void SelectSort (Sq

7、List k+ ) / 在L.ri.L.length中选择key最小的记录 if ( L.rk.key L.rj.key ) j =k ； if ( i!=j ) W=L.rj；L.rj =L.ri；L.ri = W； / 与第i个记录交换 / SelectSort 4、稳定性：稳定的 5、时间复杂度：O(n2),3.2.2 插入排序 1、基本思想：是将当前无序序列区Ri到Rn中的记录Ri插入到有序序列区R1到Ri-1中，使有序序列区的长度增1。,2、举例 一组关键字(38,49, 65, 76, 27, 13, 91, 52)进行插入排序。此记录序列中的前4个记录已按关键字非递减有序排列，构

8、成了一个含有4个记录的有序序列：(38, 49, 65, 76)，现要将第5个(关键字为27)记录插入到上式的序列中去，以得到一个新的含5个记录的有序序列： ( 27, 38, 49, 65, 76)，称这个过程为一 趟插入排序。 3、一趟插入排序算法（算法 3.3） 实现“一趟插入排序”可分三步进行： （1）在R1.i-1中查找Ri的插入位置，R1.j.key Ri.key Rj+1.i-1.key； （2）将Rj+1.i-1中的所有记录均后移一个位置； （3）将Ri 插入(复制)到Rj+1的位置上。,利用L.r0分量“复制”待插入的记录，则在向前查找插入位置时，循环变量就不可能发生出界的情

9、况,称L.r0为“监视哨”。 void InsertPass( SqList / 插入到正确位置 / InsertPass,分析：（1）整个插入排序需进行n-1趟“插入”。（2）只含一个记录的序列必定是有序序列，故插入应从i=2起进行。（3）若第i个记录的关键字不小于第i-1个记录的关键字，插入就不不需要进行了。 void InsertSort ( SqList / 插入到正确位置 / if / InsertSort,4、稳定性：稳定的 5、时间复杂度：O(n2) (最坏情况: ) 3.2.3 起泡排序 1、基本思想：是通过对无序序列区中的记录进行相邻记录关键字间的“比较”和记录位置的“交换”

10、实现关键字较小的记录向“一头”飘移，而关键字较大的记录向“另一头”下沉，从而 达到记录按关键字非递减顺序有序排列的目标。 假设在排序过程中，记录序列R1到Rn分为无序序列R1到Ri和有序序列Ri+1到Rn两个区域，则本趟起泡排序的基本操作是：从第1个记录起，比较第1个记录和第2个记录的关键字，若呈“逆序”关系，则将两个记录交换，然后比较第2个记录和第3个记录的关键字，若呈“逆序”关系，则交换，依次类推，直至比较了Ri-1和Ri之后，该无序序列区中关 键字最大的记录将定位在Ri的位置上。,假设在排序过程中，记录序列R1.n的状态为： 2、举例说明: 初始关键字(491, 38,65,97, 76

11、, 13, 27, 492)进行起泡排序。,原始关键字: (491,38, 65, 97, 76, 13, 27, 492) 第1趟排序后：38 491 65 76 13 27 492 97 第2趟排序后：38 491 65 13 27 492 76 97 第3趟排序后：38 491 13 27 492 65 76 97第4趟排序后：38 13 27 491 492 65 76 97第5趟排序后：13 27 38 491 492 65 76 97第6趟排序后： 13 27 38 491 492 65 76 97 起泡排序结束。注意: （1）起泡排序的结束条件：在某一趟排序过程中没有进行 “交换

12、记录”。 （2）一般情况下，每经过一趟“起泡”,“i减1”,但并不是每趟都如此。,3、算法 void BubbleSort(SqList /一趟排序无序序列中最后一个记录的位置 / while / BubbleSort,38,27,49,15,66,53,72,81,94,27,38,15,49,53,66,15,38,15,27,void BubbleSort(SqList /记下进行交换 4、稳定性：稳定的 5、时间复杂度：O(n2),3.3 先进排序 3.3.1 快速排序（起泡法改进） 1、基本思想：通过一趟排序将待排记录序列分割成相邻的两个区域，其中一个区域中记录的关键字均比另一个区域

13、中记录的关键字小（区域内不见得有序），则可分别对这两个区 域的记录进行再排序，以达到整个序列有序。 2、假设待排序的原始记录序列为（Rs, Rs+1, , Rt-1, Rt）,则一趟快速排序的基本操作是：任选一个记录(通常选记录Rs)，以它的关键字作为“枢轴”，凡序列中关键字小于枢轴的记录均移动至该记录之前；反之，凡序列中关键字大于枢轴的记录均移动至该记录之后。 致使一趟排序之后，假设“枢轴”为Ri,记录的无序序列Rs到Rt将被分割成两部分: Rs到Ri-1和Ri+1到Rt，且使 Rj.key Ri.key Rk.key （ 其中：s j i-1、i+1 k t ),3、一趟快速排序的具体过程

14、： 假设枢轴记录的关键字为pivotkey，附设两个指针low和high,它们的初值分别为s和t。则:（1）将枢轴记录(假设选Rs)赋给临时变量R0（2）检测指针high所指记录，若Rhigh.key=pivotkey,则减小high,否则将Rhigh移至指针low所指位置，同时low+;（3）检测指针low所指记录，若Rlow.key=pivotkey,则增加 low,否则将Rlow移至指针high所指记录位置，同时high- - 重复进行上述两个方向的检测，直至low=high为止。此时low和high所指位置即为枢轴记录的位置，最后再将R0移至Rlow。,4、一趟快速排序算法(算法3.6

15、) int Partition (RedType R, int low, int high) pivotkey = Rlow.key; / 枢轴记录关键字 R0=Rlow； / 将枢轴记录移至数组的闲置分量 while (low=pivotkey) - -high; Rlow+=Rhigh; / 将比枢轴记录小的记录移到低端 while (lowhigh / 返回枢轴所在位置 ,31,暂存枢轴记录R0,12,12,68,68,23,23,45,45,31,31,快速排序的“一次划分过程”如下所示：,31,5、举例说明一趟快速排序的过程(假设49为枢轴记录) 初始关键字: ( 491 38 65

16、 97 76 13 27 492 ) 其一趟快速排序结果: ( 27 38 13) 491 (76 97 65 492 ) 总结：一趟快速排序又称“一次划分”。接着再对一次划分后的枢轴两侧的左右区域继续如法炮制，即整个快速排序的过 程可递归进行。 6、快速排序算法：若待排的原始记录序列中只有一个记录，则显然已有序，不再需要进行排序；否则首先对该无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递 归”进行快速排序。,/对记录序列Rs.t进行快速排序 void QSort (RcdType R , int s, int t ) if (s t) / 长度大于1 pivotloc =

17、Partition(R, s, t); / 对 Rs.t 进行一次划分 QSort(R, s, pivotloc-1); / 对低子序列递归排序 QSort(R, pivotloc+1, t); / 对高子序列递归排序 /第一次调用函数 Qsort 时，待排序记录序列的上、下界分 /别为 1 和 L.length。 / 对顺序表进行快速排序 void QuickSort( SqList 7、稳定性： 不稳定 8、时间复杂度：O(nlogn),3.3.2 归并排序 1. “归并” 的含义:将两个或两个以上的有序表组合为一个新的有序表。 在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻

18、的记录有序子序列归并为一个记录的有序序列。,算法 3.9 void Merge (RcdType SR, RcdType TR, int i, int m, int n) / 将有序的记录序列 SRi.m 和 SRm+1.n / 归并为有序的记录序列 TRi.n for (j=m+1, k=i; i=m /将剩余的SRj.n复制到TR / Merge,2. 归并排序的基本思想:(构造相邻的两个有序表) （1）在待排序的原始记录序列 Rs.t中取一个中间位置m=(s+t)/2，将原始序列分为两个位置相邻的子序列(无序)为 Rs.m和Rm+1.t; （2）先分别对子序列Rs.m和Rm+1.t进行归

19、并排序，使 每个子序列变为有序序列； （3）然后调用归并有序表算法实现整个记录序列成为一个 有序序列。,52, 23, 80, 36, 68, 14 (s=1, t=6), 52, 23, 80 36, 68, 14, 52, 23 80, 52, 23, 52, 23, 52, 80,36, 68 14,36,36, 68,14, 36, 68, 14, 23, 36, 52, 68, 80 ,23, 52 23,36 68,80,14,68,void Msort ( RcdType SR, RcdType TR1, int s, int t ) /算法 3.10 / 对SRs.t进行归并排

20、序，排序后的记录存入TR1s.t RcdType TR2t-s+1; /开设用于存放归并排序中间结果的辅助空间 if (s=t) TR1s = SRs; else m = (s+t)/2; / 将SRs.t平分为SRs.m和SRm+1.t Msort (SR, TR2, s, m); / 递归地将SRs.m归并为有序的TR2s.m Msort (SR, TR2, m+1, t); / 递归地将SRm+1.t归并为有序的TR2m+1.t Merge (TR2, TR1, s, m, t); / 将TR2s.m和TR2m+1.t归并到TR1s.t / else / MSort,算法 3.11 vo

21、id MergeSort (SqList 3. 时间复杂度：(nlogn)。即：每一趟归并的时间复杂度为 O(n)，总共需进行 log2n 趟。 4. 稳定性：稳定的,3.3.3 堆排序(heap sort) 1. 堆的定义 堆是满足下列性质的数列r1, r2, r3 rn :,则r1必是数列中最小值或最大值，称作小顶堆或大顶堆。,2. 堆排序规则：建成大顶堆后，将堆顶与最后一个结点交换，即输出最大值。然后将剩余n-1个结点调整成新的大顶堆,再将堆顶与最后一个结点交换，即输出次大值，重复执行 交换、调整，直至剩余一个结点。 进行堆排序的关键： 如何建立初始大顶（小顶）堆 如何将剩余结点调整成大

22、顶（小顶）堆 3. 时间复杂度：(nlogn) 4.稳定性:不稳定 3.4 基数排序 1.复习总结：前面所讲排序方法的实现主要是通过关键字之 间的比较和移动记录这两种操作来完成的。 2.基数排序的引入：基数排序不需要进行关键字间的比较， 而是利用“分配”和“收集”两种操作完成。,3.举例分析排序过程：已知扑克牌中52张牌面的次序关系为 (23A)(2A)(23A)(2 A)。（用分配和收集的方法对扑克牌进行排序） 此时，可以认为每一张牌有两个关键字：花色和面值，且“花色”的地位高于“面值”，即在比较任意两张牌的大小时，必须先比较“花色”，若“花色”相同，则再比较面值。 按上述次序关系排列扑克牌

23、时，有两种方法： 先按花色分成有序的4堆，每一堆的牌均具有相同的花 色，然后分别对每一堆按面值大小整理有序。 先按面值分成13堆，然后将这13堆牌从大到小叠在一起，在重新按不同花色分成4堆，最后将这4堆牌按自小到 大的次序和在一起。,4.基数排序的基本思想：把一个逻辑关键字看成由若干个关键字复合而成。例如: 若关键字是数值，且其值都在0k999范围内，则可把每一个十进制数字看成一个关键字，即可认为k由3个关键字(k2,k1,k0)组成，其中k2是百位数，k1是十位数，k0是个位 数； 若关键字是由5个字母组成的单词，则可将其看成是由5个关键字(k4,k3,k2,k1,k0)组成，其中每个字母k

24、j都是一个关 键字，k0是最低位，k4是最高位。 由于如此分解而得的每个关键字kj都在相同的取值范围内，故可以按分配和收集的方法进行排序。,5.基数排序的过程： 假设记录的逻辑关键字由d个关键字构成，每个关键字可能取r个值，则只要从最低位关键字起，按关键字的不同值将记录“分配”到r个队列中，之后再“收集”在一起，如此重复d趟，最终完成整个记录序列的排序。按这种方法实现的排序称为基数排序，其中“基数”指的是r的取值范围。 6.例：对关键字为 78,09,63,30,74,89,25,05,69,18,83 的记录进行基数排序，则只需进行二趟“分配”和“收集”。 首先按其 “个位数” 取值范围是

25、0, 1, , 9，故将其“分配” 成 10 组用队列来表示（即为分配），之后按从 0 至 9 的顺序将它们 “收集” 在一起；然后按其 “十位数” 取值分别为 0, 1, , 9 ，仍“分配” 成 10 组，之后再按从 0 至 9 的顺序将它们 “收集” 在一起。,(a) 初始状态,0 1 2 3 4 5 6 7 8 9 10 11,0 1 2 3 4 5 6 7 8 9,(b) 第一趟分配之后的结果,0 1 2 3 4 5 6 7 8 9 10 11,0 1 2 3 4 5 6 7 8 9,(c) 第一趟收集之后的结果,(d) 第二趟分配之后的结果,0 1 2 3 4 5 6 7 8 9

26、10 11,(c) 第二趟收集之后的结果,对由顺序表表示存储的记录进行基数排序可利用“计数”和“复制”的操作实现。见下图:,记录数组A,0 1 2 3 4 5 6 7 8 9 10 11,记数数组count(对个位计数结果),0 1 2 3 4 5 6 7 8 9,记录数组B,0 1 2 3 4 5 6 7 8 9 10 11,记数数组count(对十位计数结果),0 1 2 3 4 5 6 7 8 9,累加结果(counti=counti+counti-1),0 1 2 3 4 5 6 7 8 9,累加结果,0 1 2 3 4 5 6 7 8 9,0 1 2 3 4 5 6 7 8 9 10

27、 11,描述基数排序的算法之前，需对记录类型重新定义。 const MAX_NUM_OF_KEY= 6; /关键字项数的最大值 const RADIX=10; /关键字基数，此为十进制整数的基数 const MAXSIZE=10000; const int bitsnum=2; /关键字的位数 typefef struct KeysType keys MAX_NUM_OF_KEY /关键字 infoType otheritem; /其它数据项 RcdType /基数排序中的记录类型,记录数组A,void RadixSort( SqList / 排序后的结果在C中，复制至L.r中 / while

28、 / RadixSort,void RadixPass( RcdType A, RcdType B, int n, int i ) / 对数组A中记录关键字的“第i位”计数，并按计数数组 /count的值将数组A中记录复制到数组B中 for ( j=0; j=0; -k ) / 从右端开始复制记录 j = Ak.keysi; B countj-1 = Ak; countj-; / for / RadixPass,待排关键字序列,1) 对“个位数”进行“计数”,1,0,0,3,0,2,0,0,1,2,2) 计算“累加值”,1,1,1,4,4,6,6,6,7,9,3,3) 从后到前将记录按累加值指

29、示的地址复制到数组 B,83,65,5,69,8,95,4,89,7,73,2,30,0,63,1,78,6,4) 统计“十位数”各个取值的记录数,0,0,1,0,0,3,2,2,1,5) 计算“累加值”,0,0,1,1,1,4,6,8,9,6)从后到前将B中的记录依照“count”指示的地址复制到A,69,3,89,7,78,5,65,2,95,8,83,6,73,4,63,1,30,0,0,0,7. 基数排序的时间复杂度 O(dn) 空间复杂度O(n) 3.5 各种排序方法的综合比较 排序方法的选用一般考虑的原则有：（1）待排序的记录个数n，（2）记录的大小;（3）关键字的分布情况；(4)

30、对排序 稳定性的要求等。 一、时间性能 1. 平均时间性能 时间复杂度为 O(nlogn) ：快速排序、堆排序和归并排序 时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序时间复杂度为 O(dn): 基数排序 2. 当待排记录序列按关键字顺序有序时 直接插入排序和起泡排序能达到O(n)的时间复杂度，快速排序的时间性能蜕化为O(n2) 。,二、空间性能 指的是排序过程中所需的辅助空间大小 1. 所有的简单排序方法(包括：直接插入、起泡和简单选择) 和堆排序的空间复杂度为O(1)； 2. 快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间； 3. 归并排序和基数排序所需辅助空间最多，其空间复杂度为 O(n);,三、排序方法的稳定性能 1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。 2. 当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法，对于不稳定的排序方法，只要能举出一个实例说明即可。 例如 : 对 4, 3, 4, 2 进行快速排序， 得到 2, 3, 4, 4 3. 快速排序、堆排序是不稳定的排序方法,表3.1 各种排序方法性能比较,