内部排序.ppt

数据结构第十章内部排序,本章内容10.1 基本概念10.2 插入排序10.3 快速排序10.4 选择排序10.5 归并排序10.6 基数排序,10-3,10.1 基本概念,关键字是记录（数据元素）中的一个（或多个）字段。通常用作检索和排序记录的依据。关键字通常可以进行比较操作。,10-4,10.1 基本概念,排序：设含有n个记录的文件R1,R2,.,Rn，其相应的关键字为K1,K2,.,Kn，将记录按关键字值非递减(或非递增)顺序排列的过程，称为排序。排序的稳定性：对所有的Ki=Kj(ij)（具有相同关键字）,若排序前Ri领先于Rj,排序后Ri仍领先于Rj,则称该排序方法是稳定的，反之，称为不稳定的。稳定性是对序列中的两个相同的关键字在初始序列和最终有序序列中相对位置（即领先关系）是否变化。排序分类内部排序：待排序文件的全部记录存放在内存进行的排序，称为内部排序。外部排序：排序过程中需要进行内外存数据交换的排序，称为外部排序。,10-5,10.1 基本概念,内排序分类：按排序过程依据的原则分为：插入排序交换排序选择排序归并排序计数排序按排序过程所需的工作量分：简单排序先进排序基数排序,10-6,10.2 插入排序,10.2.1 直接插入排序它是最简单的排序方法基本思想：依次将每个待排序的记录插入到一个有序子文件的合适位置(有序子文件记录数增1)例如：已有待排序文件为：45,34,78,12,34,32,29,64。首先将文件的第一个记录，视为有序文件，然后从第二个记录开始，直到最后一个记录，依次将他们插入到有序文件的合适位置。,12,34,32,29,64,45,34,78,10-7,10.2 插入排序,算法分析直接插入排序的算法简洁，容易实现。从时间来看，排序的基本操作为：比较两个记录的大小和移动记录。其中：最小比较次数：Cmin=n-1=O(n)最大比较次数：Cmax=(2+3+n)=(n+2)(n-1)/2=O(n2)最小移动次数：Mmin=0 最大移动次数：Mmax=(2+1+3+1+n+1)=O(n2)若待排序记录序列中出现各种可能排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字比较次数和记录移动次数约为 n2/4。因此，直接插入排序的时间复杂度为 o(n2)。,10-8,10.2 插入排序,结论直接插入排序的效率与待排文件的关键字排列有关；直接插入排序的时间复杂度为O(n2)；直接插入排序是稳定的(这一点由过程中WHILE语句的条件“”保证的，只有小于才交换)。,10-9,10.2 插入排序,10.2.2 折半插入排序(Binary Insertsort)由于是在有序子文件中确定插入的位置，因此可用折半查找来代替直接插入排序法中的顺序查找，从而可减少比较次数。基本思想设在顺序表中有一个记录序列 R1,R2,Rn。其中，R1,R2,Ri-1 是已经排好序的记录。在插入 Ri 时，利用折半搜索法寻找 Ri 的插入位置。,10-10,i=1(30)13 70 85 39 42 6 20,i=2 13(13 30)70 85 39 42 6 20,i=7 6(6 13 30 39 42 70 85)20,i=8 20(6 13 30 39 42 70 85)20,i=8 20(6 13 20 30 39 42 70 85),10.2 插入排序,10.2 插入排序,10-11,算法评价时间复杂度:T(n)=O(n),折半插入排序只能减少排序过程中关键字比较的时间,并不能减少记录移动的时间。稳定的排序方法,10-12,10.2 插入排序,10.2.3 Shell排序基本思想：希尔排序（Shells Methool）又称为缩小增量排序，也是一种插入排序方法。它将待排序数据文件分割成若干个较小的子文件，对各个子文件分别进行直接插入排序，当文件达到基本有序时，再对整个文件进行一次直接插入排序。适用条件如果待排序文件基本有序，即文件中具有特性：ri.key Max rj.key 1jI的记录数较少，则文件中大多数记录不需要进行插入，因而排序效率可以提高，接近于O(n)。,10-13,10.2 插入排序,例1：设初始关键字为：第一趟以步长为5分割为5个子文件：R1,R6 R2,R7 R3,R8 R4,R6 R5,R10 对每个子文件进行直接插入排序第二趟以步长为3对第一趟排序结果分割为3 个子文件：R1,R4,R7,R10 R2,R5,R8(R3,R6,R9对每个子文件进行直接插入排序第三趟以步长为1对第二趟排序结果进行直接插入排序,49 38 65 97 76 13 27 49 55 04,13 27 49 55 04 49 38 65 97 76,原始数据:,第一趟排序:,第二趟排序:,49 49 97,13 38 55 76,04 27 65,04 13 27 38 49 49 55 65 76 97,第三趟排序:,10-14,10.2 插入排序,例2：对下列数据进行shell排序，步长分别选为4、2、1。,12,34,32,29,64,45,34,78,10-15,10.2 插入排序,增量的取法最初 shell 提出取 d1=n/2，d2=d1/2，直到dt=1。后来 knuth 提出取di+1=di/3+1。还有人提出都取奇数为好，也有人提出各增量互质为好。算法分析不稳定空间代价：O(1)增量每次除以2递减，时间代价：O(n2)选择适当的增量序列，可以使得时间代价接近O(n)增量每次除以2递减”时，效率仍然为O(n2)问题：选取的增量之间并不互质间距为2k-1的子序列都是由那些间距为2k的子序列组成的上一轮循环中这些子序列都已经排过序了，导致处理效率不高,10-16,10.3 交换排序,10.3.1 冒泡排序冒泡排序是一种简单而且容易理解的排序方法，它和气泡从水中不断往上冒的情况有些类似。其基本思想对存放原始数据的数组，按从后往前的方向进行多次扫描，每次扫描称为一趟(pass)。当发现相邻两个数据的次序与排序要求的“递增次序”不符合时，就互换两个数据。这样，较小的数据就会逐单元向前移动，好象气泡向上浮起一样。示例,12,34,32,29,64,78,34,45,10-17,10.3 交换排序,算法评价算法稳定空间代价：O(1)时间代价：比较次数：交换次数最多为O(n2)，最少为0，平均为O(n2)。最大，平均时间代价均为O(n2)。最小时间代价为O(n)：最佳情况下只运行第一轮循环,10-18,10.3 交换排序,10.3.2 快速排序基本思想任取某个记录作为基准（通常选文件的第一个记录），将所有关键字不大于它的记录放在它的前面，将所有关键字不小于它的记录放在它的后面；这样遍历一趟文件后，将文件以该记录为界分为两部分；然后对各部分重复上述过程，直到每一部分仅剩一个记录为止。特点：基于分治法的排序：快速、归并。分治策略的实例BST查找、插入、删除算法快速排序、归并排序二分检索主要思想：划分、求解子问题(子问题不重叠)、综合解,10-19,10.3 交换排序,25 34 45 32 3412 29 64,29,32,64,25,34,最终排序结果：12 25 29 32 34 34 45 64,45,10-20,10.3 交换排序,快速排序算法评价快速排序算法不稳定。常用“三者取中”法来选取划分记录，即取首记录rs.key.尾记录rt.key和中间记录r(s+t)/2.key三者的中间值为划分记录。算法分析最差情况：时间代价：O(n2)空间代价：O(n)最佳情况：时间代价：O(nlog n)空间代价：O(log n)平均情况：时间代价：O(nlog n)空间代价：O(log n),10-21,10.4 选择排序,基本思想每一趟(例如第 i 趟，i=1,2,n-1)在后面 n-i+1 个待排序记录中选出关键字最小的记录,作为有序记录序列的第 i 个记录。待到第 n-1 趟作完，待排序记录只剩下1个，就不用再选了。,10-22,10.4 选择排序,10.4.1 简单选择排序基本思想首先在所有记录中选出关键字最小的记录，把它与第1个记录交换，然后在其余的记录中再选出关键字次最小的记录与第2个记录交换，以次类推，直到所有记录排序完成。,10-23,10.4 选择排序,初始关键字序列,34,12,49,28,31,52,51,49*,0,10-24,10.4 选择排序,算法分析交换次数：正序时交换次数最少，为0次，逆序时最多，为n-1次。比较次数：与初始文件关键字排列无关，为n(n-1)/2次。简单选择排序时间复杂度为O(n2)，并且是稳定的排序。,10-25,10.4 选择排序,10.4.2 堆排序堆的定义对于n个元素的序列k1,k2,.,kn，当且仅当满足以下关系时，称之为堆。,或,10-26,10.4 选择排序,若将堆视为一个完全二叉树，则堆的含义为：完全二叉树中所有非叶结点的值(ri)均不大于(或不小于)其左孩子的值(r2i)、右孩子的值(r2i+1)。堆顶元素(完全二叉树的根)是序列中最小(或最大)的元素。,12,65,49,81,55,34,98,是堆,14,不,36,40,73,27,10-27,10.4 选择排序,堆排序(Heap Sort)基本思想以初始关键字序列，建立堆；输出堆顶最小元素；调整余下的元素，使其成为一个新堆；重复2,3步，直到n个元素输出，得到 一个有序序列。关键问题：要解决1和3，即如何由一个无序序列建成一个堆?如何调整余下的元素成为一个新堆?,10-28,10.4 选择排序,调整方法将堆顶元素和堆的最后一个元素位置交换；然后以当前堆顶元素和其左、右子树的根结点进行比较(此时，左、右子树均为堆)，并与值较小的结点进行交换；重复第2步，继续调整被交换过的子树，直到叶结点或没进行交换为止。称这个调整过程为筛选。,10-29,10.4 选择排序,例如：设有关键字13,38,27,49,76,65,49,97，按初始次序构成一棵完全二叉树，形成一个堆如下图：,10-30,10.4 选择排序,堆排序的时间复杂度分析对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);对n个关键字，建成深度为h(=log2n+1)的堆，所需进行的关键字比较的次数至多为4n;调整“堆顶”n-1次，总共进行的关键字比较的次数不超过2(log2(n-1)+log2(n-2)+log22)2n(log2n)因此，堆排序的时间复杂度为O(nlogn)，且不稳定。,10-31,10.5 归并排序,归并归并是指将若干个已排序好的有序表合并成一个有序表。两个有序表的归并称为二路归并。归并排序将待排序的n个记录，看作n个有序的子序列，每个子序列的长度为1。然后两两归并，得到n/2个长度为2或为1的子序列；再两两归并，.，如此重复，直到得到长度为n的子序列为止。这种排序的方法称为2_路归并排序。,10-32,10.5 归并排序,2_路归并排序的核心操作：将一维数组中前后两个有序序列归并为一个有序序列。例：将一维数组49,38,65,97,76,13,27,49进行2_路归并排序：,初始：49，38，65，97，76，13，27，49,第一趟：38，49，65，97，13，76，27，49,第二趟：38，49，65，97，13，27，49，76,第三趟：13，27，38，49，49，65，76，97,10-33,10.5 归并排序,将两个有序序列归并为一个有序序列的算法,void merge(Sqlist SR,Sqlist,10-34,10.5 归并排序,一趟归并排序操作需调用n/(2h)次算法merge，将SR1.n前后相邻且长度为h的有序段两两归并,得到前后眼相邻、长度为2h的有序段,并放在TR1.n中。整个归并排序需要log2n趟。递归算法：排序区间：Rs.t设：m=（int）(low+high)/2)可递归地对两个子区间Rs.m和Rm+1.t进行归并排序。然后将两个已排序子区间合并为一个有序区间。,void MSort(SeqList SR,SeqList TR,ints,int t)/将有序表 SR.rs.t有序归并排序到 TR.rs.t中 if(s=t)TR.rs=SR.rs;else m=(s+t)/2;MSort(SR,MR,s,m);MSort(SR,MR,m+1,t);merge(MR,TR,s,m,t),10-35,10.5 归并排序,算法分析每趟归并的时间复杂度为O(n),整个算法需2n趟。时间复杂度为O(nlog2n)。归并排序算法虽简单，但占用辅助空间大，实用性差。,10-36,10.6 基数排序,基数排序是一种无需进行关键字比较的新排序方法，其基本操作是“分配”和“收集”。基数排序原理基数排序是按组成关键字的各位的值进行分配和收集，与前面介绍的排序方法不同，它无需进行关键字之间的比较。设关键字有d 位，每位的取值范围为 r(称为基数)，则需要进行d 趟分配与收集，需要设立 r 个队列。例如，若每位是十进制数字，则需要设立10个队列，若每位由小写字母组成，则要设立26个队列。,10-37,10.6 基数排序,基数排序的步骤从关键字的低位开始进行第i趟(i=1,2,.d)分配即将单链表中的记录依次按关键字的第i位分配到相应编号的队列中；分配完毕后，将各队列的记录按队列编号顺序收集成一个单链表；上一趟形成的链队，作为下一趟的输入，重复，直到第d趟收集完毕，所得单链表已成为有序表。,10-38,10.6 基数排序,第二趟分配 109 589 008 269 184 505 930 063 278 083第二趟收集 505008109930063269278083184589第三趟分配 083 063 184 278 589 008 109 269 505 930 第三趟收集 008063083109184269278505589930,第一趟收集 930063083184505278008109589269,10-39,10.6 基数排序,基数排序的特点基数排序的基本操作是分配和收集，而不是关键字之间的比较；基数排序是稳定的，其时间复杂度为O(d(n+rd)，其中n是记录数，d是关键字的位数，r是关键字各位的值域；基数排序要进行d趟分配和收集,需r个队列。,10-40,10.7 各种内部排序方法的比较,排序方法选择主要考虑：待排序记录个数n记录本身的大小关键字的分布情况对排序稳定性要求,10-41,10.7 各种内部排序方法的比较,时间特性：时间复杂度为O(nlogn):快速、堆、归并排序快速最快，在n较大时，归并较堆更快时间复杂度为O(n2):插入、冒泡、选择排序插入最常用，尤其基本有序时，选择记录移动次数最少时间复杂度为O(n):基数排序当待排序记录有序时：插入和冒泡可达到O(n)，快速蜕化到O(n2)；选择、堆和归并排序的时间特性不随关键字分布而改变,10-42,10.7 各种内部排序方法的比较,空间特性：所有的简单排序和堆排序的空间复杂度均为O(1)；快速排序为O(logn);归并排序和基数排序所需辅助空间最多，其空间复杂度为O(n).稳定性：快速排序、希尔排序和堆排序是不稳定的;其他排序方法都是稳定的,10-43,10.7 各种内部排序方法的比较,排序方法比较,