天津科技大学数据结构排序

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, ，Kn 这些关键字相互间可以进行比较，即它们之间存在一个关系这些关键字相互间可以进行比较，即它们之间存在一个关系Kp1Kp2Kpn按此固有关系将原记录序列重新排列为按此固

2、有关系将原记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作的操作称作。“比较”的次数：1*(n-1)=n-1“移动”的次数：0“比较”的次数 “移动”的次数直接插入排序所需进行关键字间的比较次数和记录移动的次数均为n2/4，所以直接插入排序的时间复杂度为O(n2)。由于R1.i-1是一个按关键字有序的有序序列，则可，如此实现的插入排序为折半插入排序。 ，改变记录的存储结构，利用改变记录的存储结构，利用进行排序，并在排序进行排序，并在排序完成后，一次性地调整各个记录相互之间的位置，从而实完成后，一次性地调整各个记录相互之间的位置，从而实现排序。现排序。例如：例如：下标下标012345

3、678关键字关键字MAXINT49 38 65 97 76 13 27 49*初值初值10-i=2201-i=32310-i=423140-i=5231504-i=66315042-i=763150472-终值终值681504723ipq01234567816a2-7MAXINT49386597762749*6815042327a3-2MAXINT386597764949*61504833(2),7a4-1MAXINT6597764949*6504834(1),6a5-8MAXINT97766549*6045358a6-3MAXINT7697656405例如：void ShellInsert(

4、SqList &L,int dk)/对顺序表对顺序表L做一趟希尔插入排序。本算法是和一趟直接插入排序相比，作了以下修改：做一趟希尔插入排序。本算法是和一趟直接插入排序相比，作了以下修改：1. 前前后记录的增量是后记录的增量是dk，而不是，而不是1; 2. 0号单元只是暂存单元，不是哨兵。当号单元只是暂存单元，不是哨兵。当j=0时，插入位置已时，插入位置已找到找到 int i,j; for(i=dk+1; i L.elemi) L.elem0=L.elemi; for(j=i-dk; j0 & L.elem0= temp.key)&(ij) j-; if (ij) Ri+

5、=Rj; while (Ri.key=temp.key)&(ij) i+; if (ij) Rj-=Ri; while (i!=j); Ri=temp; return i; QUICKSORT(rectype R,int s1,int t1) int i; if (s1t1) i=PARTITION(R,s1,t1); QUICKSORT(R,s1,i-1); QUICKSORT(R,i+1,t1); 设设C(n)表示对长度为表示对长度为n的序列进行快速排序所需的比较次的序列进行快速排序所需的比较次数，显然，它应该等于对长度为数，显然，它应该等于对长度为n的无序区进行划分所需的比的无序

6、区进行划分所需的比较次数较次数n-1，加上递归地对划分所得的左右两个无序子区进行，加上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度快速排序所需的比较次数。假设文件长度n=2k ，k=log2n，因此有：因此有：基本原理将待排序的结点分为已排序基本原理将待排序的结点分为已排序(初始为空初始为空)和为未排序和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。两组，依次将未排序的结点中值最小的结点插入已排序的组中。493865977613274913386597764927491327659776493849132738977649654913273849

