第9章-排序总结.ppt

1,第九章排序,2,本章目录,3,9.1基本概念,4,排序,排序的定义,给定一个记录集合（r1,r2,rn），其相应的关键码分别为（k1,k2,kn），排序是将这些记录排成顺序为（rs1,rs2,rsn）的一个序列，使得相应的关键码满足ks1ks2ksn（非降序或升序）或ks1ks2ksn（非升序或降序）。,5,排序算法的稳定性,若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序,若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；,不能保持一致的排序方法则称为不稳定的。,6,排序的分类,按照参加排序的数据元素（记录）是否全部放置在内存中可把排序分为内排序和外排序。内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。,7,排序的分类,按照排序所依据的关键码的个数可以把排序分为单键排序和多键排序。单键排序：根据一个关键码进行的排序。多键排序：根据多个关键码进行的排序。,8,排序的分类,按照排序的方法是否建立在关键码比较的基础上可以把排序分为：基于比较：主要是通过关键码之间的比较和记录的移动这两种操作来实现的排序。不基于比较：根据待排序数据的特点所采取的其它方法，通常是没有大量的关键码之间的比较和记录的移动操作的排序。,9,内排序的方法,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,经过一趟排序,有序序列区,无序序列区,有序序列区,无序序列区,10,内排序的主要方法,将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度，最终完全排序工作。,11,内排序的主要方法,通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,12,内排序的主要方法,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,13,内排序的主要方法,通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。,14,9.2插入排序,15,算法思想,仅有一个记录的表总是有序的，因此，对于n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。,直接插入排序,16,直接插入排序,操作步骤：Step1:选取L.key1作为初始的有序序列,i=2;Step2:将L.keyi插入到前面的有序序列中，使其有序序列长度增加1；Step3:i=i+1，若i的值小于表长，则重复Step2，否则排序结束。,17,直接插入排序,算法分析：空间效率：仅用了一个辅助单元，O(1)。时间效率：最好情况下：初始序列是顺序的最坏情况下：初始序列是逆序的平均情况下：初始序列是无序的稳定性：是一种稳定的排序方法。,18,直接插入排序,总比较次数=n-1,总移动次数=2(n-1),19,折半插入排序,算法思想,设在顺序表中有一个对象序列V0,V1,Vn-1。其中,V0,V1,Vi-1是已经排好序的对象。在插入Vi时,利用折半查找法寻找Vi的插入位置。,20,折半插入排序,操作步骤：Step1:顺序表中前j-1个记录有序，将第j个记录插入。令low=1；high=j-1；r0=rj；Step2:若lowhigh，得到插入位置，转Step5;Step3:若lowhigh，则取有序子表的中点m=(low+high)/2；Step4:若r0.keyr0.next；将i指向第一个记录位置；Step2:若i=l-length时，调整结束；否则:,2.1若i=j，j=l-rj.next；数据元素应在这分量中，不用调整处理下一个结点：i+；转Step2；,2.2若ji，则l-ri.eleml-rj.elem；保存下一个结点地址：p=l-rj.next；同时保持后续链表不被中断：l-rj.next=l-i.next；l-i.next=j；指向下一个处理的结点：j=p；i+；转Step2;,2.3若jrj.next；转到2.1。,25,表插入排序,举例说明,26,表插入排序,算法分析：时间复杂度：设有序表长度为i，则需要比较至多i+1次，修改指针两次。因此，总比较次数与直接插入排序相同，修改指针总次数为2n次。所以，时间复杂度仍为O(n2)。空间复杂度：表插入排序的空间复杂度为O(1)。稳定性：表插入排序是一种稳定的排序方法。,27,希尔排序,算法思想,先将整个待排记录分割成若干个子序列，在子序列中分别进行直接插入排序，待整个序列基本有序的时候，再对全体序列进行一次直接插入排序。,28,希尔排序,操作步骤：Step1:选择一个步长序列t1，t2，tk，其中titj，tk=1；Step2:按步长序列个数k，对序列进行k趟排序；Step3:每趟排序，根据对应的步长ti，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅步长因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。,29,希尔排序,举例说明：,30,希尔排序,算法分析：时间复杂度：由于希尔排序是依赖于增量的选取，它的时间复杂度是在O(nlog2n)O(n2)之间。空间复杂度：在希尔排序的过程中只需要一个辅助空间用于暂存当前待插入的记录，因此，希尔排序的空间复杂度为O(1)。稳定性：希尔排序方法是一种不稳定的排序方法。,31,9.3交换排序,32,冒泡排序,假设在排序过程中，记录序列R1.n的状态为：,第i趟冒泡排序,无序序列R1.n-i+1,有序序列Rn-i+2.n,n-i+1,无序序列R1.n-i,有序序列Rn-i+1.n,比较相邻记录，将关键字最大的记录交换到n-i+1的位置上,33,冒泡排序,算法思想,对n个记录的表，第一趟冒泡得到一个关键码最大的记录rn，第二趟冒泡对n-1个记录的表，再得到一个关键码最大的记录rn-1，如此重复，直到n个记录按关键码有序的表。,34,冒泡排序,一趟冒泡方法：Step1:i=1；/设置从第一个记录开始进行两两比较Step2:若ij，一趟冒泡结束。Step3:比较ri.key与ri+1.key，若ri.keyri+1.key，不交换，转Step5;Step4:当ri.keyri+1.key时，r0=ri；ri=ri+1；ri+1=r0；/将ri与ri+1交换Step5:i=i+1；对下两个记录进行两两比较，转Step2;,35,冒泡排序,操作步骤：Step1:从n记录的表尾开始，j=n；Step2:若jri+1.key时，将ri与ri+1交换;Step7:i=i+1；调整对下两个记录进行两两比较，转Step4;,37,冒泡排序,语言描述:templatevoidBubbleSort(SqList/交换L.keyj和L.keyj+1的值,38,冒泡排序,算法分析：空间复杂度：冒泡排序的空间复杂度为O(1)。时间复杂度：总共要进行n-1趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关键码比较。冒泡排序的时间复杂度为O(n2)。稳定性：冒泡排序是一种稳定的排序方法。,39,快速排序,算法思想：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列Rs.t将分割成两部分：Rs.i-1和Ri+1.t，且Rj.keyRi.keyRj.key(sji-1)枢轴(i+1jt)。,40,快速排序,示例,s,t,low,high,设Rs=52为枢轴,high,23,low,80,high,14,low,52,R0,52,low,high,high,high,low,41,快速排序,操作步骤：Step1:如果待排子序列中元素的个数大于1，则以L.rlow作为枢轴，进行一次划分；否则排序结束。Step2:对枢轴左半子序列重复Step1;Step3:对枢轴右半子序列重复Step1;,42,快速排序,算法分析：空间复杂度：快速排序是递归的，递归调用层次数与其二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)；在最坏情况下，为O(n)。时间复杂度：最好情况下为O(nlog2n)，最坏情况，快速排序蜕化为冒泡排序。稳定性：快速排序是一个不稳定的排序方法。,43,9.4选择排序,44,简单选择排序,假设排序过程中，待排记录序列的状态为：,有序序列R1.i-1,无序序列Ri.n,第i趟简单选择排序,从中选出关键字最小的记录,有序序列R1.i,无序序列Ri+1.n,45,简单选择排序,算法思想:第一趟，从n个记录中找出关键码最小的记录与第一个记录交换；第二趟，从第二个记录开始的n-1个记录中再选出关键码最小的记录与第二个记录交换；如此，第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换，直到整个序列按关键码有序。,46,简单选择排序,操作步骤：Step1:从L.keyi从L.keylength记录中选择一个关键字值最小的记录，将其下标保存至min中；Step2:若L.keyiL.keymin;则交换这两个记录;否则转Step3;Step3:i=i+1,若iL.length，则转Step1;否则排序结束。,47,简单选择排序,算法分析：时间复杂度：从算法中可看出，简单选择排序移动记录的次数较少，但关键码的比较次数依然是，算法的时间复杂度仍是O(n2)。空间复杂度：简单选择排序算法只需要一个辅助空间来作为交换记录用的暂存单元。因此，它的空间复杂度O(1)。稳定性：简单选择排序是一种稳定的排序方法。,48,树形选择排序,操作步骤:Step1:从最底层叶子结点开始，按层一一进行兄弟间的比赛，关键字值较大者上升为子树根结点，直到树的顶层为止；Step2:将树的根结点输出，把底层叶子中值相同的结点值改为0；如果输出的结点总数小于初始时树的叶子结点总数，则重复Step1;否则结束排序。,49,树形选择排序,算法分析：时间复杂度：除了最大关键字之外，每选择一个次大的关键字只需要进行log2n次比较，因此，它的时间复杂度为O(nlogn)。空间复杂度：需要附加n个辅助空间用来保存排序的结果，还要n-1个辅助空间作为排序过程中使用。因此，它的空间复杂度O(n)。稳定性：树形选择排序是一种不稳定的排序方法。这是因为在比较的过程中是跳跃式进行的。,50,堆排序,堆的定义：第一种定义方式：设有n个元素的序列k1，k2，kn，当且仅当满足下述关系之一时，称之为堆。第二种定义方式：堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆或小顶堆）；或者每个结点的值都大于或等于其左右孩子结点的值（称为大根堆或大顶堆）。,51,堆排序,算法思想：设有n个元素，将其按关键码排序。首先将这n个元素按关键码建成堆，将堆顶元素输出，得到n个元素中关键码最小(或最大)的元素。然后，再对剩下的n-1个元素建成堆，输出堆顶元素，得到n个元素中关键码次小(或次大)的元素。如此反复，便得到一个按关键码有序的序列。称这个过程为堆排序。,52,堆排序,堆排序需解决的两个问题：1.怎样建堆：如何将n个元素的序列按关键码建成堆；2.怎样调整：输出堆顶元素后，怎样调整剩余n-1个元素，使其按关键码成为一个新堆。,53,堆排序,建堆方法：先把待排序序列构造成一棵完全二叉树;然后从下往上,自右而左进行筛选,最终得到堆.,a.8个结点的初始状态,例：,54,堆排序,b.从第4个结点开始筛选,55,堆排序,e.对整棵树进行筛选,56,堆排序,操作步骤：Step1:i=1,对顺序表L1L.lengh-i+1中的建大顶堆；Step2:将堆顶元素和LL.lengh-i+1交换；Step3:i=i+1,若iv或jt，则比较选取结束转Step4；Step3:选取ri和rj中关键码较小的存入辅助数组rf。如果ri.keyrj.key，则rfk=ri；i+；k+；否则，rfk=rj；j+；k+。转Step2;Step4:将尚未处理完的子表中元素存入rf：Step5:合并结束。,60,二路归并排序,递归算法操作步骤：Step1:将待排序的记录序列分为两个相等的子序列，分别将这两个子序列进行排序；Step2:调用一次归并算法Merge，将这两个有序子序列合并成一个含有全部记录的有序序列。,61,二路归并排序,算法分析:时间复杂度：归并过程对应由叶向根生成一棵二叉树的过程，所以归并趟数约等于二叉树的高度-1，即log2n，每趟归并需移动记录n次，故时间复杂度为O(nlog2n)。空间复杂度：需要一个与表等长的辅助元素数组空间，所以空间复杂度为O(n)。稳定性：由一次归并算法中的if语句可知，二路归并算法是一种稳定的算法。,62,9.6基数排序,基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。,63,多关键码排序,定义：n个记录的序列R1,R2,，Rn对关键字(Ki1,Ki2,Kid)有序是指：对于序列中任意两个记录Ri和Rj(1ijn)都满足下列(词典)有序关系：(Ki1,Ki2,Kid)(Kj1,Kj2,Kjd)，其中:K1被称为“最主”位关键字，Kd被称为“最次”位关键字。,64,多关键码排序,两种方法最高位优先MSD法先对K1进行排序，并按K1的不同值将记录序列分成若干子序列之后，分别对K2进行排序，.，依次类推，直至最后对最次位关键字排序完成为止。最低位优先LSD法先对Kd进行排序，然后对Kd-1进行排序，依次类推，直至对最主位关键字K1排序完成为止。,65,多关键码排序,例如:学生记录含三个关键字:系别、班号和班内的序列号，其中以系别为最主位关键字。LSD的排序过程如下:,无序序列,对K3排序,对K2排序,对K1排序,3,2,30,1,2,15,3,1,20,2,3,18,2,1,20,1,2,15,2,3,18,3,1,20,2,1,20,3,2,30,3,1,20,2,1,20,1,2,15,3,2,30,2,3,18,1,2,15,2,1,20,2,3,18,3,1,20,3,2,30,66,链式基数排序,算法思想：从最低位关键码起，按关键码的不同值将序列中的记录“分配”到RADIX个队列中，然后再“收集”之。如此重复d次即可。链式基数排序是用RADIX个链队列作为分配队列，关键码相同的记录存入同一个链队列中，收集则是将各链队列按关键码大小顺序链接起来。,67,链式基数排序,操作步骤：Step1:初始化，建立待排序列的静态链表SL；Step2:从最低位关键码开始，按关键码值将SL中记录分配到各个单链表中；Step3:按照关键码的值，从小到大将各个单链表进行收集，重复Step2，直到排序完成。,68,链式基数排序,例：,69,链式基数排序,70,链式基数排序,71,链式基数排序,算法分析：时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix)。空间效率：需要2*