数据结构和排序分析

1、10.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按此固有关系将原记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。排序算法的稳定性判断标准：关键字相同的数据对象在排序过程中是否保持前

2、后次序不变。如 2, 2*,1，排序后若为1, 2*, 2 ，则该排序方法是不稳定的。内部排序和外部排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。有序序列区无序序列区使有序区中记录的数目增加一个或几个的操作称为一趟排序。逐步扩大记录有序序列长度的方法大致有下列几类：插入类将无序序列中的一个或几个记录“插入”到有序序列中；交换类通过“交换”无序序

3、列中的记录从而得到其中关键字最小或最大的记录，并将它加到有序子序列中;选择类从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中;归并类通过“归并”两个或两个以上的记录有序序列;其它方法 10.2 插入排序 假设在排序过程中，记录序列R1.n的状态为：有序序列R1.i-1Ri无序序列Ri+1.n则一趟直接插入排序的基本思想：将记录Ri插入到有序子序列R1.i-1中，使记录的有序序列从R1.i-1变为R1.i。完成一趟“插入”需分三步进行：1查找Ri的插入位置j+1；2将Rj+1.i-1中的记录后移一个位置；3将Ri复制到Rj+1的位置上。一、直接插入排序利用顺序查找实现

4、“在R1.i-1中查找Ri的插入位置”的插入排序。直接插入排序算法的三个要点： 1、从Ri-1起向前顺序查找，监视哨设置在R0；R0 = Ri; / 设置“哨兵”for (j=i-1; R0.keyRj.key; -j); / 从后往前找/循环结束后，可得Ri的插入位置j+12在查找过程中找到的关键字大于R0.key的记录需在查找的同时向后移动；for (j=i-1; R0.keyRj.key; -j) Rj+1 = Rj;3i = 2，3，, n, 实现整个序列的排序。算法描述如下: void InsertionSort ( Elem R , int n) / 对记录序列R1.n作直接插入排

5、序。for ( i=2; i=n; +i ) R0 = Ri; / 复制为监视哨for ( j=i-1; R0.key Rj.key; -j )Rj+1 = Rj; / 记录后移Rj+1 = R0; / 插入到正确位置 / InsertSort排序的时间分析： 实现排序的基本操作有两个：（1）“比较”序列中两个关键字的大小；（2）“移动”记录。对于直接插入排序：最好的情况(关键字在记录序列中顺序有序)：“比较”的次数：1*(n-1)=n-1“移动”的次数：0最坏的情况(关键字在记录序列中逆序有序)：“比较”的次数 “移动”的次数直接插入排序所需进行关键字间的比较次数和记录移动的次数均为n2/4

6、，所以直接插入排序的时间复杂度为O(n2)。直接插入排序是一种稳定的排序方法。原因：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。二、折半插入排序由于R1.i-1是一个按关键字有序的有序序列，则可利用折半查找实现“在R1.i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。void BInsertionSort (Elem R ， int n) / 对记录序列R1.n作折半插入排序。for ( i=2; i=L.length; +i ) R0 = Ri; / 将Ri暂存到R0l

7、ow = 1; high = i-1;while (low=high)/在Rlow.high中折半查找插入的位置m = (low+high)/2; / 折半if (R0.key =high+1; -j )Rj+1 = Rj; / 记录后移Rhigh+1 = R0; / 插入 / BInsertSort三、表插入排序 为了减少在排序过程中进行的“移动”记录的操作，改变记录的存储结构，利用静态链表进行排序，并在排序完成后，一次性地调整各个记录相互之间的位置，从而实现排序。例如：下标012345678关键字MAXINT4938659776132749*初值10-i=2201-i=32310-i=42