7、76976549132738494997657613273849496597761327384949657697直接选择排序算法直接选择排序算法SELECTSORT(rectype R) int i,j,k; rectype temp; for (i=0;in-1;i+) k=i; for (j=i+1;jn;j+) if (Rj.key low(n/2)的结点都是叶子，因此，以这些结点为根的子树的结点都是叶子，因此，以这些结点为根的子树都已是堆。都已是堆。即只需依次将序号为即只需依次将序号为low(n/2)，low(n/2)-1，.，1的结点作的结点作为根的子树都调整为堆即可。为根的子树都调

8、整为堆即可。以以为例进行说明为例进行说明因为因为Ri的左右子树已是堆，这两棵的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以在子树的根分别是各自子树中关键字最大的结点，所以在Ri和它的左右孩子中选取关键字最大的结点放到和它的左右孩子中选取关键字最大的结点放到Ri的位置上。的位置上。若若Ri的关键字已是三者中的最大者，则无须做任何的关键字已是三者中的最大者，则无须做任何调整，以调整，以Ri为根的子树已构成堆，为根的子树已构成堆，否则，将否则，将Ri和具有最大关键字的左孩子和具有最大关键字的左孩子R2i或右或右孩子孩子R2i+1进行交换。进行交换。假定假定R2i的关键字最大，

9、将的关键字最大，将Ri和和R2i交换位置，交换位置，交换之后有可能导致交换之后有可能导致R2i为根的子树不再是堆，但由于为根的子树不再是堆，但由于R2i的左右子树仍然是堆，于是可以重复上述过程，将的左右子树仍然是堆，于是可以重复上述过程，将以以R2i为根的子树调整为堆，为根的子树调整为堆，.，如此逐层递推下去，如此逐层递推下去，最多可能调整到树叶。最多可能调整到树叶。例子：关键字序列为例子：关键字序列为 42，13，91，23， 24， 16，05，88，n=8，故从第四个结点开始调整，故从第四个结点开始调整4242131391912323242416160505888842139123241

10、60588424213139191888824241616050523234213918824160523不调整不调整424213139191888824241616050523234213918824160523424288889191232324241616050513134288912324160513919188884242232324241616050513139188422324160513建成的堆建成的堆筛选算法筛选算法SIFT(rectype R,int i;int m) int j; rectype temp; temp=Ri; j=2*i; while (j=m) if (

11、jm)&(Rj.keyRj+1.key) j+; if (temp.key=1; i-) SIFT(R, i, n)由于建堆的结果把关键字最大的记录选到了堆顶的位由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该将置，而排序的结果应是升序，所以，应该将R1和和Rn交交换，这就得到了第一趟排序的结果。换，这就得到了第一趟排序的结果。 第二趟排序的操作首先是将无序区第二趟排序的操作首先是将无序区R1到到Rn-1调整为调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用可以调用SIFT函数将函数

12、将R1到到Rn-1调整为大根堆，选出最调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录记录Rn-1交换，如此反复进行下去。交换，如此反复进行下去。919188884242232324241616050513139188422324160513（a a）初始堆）初始堆R1R1到到R8R8131388884242232324241616050591911388422324160591（b b）第一趟排序之后）第一趟排序之后（c c）重建的堆）重建的堆R1R1到到R7R7888824244242232313131616050

13、591918824422313160591050524244242232313131616888891910524422313168891（d d）第二趟排序之后）第二趟排序之后（e e）重建的堆）重建的堆R1R1到到R6R6424224241616232313130505888891914224162313058891（f f）第三趟排序之后）第三趟排序之后050524241616232313134242888891910524162313428891（g g）重建的堆）重建的堆R1R1到到R5R524242323161605051313424288889191242316051342889

14、1（h h）第四趟排序之后）第四趟排序之后131323231616050524244242888891911323160524428891（i i）重建的堆）重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891（j j）第五趟排序之后）第五趟排序之后050513131616232324244242888891910513162324428891（k k）重建的堆）重建的堆R1R1到到R3R3161613130505232324244242888891911613052324428891（l l）第六趟排序之后）第六趟排序之

15、后050513131616232324244242888891910513162324428891（m m）重建的堆）重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891（n n）第七趟排序之后）第七趟排序之后050513131616232324244242888891910513162324428891堆排序算法堆排序算法HEAPSORT(rectype R) int i; rectype temp; for (i=n/2;i=1;i-) SIFT(R,i,n); for (i=n;i=1;i-) temp=R1; R1

16、=Ri; Ri=temp; SIFT(R,1,i-1); 归并过程示例归并过程示例(25) (57) (48) (37) (12) (92) (86)(25 57) (37 48) (12 92) (86)(25 37 48 57) (12 86 92)(12 25 37 48 57 86 92)一趟归并算法一趟归并算法MERGEPASS(rectype R,rectype R1,int length) int i,j; i=0; while (i+2*length-1n) MERGE(R,R1,i,i+length-1,i+2*length-1); i=i+2*length; if (i+l

17、ength-1n-1) MERGE(R,R1,i,i+length-1,n-1); else for (j=i;jn;j+) R1j=Rj;归并算法归并算法MERGE(rectypr R,rectype R1,int low,int mid,int high) int i,j,k; i=low; j=mid+1; k=low; while (i=mid)&(j=high) if (Ri.key=Rj.key) R1k+=Ri+; else R1k+=Rj+; while (i=mid) R1k+=Ri+; while (j=high) R1k+=Rj+;归并排序算法归并排序算法MERGESORT(rectype R