数据结构与算法-东北林业大学 数据结构演示文稿10[1].ppt

1、第十章 内部排序,概述 插入排序 快速排序 选择排序 归并排序 基数排序,概 述,排序：假定 n 个序列为 R1 ，R2 ， ，Rn 其相应的关键字序列为 K1 ，K2 ， ，Kn 需确定 1,2, ,n 的一种排列 p1,p2, ,pn, 使其相应的关键字满足如下的非递减（或非递增）关系 Kp1 Kp2 Kpn 即使记录成为一个按关键字有序的序列 Rp1 Rp2 Rpn ,记录的关键字可以是主关键字，也可以是次关键字，甚至可以是多个数据项的组合。 当记录的关键字不是主关键字时，排序的结果不唯一。 对于关键字相等的记录，如果排序前后的相对顺序没有改变，则称使用的排序方法是稳定的；反之，若可能存

2、在关键字相等的记录在排序前后的相对顺序发生了改变，则称使用的排序方法是不稳定的。 若将序列中的所有记录同时放在内存中完成排序过程，则称内部排序；若在排序过程中存在记录存放在外存，则称外部排序。,待排序记录的三种存储方式： 1. 记录按序列存储在一组连续的存储单元； 2. 记录按序列存储在静态链表中； 3. 用一个向量记录各记录的存储位置。 排序过程所需进行的两种基本操作： 1. 比较两个关键字的大小； 2. 移动记录位置或改变地址指针。 约定待排记录的数据类型(其中n为记录数目)： TYPE rcdtype=RECORD key:integer; otheritem:anytype END;

3、listtype=ARRAY0.n OF rcdtype;,数据结构,主讲：王阿川,插 入 排 序,直接插入排序 将一个记录插入到已排好序的有序表中, 从而得到一个新的、记录数增 1 的有序表。 设待排序列的关键字序列为: 49, 38, 65, 97, 76, 13, 27, 假定在排序过程中前面4个记录已按关键字得到了一个序列： R(38)，R(49)，R(65)，R(97) 则在此序列中插入第5个记录后的新序列如下： R(38)，R(49)，R(65)， R(76)， R(97) * 直接插入排序需多趟才能完成。,一趟直接插入排序算法（教材第266页）： 已知r1.i-1中的记录按关键字

4、非递减有序,本算法插入ri，使r1.i按关键字非递减有序。,PROC straipass(VAR r:listtype; i:integer); r0 := ri ; j := search(r,i); ( ri, . ,rj+2 ) := ( ri-1, . ,rj+1 ); rj+1 := r0 ENDP; straipass,* search(r,i)定义为在r1.i-1中进行搜索,找到位置j使rj.keyri.keyrj+1.key,其中(0ji) * 此算法包含了两个循环,一趟直接插入排序算法的改进(教材第266页):,PROC straipass1(VAR r:listtype;

5、i:integer); r0 := ri; j:=i-1; x:=ri.key; WHILE xrj.key DO rj+1:=rj; j:=j-1; rj+1 := r0 ENDP; straipass1,直接插入排序完整算法(教材第267页): 从第2个记录起逐个进行一趟直接插入排序可得完整的直接插入排序算法。,PROC straisort(VAR r:listtype); ROR i:=2 TO n DO straipass1(r,i) ENDP; straisort,直接插入排序示例,折半插入排序 采用折半查找方法确定元素的插入位置,以减少关键字的比较次数。 一趟折半插入算法如下（教材

6、第268页）：,PROC binpass(VAR r:listtype; i:integer); r0 := ri ; x := ri.key; s:=1; j:=i-1; WHILE s j DO m := (s+j)/2 ; IF xrm.key THEN j:=m-1 ELSE s:=m+1 ; FOR k:=i-1 DOWNTO j+1 DO rk+1:=rk; rj+1 := r0 ENDP; binpass,折半插入排序的完整算法(教材第268页): 从第2个记录起逐个进行一趟折半插入排序可得完整的折半插入排序算法。,PROC binsort(VAR r:listtype); RO