8、3140-i=5231504-i=66315042-i=763150472-终值681504723void LInsertionSort (Elem SL ， int n)/ 对记录序列SL1.n作表插入排序。SL0.key = MAXINT ;SL0.next = 1; SL1.next = 0;for ( i=2; i头结点，k - a1 while(SLk.key7MAXINT4938659776132749*68150472327a3-2MAXINT1338659776492749*6(6)15048233(2),7a4-1MAXINT1327659776493849*6(6)(7)5

9、048134(1),6a5-8MAXINT1327389776496549*6(6)(7)(7)0485358a6-3MAXINT1327384976976549*6(6)(7)(7)(6)40536(3),7a7-5MAXINT1327384949*9765766(6)(7)(7)(6)(8)0547(5),8a8-4MAXINT13273849526597766(6)(7)(7)(6)(8)(7)04(4),(7),8MAXINT13273849526576976(6)(7)(7)(6)(8)(7)(8)0void Arrange ( Elem SL , int n ) p = SL0.n

10、ext; /p=6for ( i=1; in; +i ) while (pi) p = SLp.next;q = SLp.next; if ( p!= i ) SLpSLi; SLi.next = p; p = q; / Arrange根据静态链表SL中各结点的指针值调整记录位置，使得SL中记录按关键字非递减有序顺序排列算法中使用了三个指针:p指示第i个记录的当前位置；i指示第i个记录应在的位置；q指示第i+1个记录的当前位置 p指示第一个记录的当前位置 SL1.i-1中记录已按关键字有序排列，第i个记录在SL中的当前位置应不小于i找到第i个记录，并用p指示其在SL中当前位置 q指示尚未调整的

11、表尾交换记录，使第i个记录到位 指向被移走的记录， 使得以后可由while循环找回 p指示尚未调整的表尾，为找第i+1个记录作准备四、希尔排序（又称缩小增量排序）1959年由D.L. Shell提出。基本思想对待排记录序列先作“宏观”调整，再作“微观”调整。“宏观”调整“跳跃式”的插入排序。将记录序列分成若干个由不相邻的记录构成的子序列，每个子序列分别进行插入排序。假设将n个记录分成d个子序列，则这d个子序列分别为： R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 其中，d称为增量，它的值在排序过程中从大到小逐渐缩小

12、（如：d=d/2），直至最后一趟排序减为1。例如：void ShellInsert(SqList &L,int dk)/对顺序表L做一趟希尔插入排序。本算法是和一趟直接插入排序相比，作了以下修改：1. 前后记录的增量是dk，而不是1; 2. 0号单元只是暂存单元，不是哨兵。当j=0时，插入位置已找到 int i,j; for(i=dk+1; i L.elemi)/需将L.elemi插入有序子表 L.elem0=L.elemi; /暂存在0号单元 for(j=i-dk; j0 & L.elem0L.elemwordj; j -= dk) L.elemj+dk=L.elemj; /记录后移，查找插

13、入位置 L.elemj+dk=L.elem0; /插入到正确的位置 void ShellSort(SqList &L,int dlta,int t)/按增量序列dlta0.t-1对顺序表L作希尔排序for(int k=0;k1&change;-i) change=False; for(j=0;jL. keyj+1) L. keyj L. keyj+1 change=True; 算法分析最好情况：初始时关键字递增有序，每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。在while循环之前和之中，至少要移动记录两次，所以总的比较次数为2(n-1)。最坏情况：初始时关键字递减有序，此时

14、记录比较和移动次数分别为：直接插入排序是一种稳定的排序方法。原因：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。快速排序比较次数较少、内部排序中速度较快的方法。基本过程取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。4938659776132749 38659776132749273865977613 492738 97761365492738139776 6549273813 76976549273813 49 76 97 654949

15、temp快速排序示例快速排序算法int PARTITION(rectype R,int l,int h) int i=l; j=h; rectype temp=Ri; do while (Rj.key = temp.key)&(ij) j-; if (ij) Ri+=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); QUICKS

16、ORT(R,s1,i-1); QUICKSORT(R,i+1,t1); 最好情况每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等。快速排序的时间复杂度考虑关键字的比较次数和对象移动次数最坏情况每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准的左边(或右边)为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为 设C(n)表示对长度为n的序列进行快速排序所需的比较次数，显然，它应该等于对长度为n的无序区进行划分所需的比较次数n-1，加上递归地对划分所得的左右两个无序子

17、区进行快速排序所需的比较次数。假设文件长度n=2k ，k=log2n，因此有： 快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。 可证:快速排序的平均时间复杂度也是O(nlog2n)。 快速排序是不稳定的排序方法。四、选择排序基本原理将待排序的结点分为已排序(初始为空)和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。两种常见的选择排序直接选择排序堆排序直接选择排序的基本过程在一组对象Vi到Vn-1中选择具有最小关键字的对象若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。删除具有最小关键

18、字的对象，在剩下的对象中重复第(1)、(2)步，直到剩余对象只有一个为止。49386597761327491338659776492749132765977649384913273897764965491327384976976549132738494997657613273849496597761327384949657697直接选择排序示例直接选择排序算法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)的结点都是叶子，因此，以

