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

第十章 排序 概述 插入排序 交换排序 选择排序 归并排序 分配排序 外排序 排序是计算机中经常遇到的操作。,第十章 排 序 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*,1，排序后若为1, 2*, 2 ，则该排序方法是不稳定的。,内部排序和外部排序 若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序； 若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。 内部排序的方法 内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。,使有序区中记录的数目增加一个或几个的操作称为一趟排序。,逐步扩大记录有序序列长度的方法大致有下列几类： 插入类 将无序序列中的一个或几个记录“插入”到有序序列中； 交换类 通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加到有序子序列中; 选择类 从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中; 归并类 通过“归并”两个或两个以上的记录有序序列; 其它方法,10.2 插入排序 假设在排序过程中，记录序列R1n的状态为：,则一趟直接插入排序的基本思想： 将记录Ri插入到有序子序列R1i-1中，使记录的有序序列从R1i-1变为R1i。 完成一趟“插入”需分三步进行： 1查找Ri的插入位置j+1； 2将Rj+1i-1中的记录后移一个位置； 3将Ri复制到Rj+1的位置上。,一、直接插入排序 利用顺序查找实现“在R1i-1中查找Ri的插入位置”的插入排序。 直接插入排序算法的三个要点： 1、从Ri-1起向前顺序查找，监视哨设置在R0； R0 = Ri; / 设置“哨兵” for (j=i-1; R0.keyRj.key; -j); / 从后往前找 /循环结束后，可得Ri的插入位置j+1 2在查找过程中找到的关键字大于R0.key的记录需在查找的同时向后移动； for (j=i-1; R0.keyRj.key; -j) Rj+1 = Rj; 3i = 2，3，, n, 实现整个序列的排序。,算法描述如下: void InsertionSort ( Elem R , int n) / 对记录序列R1n作直接插入排序。 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，所以直接插入排序的时间复杂度为O(n2)。,直接插入排序是一种稳定的排序方法。 原因：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。 二、折半插入排序 由于R1i-1是一个按关键字有序的有序序列，则可利用折半查找实现“在R1i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。 折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。,void BInsertionSort (Elem R ， int n) / 对记录序列R1n作折半插入排序。 for ( i=2; i=high+1; -j ) Rj+1 = Rj; / 记录后移 Rhigh+1 = R0; / 插入 / BInsertSort,三、表插入排序 为了减少在排序过程中进行的“移动”记录的操作，改变记录的存储结构，利用静态链表进行排序，并在排序完成后，一次性地调整各个记录相互之间的位置，从而实现排序。 例如：,void LInsertionSort (Elem SL ， int n) / 对记录序列SL1n作表插入排序。 SL0.key = MAXINT ; SL0.next = 1; SL1.next = 0; for ( i=2; i头结点，k - a1 while(SLk.key=SLi.key) j=k, k=SLk.next ; SLj.next = i; SLi.next = k; / LinsertionSort,void Arrange ( Elem SL , int n ) p = SL0.next; /p=6 for ( 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指示第一个记录的当前位置 SL1i-1中记录已按关键字有序排列，第i个记录在SL中的当前位置应不小于i 找到第i个记录，并用p指示其在SL中当前位置 q指示尚未调整的表尾 交换记录，使第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称为增量，它的值在排序过程中从大到小逐渐缩小（如：d=d/2），直至最后一趟排序减为1。,例如：,void ShellInsert(SqList /插入到正确的位置 ,void ShellSort(SqList /一趟增量为dltak的插入排序 ,10.3 快速排序 它属交换排序，起泡排序是最简单的一种交换排序。 起泡排序 假设在排序过程中，记录序列R1n的状态为：,则第i趟起泡插入排序的基本思想 借助对无序序列中的记录进行“交换”的操作，将无序序列中关键字最大的记录“交换”到Rn-i+1的位置上。,void BubbleSort(SqList ,算法分析 最好情况：初始时关键字递增有序，每一趟排序中仅需进行一次关键字的比较，所以总的比较次数为n-1。在while循环之前和之中，至少要移动记录两次，所以总的比较次数为2(n-1)。 最坏情况：初始时关键字递减有序，此时记录比较和移动次数分别为：,直接插入排序是一种稳定的排序方法。 原因：关键字相同的两个对象，在整个排序过程中，不会通过比较而相互交换。,快速排序 比较次数较少、内部排序中速度较快的方法。 基本过程 取待排序的结点序列中某个结点的值作为控制值，采用某种方法把这个结点放到适当的位置，使得这个位置的左边的所有结点的值都小于等于这个控制值，而这个位置的右边的所有结点的值都大于等于这个控制值。,49,38,65,97,76,13,27,49,38,65,97,76,13,27,49,27,38,65,97,76,13,49,27,38,97,76,13,65,49,27,38,13,97,76,65,49,27,38,13,76,97,65,49,27,38,13,49,76,97,65,49,49,temp,快速排序示例,快速排序算法 int PARTITION(rectype R,int l,int h) int i=l; j=h; rectype temp=Ri; do while (Rj.key = temp.key) ,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); ,最好情况 每次所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左右两个无序子区的长度大致相等。,快速排序的时间复杂度 考虑关键字的比较次数和对象移动次数 最坏情况 每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准的左边(或右边)为空，划分前后无序区的元素个数减少一个，因此，排序必须做n-1趟，每一趟中需做n-i次比较，所以最大比较次数为,设C(n)表示对长度为n的序列进行快速排序所需的比较次数，显然，它应该等于对长度为n的无序区进行划分所需的比较次数n-1，加上递归地对划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度n=2k ，k=log2n，因此有：,快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为O(nlog2n)。 可证:快速排序的平均时间复杂度也是O(nlog2n)。 快速排序是不稳定的排序方法。,四、选择排序 基本原理 将待排序的结点分为已排序(初始为空)和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。 两种常见的选择排序 直接选择排序 堆排序,直接选择排序的基本过程 在一组对象Vi到Vn-1中选择具有最小关键字的对象若它不是这组对象中的第一个对象，则将它与这组对象中的第一个对象对调。删除具有最小关键字的对象，在剩下的对象中重复第(1)、(2)步，直到剩余对象只有一个为止。,49,38,65,97,76,13,27,49,13,38,65,97,76,49,27,49,13,27,65,97,76,49,38,49,13,27,38,97,76,49,65,49,13,27,38,49,76,97,65,49,13,27,38,49,49,97,65,76,13,27,38,49,49,65,97,76,13,27,38,49,49,65,76,97,直 接 选择 排序 示 例,直接选择排序算法 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.keyRk.key) k=j; if (k!=i) temp=Ri; Ri=Rk; Rk=temp; ,2. 当文件为正序时，移动次数为0，文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)。 直接选择排序是不稳定的排序方法。,直接选择排序的时间复杂度 1、无论初始状态如何，第i 趟排序中选择最小关键字的记录，需做n-i次比较，因此总的比较次数为：,堆排序 树型选择排序。 堆是一关键字序列k1,k2,kn,它具有如下特性： kik2i 且 ki k2i+1 或kik2i 且 k2i+1 (i=1,2, n/2) 堆的特性在完全二叉树中解释： 在排序过程中，将R1到Rn看成是一个完全二叉树顺序存储结构，在完全二叉树中任一结点的关键字都小于等于（或大于等于）它的左右孩子的关键字。 堆排序分为两个步骤： 1、根据初始输入，形成初始堆。 2、通过一系列的对象交换和重新调整进行排序。,10,15,56,25,30,70,10,15,56,25,30,70,小根堆示例,70,56,30,25,15,10,70,56,30,25,15,10,大根堆示例,堆排序的第一个工作是建堆，即把整个记录数组R1到Rn调整为一个堆。 只有一个结点的树是堆，而在完全二叉树中，所有序号i low(n/2)的结点都是叶子，因此，以这些结点为根的子树都已是堆。 即只需依次将序号为low(n/2)，low(n/2)-1，.，1的结点作为根的子树都调整为堆即可。 以大根堆为例进行说明 “筛选法”基本思想：因为Ri的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以在Ri和它的左右孩子中选取关键字最大的结点放到Ri的位置上。,若Ri的关键字已是三者中的最大者，则无须做任何调整，以Ri为根的子树已构成堆， 否则，将Ri和具有最大关键字的左孩子R2i或右孩子R2i+1进行交换。 假定R2i的关键字最大，将Ri和R2i交换位置，交换之后有可能导致R2i为根的子树不再是堆，但由于R2i的左右子树仍然是堆，于是可以重复上述过程，将以R2i为根的子树调整为堆，.，如此逐层递推下去，最多可能调整到树叶。,例子：关键字序列为 42，13，91，23， 24， 16，05，88，n=8，故从第四个结点开始调整,42,13,91,23,24,16,05,88,42,13,91,23,24,16,05,88,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,不调整,42,13,91,88,24,16,05,23,42,13,91,88,24,16,05,23,42,88,91,23,24,16,05,13,42,88,91,23,24,16,05,13,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,建成的堆,筛选算法 SIFT(rectype R,int i;int m) int j; rectype temp; temp=Ri; j=2*i; while (j=m) if (jm) ,上述算法只是对一个指定的结点进行调整。将初始的无序区R1到Rn建成一个大根堆，可用以下语句实现： for (i = n/2; i=1; i-) SIFT(R, i, n) 由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该将R1和Rn交换，这就得到了第一趟排序的结果。 第二趟排序的操作首先是将无序区R1到Rn-1调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用SIFT函数将R1到Rn-1调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录Rn-1交换，如此反复进行下去。,91,88,42,23,24,16,05,13,91,88,42,23,24,16,05,13,（a）初始堆R1到R8,13,88,42,23,24,16,05,91,13,88,42,23,24,16,05,91,（b）第一趟排序之后,（c）重建的堆R1到R7,88,24,42,23,13,16,05,91,88,24,42,23,13,16,05,91,05,24,42,23,13,16,88,91,05,24,42,23,13,16,88,91,（d）第二趟排序之后,（e）重建的堆R1到R6,42,24,16,23,13,05,88,91,42,24,16,23,13,05,88,91,（f）第三趟排序之后,05,24,16,23,13,42,88,91,05,24,16,23,13,42,88,91,（g）重建的堆R1到R5,24,23,16,05,13,42,88,91,24,23,16,05,13,42,88,91,（h）第四趟排序之后,13,23,16,05,24,42,88,91,13,23,16,05,24,42,88,91,（i）重建的堆R1到R4,23,13,16,05,24,42,88,91,23,13,16,05,24,42,88,91,（j）第五趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（k）重建的堆R1到R3,16,13,05,23,24,42,88,91,16,13,05,23,24,42,88,91,（l）第六趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,（m）重建的堆R1到R2,13,05,16,23,24,42,88,91,13,05,16,23,24,42,88,91,（n）第七趟排序之后,05,13,16,23,24,42,88,91,05,13,16,23,24,42,88,91,堆排序算法 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=Ri; Ri=temp; SIFT(R,1,i-1); ,堆排序的时间复杂度 堆排序的时间复杂性为O(n log2n) 空间复杂性为 O(1) 堆排序是不稳定的排序方法。,五、归并排序 通过对两个有序结点序列的合并来实现排序。 归并：将若干个已排好序的部分合并成一个有序的部分。 归并的基本思想 将待排序列R0到Rn-1看成n个长度为1的有序子序列，把这些子序列两两归并，便得到high(n/2)个有序的子序列。然后再把这high(n/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,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) ,归并排序算法 MERGESORT(rectype R) int length=1; while (lengthn) MERGEPASS(R,R1,length); length=2*length; MERGEPASS(R1,R,length); length=2*length; ,算法复杂性分析 归并排序在第i 趟归并后，有序子文件长度为2i，因此，因此，对于具有n个记录的序列来说，必须做high(log2n)趟归并，每趟归并所花的时间为O(n)。所以，二路归并排序算法的时间复杂度为O(nlog2n)，辅助数组所需的空间为O(n)。 归并排序是稳定的排序方法。,六、基数排序 基本原理，采用“分配”和“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。 下面先介绍多关键字排序 多关键字排序方法示例 如对扑克牌的排序 每张扑克牌有两个“关键字”：花色和面值它们之间有次序的优先。 对以上排序，可以先对花色排序，或先对面值排序。,多关键字有序的概念 考虑对象序列V0,V1,., Vn-1，每个对象Vi含d个关键字(Ki1,Ki2,., Kid)。若对序列中的任意两个对象Vi和Vj都有 (Ki1,Ki2,., Kid) (Kj1,Kj2,., Kjd) 则称序列对关键字(Ki1,Ki2,., Kid)有序，且K1称为最高位关键字，Kd称为最低位关键字。,多关键字排序 原理：根据组成关键字的各位的值进行排序。 实现基数排序的两种方法： 最高位优先(MSD)排序：从关键字的高位到低位 最低位优先(LSD)排序：从关键字的低位到高位 MSD方法通常是一个递归的过程。 LSD和MSD方法也可应用于对一个关键字进行的排序。此时可将单关键字Ki看成是一个子关键字组： (Ki1,Ki2,., Kid) 如对关键字取值范围为0到999的一组对象，可看成是(K1,K2,K3)的组合。 MSD方法按K1,K2,K3的顺序对所有对象排序；LSD方法按K3 ,K2 , K1的顺序对所有对象排序。,链式的基数排序 基数排序是一种典型的LSD排序方法，它利用“分配”和“收集”两种运算对单关键字进行排序。 此时可将单关键字K看成是一个子关键字组： (Ki1,Ki2,., Kid) 排序过程：设关键字共有d位，让j= d, d-1,.,1, 依次执行d次“分配”与“收集”。,179,208,306,93,859,984,55,9,271,33,B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f,B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e,271,93,33,984,55,306,208,179,859