7、R i:=2 TO n DO binpass(r,i) ENDP; binsort,2-路插入排序 另设与r同类型数组d, 令d1:=r1, 并将d1看成已排好序的序列中处于中间位置的记录, 然后将 r 中第2个起的记录依次插入到 d1 之前或之后的有序序列中。实现算法时, 将 d 视作循环向量并分别设头尾针first和final，用来指示排序过程中得到的有序序列的位置。,设初始关键字为：49, 38, 65, 97, 76, 13, 27, 49 排序过程中 d 的状态如下：,（ : first : final ）,数据结构,主讲：王阿川,快 速 排 序,起泡排序（冒泡排序） 一趟起泡排序方

8、法：从第一个记录开始, 依次比较相邻两个记录的关键字, 若它们逆序，则将记录位置交换，直到比较处理最后两个记录。,初始状态：49, 38, 65, 97, 76, 13, 27, 49 第1次比较结果：38, 49, 65, 97, 76, 13, 27, 49 第2次比较结果：38, 49, 65, 97, 76, 13, 27, 49 第3次比较结果：38, 49, 65, 97, 76, 13, 27, 49 第4次比较结果：38, 49, 65, 76, 97, 13, 27, 49 第5次比较结果：38, 49, 65, 76, 13, 97, 27, 49 第6次比较结果：38,

9、49, 65, 76, 13, 27, 97, 49 第7次比较结果：38, 49, 65, 76, 13, 27, 49, 97,完整起泡排序方法：依次对r1.n中的前面n个记录、前面 n-1个记录、前面2个记录实施一趟起泡排序，即可得到有序的r1.n。若在某趟起泡排序中没有交换过记录, 则可提前结束整个起泡排序。,初始状态：49, 38, 65, 97, 76, 13, 27, 49 第1趟结果： 38, 49, 65, 76, 13, 27, 49, 97 第2趟结果： 38, 49, 65, 13, 27, 49, 76, 97 第3趟结果： 38, 49, 13, 27, 49, 6

10、5, 76, 97 第4趟结果： 38, 13, 27, 49, 49, 65, 76, 97 第5趟结果： 13, 27, 38, 49, 49, 65, 76, 97 第6趟结果： 13, 27, 38, 49, 49, 65, 76, 97,快速排序 通过一趟排序将待排记录整理成分段有序，然后对每段递归实施同样的算法，直到整个序列有序。 一趟快速排序的一般过程是，假定待排序列为rs,rs+1,rt, 首先任取一个记录 ( 通常取rs或rt)作为支点, 然后重新排列其余记录，将所有关键字比它小的记录安置在它的位置之前, 而将其余的记录安置在它的位置之后。由此可得该支点记录所在位置作分界线，

11、将序列分割成两个子序列。,一趟快速排序的具体做法： 设两个指针i, j, 其初值分别为s和t,设支点记录 rp=rs,x=rp.key, 则首先 j 从所指位置向前搜索第一个关键字小于 x 的记录并将其存储到i的位置，然后i从所指的位置向后搜索第一个关键字大于 x 的记录并将其存储到 j的位置，重复这两步直到 i=j ,最后将rp存储到 i 的位置。,49, 38, 65, 97, 76, 13, 27, 49,rp=rs x= 49,rs,rt,i , j,49 38 65 97 76 13 27 49,初始状态：,rp=rs x= 49,49 38 65 97 76 13 27 49,i,