19、这些结点为根的子树都已是堆。即只需依次将序号为low(n/2)，low(n/2)-1，.，1的结点作为根的子树都调整为堆即可。以大根堆为例进行说明“筛选法”基本思想：因为Ri的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以在Ri和它的左右孩子中选取关键字最大的结点放到Ri的位置上。若Ri的关键字已是三者中的最大者，则无须做任何调整，以Ri为根的子树已构成堆，否则，将Ri和具有最大关键字的左孩子R2i或右孩子R2i+1进行交换。假定R2i的关键字最大，将Ri和R2i交换位置，交换之后有可能导致R2i为根的子树不再是堆，但由于R2i的左右子树仍然是堆，于是可以重复上述过程，将

20、以R2i为根的子树调整为堆，.，如此逐层递推下去，最多可能调整到树叶。例子：关键字序列为 42，13，91，23， 24， 16，05，88，n=8，故从第四个结点开始调整4213912324160588421391232416058842139188241605234213918824160523不调整421391882416052342139188241605234288912324160513428891232416051391884223241605139188422324160513建成的堆筛选算法SIFT(rectype R,int i;int m) int j; rectype

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

22、188422324160513（a）初始堆R1到R813884223241605911388422324160591（b）第一趟排序之后（c）重建的堆R1到R78824422313160591882442231316059105244223131688910524422313168891（d）第二趟排序之后（e）重建的堆R1到R642241623130588914224162313058891（f）第三趟排序之后05241623134288910524162313428891（g）重建的堆R1到R524231605134288912423160513428891（h）第四趟排序之后132316

23、05244288911323160524428891（i）重建的堆R1到R423131605244288912313160524428891（j）第五趟排序之后05131623244288910513162324428891（k）重建的堆R1到R316130523244288911613052324428891（l）第六趟排序之后05131623244288910513162324428891（m）重建的堆R1到R213051623244288911305162324428891（n）第七趟排序之后05131623244288910513162324428891堆排序算法HEAPSORT(re

24、ctype 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=Ri; Ri=temp; SIFT(R,1,i-1); 堆排序的时间复杂度堆排序的时间复杂性为O(n log2n) 空间复杂性为 O(1)堆排序是不稳定的排序方法。五、归并排序通过对两个有序结点序列的合并来实现排序。归并：将若干个已排好序的部分合并成一个有序的部分。归并的基本思想将待排序列R0到Rn-1看成n个长度为1的有序子序列，把这些子序列两两归并，便得到high(n/2)个有序的子序列。然后再把这high(n

25、/2)个有序的子序列两两归并，如此反复，直到最后得到一个长度为n的有序序列。该归并操作，都是将两个子序列归并为一个子序列，称“二路归并”，类似地还有“三路归并”或“多路归并”。归并过程示例(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,

26、i+length-1,i+2*length-1); i=i+2*length; if (i+length-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) int length=1; while (lengt