第+10+章+排序n.ppt

内部排序,教学内容1、插入排序（直接插入排序、折半插入排序、希尔排序）；2、交换排序（起泡排序、快速排序）；3、选择排序（直接选择排序、堆排序）；4、归并排序；5、基数排序；,排序：将数据元素的一个任意序列，重新排列成一个按关键字有序的序列。,10.1概述,例：将关键字序列：52,49,80,36,14,58,61,23,调整为：14,23,36,49,52,58,61,80,若按主关键字排序则结果惟一。,若按次关键字排序则结果可以不惟一（因有相同关键字）。,设Ki、Kj(1in,1jn,ij)分别为记录Ri、Rj的关键字，且Ki=Kj，在排序前的序列中Ri领先于Rj（即ij）。若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。,例：设排序前的关键字序列为：52,49,80,36,14,58,36,23若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是稳定的。若排序后的关键字序列为：14,23,36,36,49,52,58,80，则排序方法是不稳定的。,内部排序和外部排序,若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；,反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。,排序方法分类：,1)、插入排序：直接插入排序、折半插入排序、希尔排序,2)、交换排序：冒泡排序、快速排序,3)、选择排序：简单选择排序、堆排序,4)、归并排序：2-路归并排序,5)、基数排序,10.2插入排序,有序序列R1.i-1,Ri,无序序列Ri.n,一趟直接插入排序的基本思想：,有序序列R1.i,无序序列Ri+1.n,实现“一趟插入排序”可分三步进行：,3将Ri插入（复制）到Rj+1的位置上。,2将Rj+1.i-1中的所有记录均后移一个位置；,1在R1.i-1中查找Ri的插入位置，R1.j.keyRi.keyRj+1.i-1.key；,10.2.1直接插入排序,i=2,38,49,38,7趟排序,1趟排序,2趟排序,voidInsertSort(SqList+i)if(L.ri.keyL.ri-1.key)/InsertSort,排序过程：先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。,在R1.i-1中查找Ri的插入位置;对于在查找过程中找到的那些关键字不小于Ri.key的记录，在查找的同时实现记录向后移动；插入Ri;,L.r0=L.ri;/复制为监视哨L.ri=L.ri-1;for(j=i-2;L.r0.keyL.rj.key;-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置,比较次数和移动次数均约为：,T(n)=O(n),算法评价,时间复杂度：,比较次数：,移动次数：0,最好的情况：待排序记录按关键字从小到大排列（正序）,比较次数：,移动次数：,最坏的情况：待排序记录按关键字从大到小排列（逆序）,一般情况：待排序记录是随机的，取平均值。,空间复杂度：S(n)=O(1),直接插入排序是稳定排序,10.2.2其他插入排序,1、折半插入排序：用折半查找方法确定插入位置的排序。,voidBInsertSort(SqList/插入/for/BInsertSort,i=1(30)1370853942620,i=76(6133039427085)20,i=820(613203039427085),T(n)=O(n),时间复杂度：,空间复杂度：S(n)=O(1),折半插入排序是稳定排序,仅减少了比较次数，移动次数不变。,第二趟希尔排序,第三趟分组，设d3=1,10.2.3希尔排序（缩小增量排序）,基本思想：对待排序列先作“宏观”调整，再作“微观”调整。,排序过程：先取一个正整数d1n，把所有相隔d1的记录放在一组内，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。其中di称为增量。,例：,第一趟希尔排序,第三趟希尔排序,第一趟分组，设d1=5,49386597761327495504,13274955044938659776,第二趟分组，设d2=3,希尔排序特点：,分组不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列。,增量序列取法希尔最早提出的选法是d1=n/2，di+1=di/2。克努特(Knuth)提出的选法是di+1=(di-1)/3。还有其他不同的取法。如何选择增量序列以产生最好的排序效果，至今仍没有从数学上得到解决。1)、没有除1以外的公因子；2)、最后一个增量值必须为1。,希尔排序可提高排序速度1)、记录跳跃式前移，在进行最后一趟排序时，已基本有序。2)、分组后n值减小，n2更小，而T(n)=O(n2)，所以T(n)从总体上看是减小了。,3、重复直到“在一趟排序过程中没有进行过交换记录的操作”或“仅第一二个交换过”为止。,冒泡排序算法,10.3交换排序,1、冒泡排序,1、比较第一个记录与第二个记录，若关键字为逆序则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。,2、对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置。,第一趟排序,49,38,49,97,76,97,97,13,97,97,27,97,97,49,97,3849657613274997,38496513274976,第二趟排序,384913274965,第三趟排序,3813274949,第四趟排序,13273849,第五趟排序,132738,第六趟排序,for(j=1;jn;j+)if(rj+1rj)rjrj+1;,for(j=1;j1),/while,i=n;,i=k;,VoidBubbleSort(SqList/交换的位置,k=1;,排序过程,一般情况下每经过一趟“起泡”，“i减1”，但并不是每趟都如此。,例：,i=6,i=2,i=1,算法评价,时间复杂度：,最好情况（正序）,比较次数：n-1移动次数：0T(n)=O(n),最坏情况（逆序）,比较次数：移动次数：,T(n)=O(n2),空间复杂度：S(n)=O(1),稳定性：稳定排序,s,一般取第一个记录,基本思想：任选一个记录，以它的关键字作为“枢轴”，凡关键字小于枢轴的记录均移至枢轴之前，凡关键字大于枢轴的记录均移至枢轴之后。,2、一趟快速排序（一次划分）,low,high,设Rs=52为枢轴。,例：,52,t,附设两个指针low和high，从high所指位置起向前搜索找到第一个关键字小于枢轴的关键字的记录与枢轴记录交换，然后从low+1所指位置起向后搜索找到第一个关键字大于枢轴的关键字的记录与枢轴记录交换，重复这两步直至low=high为止。,high,23,low,low,80,high,high,high,high,14,low,low,52,快速排序过程,3、快速排序,首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行一趟快速排序。,无序的记录序列,无序记录子序列(1),无序子序列(2),枢轴,一次划分,分别进行一趟快速排序,有序的记录序列,若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。所以快速排序适用于原始记录排列杂乱无章的情况。,为避免出现蜕化情况，需在进行一次划分之前，进行“预处理”，即：先对R(s).key,R(t).key和R(s+t)/2.key，进行相互比较，然后取关键字的大小为中间的记录为枢轴记录。,到目前为止快速排序是平均速度最大的一种排序方法。时间复杂度为O(nlogn)。,快速排序是一种不稳定的排序，在递归调用时需要占据一定的存储空间用来保存每一层递归调用时的必要信息。,10.4选择排序,10.4.1简单选择排序,排序过程：首先通过n1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换。再通过n2次比较，从剩余的n1个记录中找出关键字次小的记录，将它与第二个记录交换。重复上述操作，共进行n1趟排序后，排序结束。,j+,if(L.rj.keyL.rk.key)k=j;,j=i+1;,for(i=1;iL.length;+i),例：,初始：49386597761327,i=1,13,49,一趟：13386597764927,i=2,二趟：13276597764938,三趟：13273897764965,四趟：13273849769765,五趟：13273849659776,六趟：13273849657697,排序结束：六趟：13273849657697,k=i;,for(j=i+1;j=n;j+)if(L.rj.keyL.rk.key)k=j;,if(i!=k)L.riL.rk;/与第i个记录交换,i=6,voidSelectSort(SqList&L)/对顺序表L作简单选择排序。,/SelectSort,i=3,i=4,i=5,比较次数,n-1,n-2,n-6,比较次数：,移动次数：,正序：最小值为0；,最大值为3(n-1)。,例：前n1个为正序，第n个记录的关键字最小。,时间复杂度：O(n2),空间复杂度：O(1),不稳定,10.4.3堆排序,堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆。,或,(i=1,2,n/2),kik2ikik2i+1,kik2ikik2i+1,小顶堆,大顶堆,小根堆,正堆,大根堆,逆堆,例1：(96,83,27,38,11,09),例2：(13,38,27,49,76,65,49,97),可将堆序列看成完全二叉树，则：k2i是ki的左孩子；k2i+1是ki的右孩子。所有非终端结点的值均不大（小）于其左右孩子结点的值。堆顶元素必为序列中n个元素的最小值或最大值。,堆排序：,堆排序需解决的两个问题：1、如何由一个无序序列建成一个堆？2、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？,将无序序列建成一个堆，得到关键字最小（大）的记录；输出堆顶的最小（大）值后，将剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；如此重复执行，直到堆中只有一个记录为止，每个记录出堆的顺序就是一个有序序列，这个过程叫堆排序。,堆,堆,筛选,所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树也成为一个堆。,第二个问题解决方法筛选：,输出堆顶元素后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小（大）者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。,97,97,27,97,49,97,38,97,97,49,65,65,49,76,49,76,97,97,65,76,27,65,49,38,49,97,13,76,对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)。,81,73,64,27,98,12,第一个问题解决方法：从无序序列的第n/2个元素（即无序序列对应的完全二叉树的最后一个内部结点）起，至第一个元素止，进行反复筛选。,建堆是一个从下往上进行“筛选”的过程。,例:排序之前的关键字序列为：,40,55,49,36,12,36,73,49,98,81,98,49,40,现在，左/右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个“堆”即可。,81,73,55,堆排序的时间复杂度和空间复杂度：,1.对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1)；,3.调整“堆顶”n-1次，总共进行的关键字比较的次数不超过2(log2(n-1)+log2(n-2)+log22)2n(log2n),因此，堆排序的时间复杂度为O(nlogn)，与简单选择排序O(n2)相比时间效率提高了很多。,2.对n个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多4n；,空间复杂度：S(n)=O(1),堆排序是一种速度快且省空间的排序方法。,不稳定。,10.5归并排序,归并：将两个或两个以上的有序表组合成一个新的有序表。,在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列归并为一个记录有序的序列。,初始关键字：49386597761327,一趟归并后：38496597137627,二趟归并后：38496597132776,三趟归并后：13273849657697,看成是n个有序的子序列（长度为1），然后两两归并。,得到n/2个长度为2或1的有序子序列。,空间复杂度为：O(n)。时间复杂度为：O(nlog2n)。稳定。,每趟归并的时间复杂度为O(n)，共需进行log2n趟。,10.6基数排序,基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。,10.6.1多关键字的排序,例：将右表所示的学生成绩单按数学成绩的等级由高到低排序，数学成绩相同的学生再按英语成绩的高低等级排序。,105AA102AB104BB101BC108CB103CD106DB107EA,特点：每个记录最终的位置由两个关键字k1k2决定。,第二关键字K2,第一关键字K1,我们将它称之为复合关键字，即多关键字排序是按照复合关键字的大小排序。,例：扑克牌中52张牌，可按花色和面值分成两个“关键字”，其大小关系为：花色：面值：2345678910JQKA,若对扑克牌按花色、面值进行升序排序，得到如下序列：2,3,.,A,2,3,.,A,2,3,.,A,2,3,.,A,即两张牌，若花色不同，不论面值怎样，花色低的那张牌小于花色高的，只有在同花色情况下，大小关系才由面值的大小确定。这也是按照复合关键字的大小排序，即：多关键字排序。,多关键字排序的方法：,n个记录的序列R1,R2,Rn对关键字(Ki0,Ki1,Kid-1)有序是指：对于序列中任意两个记录Ri和Rj(1ijn)都满足下列（词典）有序关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1),其中：K0被称为最主位关键字，Kd-1被称为最次位关键字。,多关键字排序按照从最主位关键字到最次位关键字或从最次位关键字到最主位关键字的顺序逐次排序，分两种方法：,最高位优先法，简称MSD法：先按k0排序分组，同一组中记录，关键字k0相等，再对各组按k1排序分成子组，之后，对后面的关键字继续这样的排序分组，直到按最次位关键字kd对各子组排序后，再将各组连接起来，便得到一个有序序列。,3,1,20,1,2,15,2,3,18,1,2,15,无序序列,3,2,30,最低位优先法，简称LSD法：先从kd-1开始排序，再对kd-2进行排序，依次重复，直到对k0排序后便得到一个有序序列。,例：学生记录含三个关键字：系别、班号和班内的序列号，其中以系别为最主位关键字。,对K2排序,对K1排序,对K0排序,3,1,20,2,1,20,2,3,18,3,1,20,2,1,20,3,2,30,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,LSD的排序过程如下：,对Ki(0id-2)进行排序时，只能用稳定的排序方法。,例：先将学生记录按英语等级由高到低分成A、B、C、D、E五个组：,用LSD法进行的排序，在一定的条件下（即对Ki的不同值Ki+1均取相同值），可通过若干次“分配”和“收集”来实现。,然后按从左向右，从上向下的顺序将它们收集起来得到关键字序列：AA，EA，AB，BB，DB，CB，BC，CD,再按数学成绩由高到低分成A、B、C、D、E五个组：,可以看出，这个关键字序列已经是有序的了。,AA，AB，BB，BC，CB，CD，DB，EA,对每个关键字都是将整个序列按关键字分组，然后按顺序收集，显然LSD法，操作比较简单。,按从上向下，从左向右的顺序将其收集起来得到关键字序列：AA，EA，AB，BB，DB，CB，BC，CD,按从上向下，从左向右的顺序将其收集起来得到关键字序列：,MSD与LSD的不同特点,必须将序列逐层分割成若干子序列，然后对各子序列分别排序。,不必分成子序列，对每个关键字都是整个序列参加排序；通过若干次分配与收集实现排序。,LSD,MSD,基数排序：,是借助于多关键字排序思想进行排序的一种排序方法。该方法将排序关键字K看作是由多个关键字组成的组合关键字，即：K=k0k1kd-1。每个关键字ki表示关键字的一位，其中k0为最高位，kd-1为最低位，d为关键字的位数。,例：对于关键字序列(101,203,567,231,478,352)，可以将每个关键字K看成由三个单关键字组成，即K=k1k2k3，每个关键字的取值范围为0ki9，所以每个关键字可取值的数目为10。通常将关键字取值的数目称为基数，用r表示，在本例中r=10。,对于关键字序列（AB,BD,ED）可以将每个关键字看成是由二个单字母关键字组成的复合关键字，并且每个关键字的取值范围为“AZ”，所以关键字的基数r=26。,基数排序可用多关键字的LSD方法排序，即对待排序的记录序列按复合关键字从低位到高位的顺序交替地进行“分组”、“收集”，最终得到有序的记录序列。在此我们将一次“分组”、“收集”称为一趟。对于由d位关键字组成的复合关键字，需要经过d趟的“分配”与“收集”。因此，若d值较大，基数排序的时间效率就会随之降低。,在计算机上实现基数排序时，为减少所需辅助存储空间，应采用链表作存储结构，即链式基数排序，具体作法为：,10.6.2链式基数排序,1、以静态链表存储待排记录，并令表头指针指向第一个记录；,2、“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同；,3、“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表；,4、对每个关键字位均重复2和3两步。,例：,以静态链表存储待排记录，并令表头指针指向第一个记录。,“分配”时，按当前“关键字位”所取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同。,时间复杂度：,算法评价：,分配（每趟）：T(n)=O(n),收集（每趟）：T(n)=O(rd),T(n)=O(d(n+rd),空间复杂度：S(n)=2rd个队列指针+n个指针域空间,假设：n记录数d关键字数rd关键字取值范围（如十进制为10）,一、时间性能,时间复杂度为O(nlogn)：快速排序、堆排序和归并排序，其中以快速排序为最好。,时间复杂度为O(n2)：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字基本有序的记录序列尤为如此。,时间复杂度为O(n)：基数排序。,1.按平均时间性能