12、j,27 38 65 97 76 13 27 49,i,j,27 38 65 97 76 13 65 49,i,j,27 38 13 97 76 13 65 49,i,j,27 38 13 97 76 97 65 49,i,j,27 38 13 49 76 97 65 49,i,j,一趟快速排序示意图,一趟快速排序算法：设rs.t为待排记录序列，i为支点记录最终位置(算法10.10(b)。,PROC qkpass(VAR r:listtype;s,t:integer; VAR i:integer); i:=s; j:=t; rp:=rs; x:=rs.key; WHILE ij DO WHIL

13、E ij AND (rj.keyx) DO j:=j-1; ri := rj; i:=i+1; WHILE ij AND (ri.keyx) DO i:=i+1; rj := ri; j:=j-1 ; ri := rp ENDP; qkpass,完整的快速排序算法：借用一趟快速排序算法，采用递归形式可得完整的快速排序算法如下（教材第277页）：,PROC qksort(VAR r:listtype;s,t:integer); IF s t THEN qkpass(r, s, t, k); qksort(r,s,k-1); qksort(r,k+1,t) ; ENDP; qksort,数据结构,

14、主讲：王阿川,选 择 排 序,一趟选择排序的基本思路是将序列中关键字最小的一个记录排放到序列的第一个位置。 简单选择排序 一趟简单选择排序的操作过程是: 对于给定的包含n-i+1个记录的序列 ri.n, 通过n-i次关键字比较, 找出其中关键字最小的记录, 并将此记录与序列中的第一个记录ri交换。,对ri.n进行一趟简单选择排序算法：,PROC smp_selecpass(VAR r:listtype; i:integer); k:=i; FOR j:=i+1 TO n DO IF rj.key rk.key THEN k:=j; IF ki THEN ri rk ENDP; smp_sele

15、cpass,对r1.n进行简单选择排序算法：,PROC smp_selecsort(VAR r:listtype); FOR i:=1 TO n-1 DO smp_selecpass(r,i) ENDP; smp_selecsort,树形选择排序,树形选择排序（锦标赛排序）的基本思路是: 在通过比较找出序列中关键字最小的记录,完成一趟选择排序后，在对其余记录实施下一趟选择排序时，充分利用前一趟选择排序时的比较结果，以减少比较次数。,38,49,97,65,13,76,49,27,38,65,13,27,38,13,13,38,49,97,65,76,49,27,38,65,76,27,38,2

16、7,27,第1趟比较输出13,输出13后第2趟比较,38,49,97,65,76,49,27,38,65,76,27,38,27,27,输出27,38,49,97,65,76,49,38,65,76,49,38,49,38,输出27后第3趟比较,堆排序,对于n个元素的序列k1,k2,kn，若将此序列对应的一维数组看成是一个完全二叉树的顺序存储结构，则这个完全二叉树中所有非终端结点的值均不大于（或不小于）其孩子结点的值。满足此条件的序列称为堆。 显然，堆中的元素满足：,ki k2i ki k2i+1,ki k2i ki k2i+1,或,11,38,09,83,27,96,47,85,53,30,

17、36,24,12,91,两个堆的示例：,序列: 96,83,27,38,11,09 数组:,序列: 12,36,24,85,47,30,53,91 数组:,堆排序的方法：,堆顶元素（序列中的第一个元素）即为序列中的最小元素 (或最大元素)。先输出堆顶元素，然后将剩余的元素重新调整为堆，如此重复直到输出序列中的所有元素，则可得到序列的一个有序排列。,输出堆顶元素后堆的调整方法：,输出堆顶元素后，以堆中最后一个元素取代堆顶的位置，然后从堆顶开始从上至下，按堆的定义用交换元素位置的方法进行调整。,76,49,49,65,38,27,13,97,堆的调整示例：,76,49,49,65,38,27,97

18、,13,76,49,49,65,38,97,27,76,49,97,65,38,49,27,13,13,76,49,97,65,38,49,27,76,49,97,65,38,49,27,76,49,65,97,49,38,76,97,65,49,49,38,13,13,13,27,27,13,堆的创建方法：,将序列k1,k2,kn看成一个完全二叉树，则这个完全二叉树的最后一个非终端结点是第n/2个元素。按堆的调整方法从后到前逐个调整这 n/2 个非终端结点，则可得到由这 n 个元素所创建的堆。,76,97,27,13,38,65,49,49,堆的创建过程示例： 设序列为: 49, 38, 6

19、5, 97, 76, 13, 27, 49 ,76,97,27,13,38,65,49,49,76,97,27,65,38,13,49,49,76,97,27,65,38,13,49,49,76,97,27,65,38,13,49,49,76,97,27,65,38,13,49,49,76,97,27,65,38,13,49,49,数据结构,主讲：王阿川,归 并 排 序,将两个或两个以上的有序表合并成一个新的有序表称为归并。如果一趟将k个有序表合并成一个有序表，则称 k-路归并。 2-路归并排序的一般方法是，先将待排的n个记录看成n个有序子序列(每个序列长度为1)，然后两两归并，得到 n/2 个长度为 2 或 1 的有序子序列；再两两归并, , 直至得到一个长度为 n 的有序序列。,归并排序示例： 设待排序列为: 49, 38, 65, 97, 76, 13, 27 ,数据结构,主讲：王阿川,基 数 排 序,一种借助于多关键字排序思想对单逻辑关键字进行排序的方法。 多关键字排序 设有n个记录序列R1,R2,Rn, 且每个记录Ri中含有d个关键字(Ki1, Ki2, , Kid),则序列对多关键字