数据结构Chap10 排序.ppt

CSU数据结构 陈淑红中南大学中南大学中南大学信息院计科系中南大学信息院计科系主讲人：王国军主讲人：王国军http:/ 内部排序内部排序 提提 纲纲 10.1 概述 10.2 插入排序 10.3 快速排序 10.4 选择排序 10.5 归并排序 10.6 基数排序 10.7 各种内部排序方法的比较讨论排序定义排序定义将一组数据元素（或记录）的任意序列，重新排列成一个按关键字有序排列（升序或降序）的序列。10.1 10.1 概述概述排序是计算机程序设计中的一种重要运算，是计算机处理数据时一种频繁要做的工作。关键字将随着用户的要求不同而不同。如：人事档案文件可按年龄、工资或文化水平进行排序，从而获得不同的有序文件。按待排序记录所在位置按待排序记录所在位置内部排序：内部排序：待排序记录存放在内存中进行的排序外部排序：外部排序：待排序记录的数量很大，以至于内存一次不能容纳全部记录，在排序过程中需对外存进行访问的排序排序分类排序分类插入排序：插入排序：直接插入排序、折半插入排序、希尔排序交换排序：交换排序：冒泡排序、快速排序选择排序：选择排序：简单选择排序、堆排序归并排序：归并排序：2-路归并排序基数排序基数排序按排序依据原则按排序依据原则简单的排序方法：简单的排序方法：T(n)=O(n)先进的排序方法：先进的排序方法：T(n)=O(nlogn)基数排序：基数排序：T(n)=O(dn)按排序所需工作量按排序所需工作量n为记录的个数，为记录的个数，d为关键字的位数为关键字的位数排序基本操作排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置评价一个排序方法好坏的标准评价一个排序方法好坏的标准排序所需比较关键字的次数排序所需移动记录的次数排序过程中所需的辅助空间的大小算法本身的复杂程度少少少少小小插入排序的准则：插入排序的准则：在有序序列中插入新的记录以达到扩大有序区的长度的目的。直接插入排序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。10.2 10.2 插入排序插入排序例例1 149 38 65 97 76 13 27i=2 38 (38 49)65 97 76 13 27i=3 65 (38 49 65)97 76 13 27i=4 97 (38 49 65 97)76 13 27i=5 76 (38 49 65 76 97)13 27i=6 13 (13 38 49 65 76 97)27i=1 ()i=7 (13 38 49 65 76 97)2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：排序结果：监视哨L.r0void InsertSort(SqList&L)/对顺序表L作直接插入排序 for(i=2;i=L.length;+i)if(L.ri.key L.ri-1.key)/将 L.ri 插入有序子表L.r0=L.ri;L.ri=L.ri-1;for(j=i-2;L.r0.key L.rj.key;-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置/if/InsertSort算法描述算法描述时间复杂度时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：0若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：T(nT(n)=O(n)=O(n)算法评价算法评价若待排序记录是随机的，取上述最大最小的平均值 关键字比较次数：记录移动次数：空间复杂度：空间复杂度：S(n)=O(1)排序过程：排序过程：用折半查找方法确定插入位置的排序例例2：i=1 (30)13 70 85 39 42 6 20i=2 13 (13 30)70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85)20.i=8 20 (6 13 30 39 42 70 85)20lhmi=8 20 (6 13 30 39 42 70 85)20lhmi=8 20 (6 13 30 39 42 70 85)20lhm i=8 20 (6 13 30 39 42 70 85)20lhi=8 20 (6 13 20 30 39 42 70 85)折半插入排序折半插入排序算法描述算法描述void BInsertSort(SqList&L)/对顺序表L作折半插入排序for(i=2;i=L.length;+i)L.r0=L.ri;/将L.ri暂存到L.r0low=1;high=i-1;while(low=high)/在rlow.high中折半查找有序插入的位置 m=(low+high)/2;/折半 if(L.r0.key=low;-j)L.rj+1=L.rj;/记录后移L.rhigh+1=L.r0;/插入/BInsertSort算法评价算法评价T(nT(n)=O(n)=O(n)时间复杂度：时间复杂度：S(n)=O(1)仅减少了关键字的比较次数,而记录的移动次数不变，所以时间复杂度仍然为空间复杂度：空间复杂度：希尔排序希尔排序(缩小增量法缩小增量法)排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d20)for(i=d;i=0&Rj.keyRj+d.key)temp=Rj;/*Rj与Rj+d交换*/Rj=Rj+d;Rj+d=temp;j=j-d;d=d/2;/*递减增量d*/由于没有负数的下标，在dk1时需对j循环中以防出界另作j0的判别，即L.r0 不再起到监视哨的作用，而仅仅作为一个暂存记录的空间。算法描述算法描述2 2void ShellInsert(SqList&L，int dk)/对顺序表序表L作一趟增量作一趟增量为dk的希的希尔排序排序 for(i=dk+1;i=L.length;+i)if(L.ri.key 0&L.r0.key L.rj.key;j-=dk)L.rj+dk=L.rj;/记录后移后移L.rj+dk=L.r0;/插入到正确位置插入到正确位置/if/ShellInsertvoid ShellSort(SqList&L,int dlta,int t)/按增量序列按增量序列 dlta0.t-1 对顺序表序表L作希作希尔排序排序for(k=0;k1&change;-i)change=FALSE;for(j=1;j L.rj+1.key)L.rjL.rj+1;change=TRUE;/for i/BubbleSort算法描述算法描述最好情况（正序）比较次数：n-1 移动次数：0最坏情况（逆序）比较次数：移动次数：算法评价算法评价T(nT(n)=O(n)=O(n)时间复杂度：时间复杂度：S(n)=O(1)空间复杂度：空间复杂度：基本思想：基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。排序过程：排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs,x=rp.key快速排序快速排序 初始时令i=s,j=t 首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换 再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换 重复上述两步，直至i=j为止 再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。初始关键字：初始关键字：49 38 65 97 76 13 27 50 ijX=49ji 完成一趟排序：完成一趟排序：(27 38 13)49 (76 97 65 50)第二趟排序：第二趟排序：(13)27 (38)49 (76 97 65 50)快速排序结束：快速排序结束：13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij分别进行快速排序：分别进行快速排序：第三趟排序：第三趟排序：(13)27 (38)49 (50 65)76 (97)例例6 6：void QuickSort(RecType R,int s,int t)/*对对Rs至至Rt的元素进行快速排序的元素进行快速排序*/int i=s,j=t;RecType temp;if(si&Rj.keytemp.key)j-;if(ij)/*表示找到这样的表示找到这样的Rj,Ri、Rj交换交换*/Ri=Rj;i+;while(ij&Ri.keytemp.key)i+;if(ij)/*表示找到这样的表示找到这样的Ri,Ri、Rj交换交换*/Rj=Ri;j-;Ri=temp;QuickSort(R,s,i-1);/*对左区间递归排序对左区间递归排序*/QuickSort(R,i+1,t);/*对右区间递归排序对右区间递归排序*/划划分分算法描述算法描述2 2void QSort(RcdType R,int s,int t)/对记录序列 Rs.t 进行快速排序if(s t)/长度大于1pivotloc=Partition(R,s,t);/对 Rs.t 进行一趟快排，并返回枢轴位置QSort(R,s,pivotloc-1);/对低子序列递归进行排序QSort(R,pivotloc+1,t);/对高子序列递归进行排序/if/QSortvoid QuickSort(SqList&L)/对顺序表 L 进行快速排序QSort(L.r,1,L.length);/QuickSortint Partition(RcdType R,int low,int high)/对记录子序列 Rlow.high 进行一趟快速排序，并返回枢轴记录/所在位置，使得在它之前的记录的关键字均不大于它的关键字，/而在它之后的记录的关键字均不小于它的关键字R0=Rlow;/将枢轴记录移至数组的闲置分量pivotkey=Rlow.key;/枢轴记录关键字while(lowhigh)/从表的两端交替地向中间扫描while(low=pivotkey)-high;Rlow+=Rhigh;/将比枢轴记录小的记录移到低端while(lowhigh&Rlow.key=pivotkey)+low;Rhigh-=Rlow;/将比枢轴记录大的记录移到高端/whileRlow=R0;/枢轴记录移到正确位置return low;/返回枢轴位置/Partition算法评价算法评价T(nT(n)=O(n)=O(n)时间复杂度：时间复杂度：最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n)为避免出现枢轴记录关键字为最大或最小的情况，通常进行的快速排序采用三者取中的改进方案，即以 Rs、Rt 和 R(s+t)/2 三者中关键字介于中值者为枢轴。只要将它和 Rs 互换，一次划分的算法仍不变。可以证明，快速排序的平均时间复杂度为O(nlogn)，并且在所有平均时间复杂度为O(nlogn)的算法中它是最快的。在三者取中的前提下，对随机的关键字序列，快速排序是目前被认为是最好的排序方法，如果借用冒泡排序中设置记录“交换与否”的布尔变量的作法，快速排序也适用于已经有序的记录序列。最坏情况：一般情况：S(n)=O(n)空间复杂度：空间复杂度：需栈空间以实现递归S(n)=O(log2n)基本思想基本思想：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子表的最后，直到全部记录排序完毕。11.4 11.4 选择排序选择排序两种交换排序两种交换排序:(1)直接选择排序(或称简单选择排序)(2)堆排序排序过程排序过程 首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换；再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换；重复上述操作，共进行n-1趟排序后，排序结束。简单选择排序简单选择排序void SelectSort(SqList&L)/对顺序表L作简单选择排序for(i=1;iL.length;+i)/选择第 i 小的记录，并交换到位k=i;for(j=i+1;j=L.length;j+)if(L.rj.key L.rk.key)k=j;/在L.ri.L.length中选择关键字最小的记录if(i!=k)L.rk L.ri;/与第 i 个记录互换/for/SelectSort算法描述算法描述 选择排序是否也和插入排序或冒泡排序相类似，在对正序和逆序的待排序列进行排序时，所需进行的比较和移动 次数有很大差别？无论待排序列处于什么状态，选择排序所需进行的“比较”次数都相同，为而移动次数在待排序列为正序时达最小为0，在逆序时达最大为3(n-1)。例例1 1：初始：初始：49 38 65 97 76 13 27 kjjjjjjkki=11349一趟：一趟：13 38 65 97 76 49 27 i=2kkjjjjj2738二趟：二趟：13 27 65 97 76 49 38 三趟：三趟：13 27 38 97 76 49 65 四趟：四趟：13 27 38 49 76 97 65 五趟：五趟：13 27 38 49 65 97 76 六趟：六趟：13 27 38 49 65 76 97 排序结束：排序结束：13 27 38 49 65 76 97记录移动次数：最好情况：0 最坏情况：3(n-1)比较次数：总时间复杂度：算法评价算法评价T(nT(n)=O(n)=O(n)时间复杂度：时间复杂度：S(n)=O(1)空间复杂度：空间复杂度：堆的定义：堆的定义：n个元素的序列(k1,k2,kn)，当且仅当满足下列关系时，称之为堆。或或(i=1,2,.n/2)ki k2iki k2i+1ki k2iki k2i+1例例2 2：（9696，8383，2727，3838，1111，9 9）即堆是一个具有这样性质的完全二叉树：每个非终端结点（记录）的关键字大于等于（或小于等于）其孩子结点的关键字。969627279 91111383883831 12 23 34 45 56 6堆排序堆排序例例3 3：（：（1313，3838，2727，5050，7676，6565，4949，9797）13132727383849496565767650509797 堆顶元素（完全二叉树的根）必为序列中堆顶元素（完全二叉树的根）必为序列中n n个元个元素的最小值或最大值素的最小值或最大值 堆中任何一个结点的非空左右子树都是一个堆堆中任何一个结点的非空左右子树都是一个堆 根结点到任一个叶结点的每条路径上的结点值根结点到任一个叶结点的每条路径上的结点值（关键字）都递减有序（或递增有序）（关键字）都递减有序（或递增有序）例例2 2：（9696，8383，2727，3838，1111，9 9）969627279 91111383883831 12 23 34 45 56 6大顶大顶堆堆小顶堆小顶堆 堆排序：堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（或最大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫堆排序。方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。堆排序需解决的两个问题：堆排序需解决的两个问题：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？第二个问题解决方法第二个问题解决方法筛选筛选例例4 4：13273849657650979727384965765013输出：输出：132749389765765013输出：输出：139749382765765013输出：输出：13 273849502765769713输出：输出：13 276549502738769713输出：输出：13 27 384965502738769713输出：输出：13 27 387665502738499713输出：输出：13 27 38 495065762738499713输出：输出：13 27 38 499765762738495013输出：输出：13 27 38 49 506597762738495013输出：输出：13 27 38 49 509765762738495013输出：输出：13 27 38 49 50 657665972738495013输出：输出：13 27 38 49 50 659765762738495013输出：输出：13 27 38 49 50 65 769765762738495013输出：输出：13 27 38 49 50 65 76 97算法描述算法描述void HeapAdjust(SqList&H,int s,int m)/已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，/本函数依据关键字的大小对H.rs进行调整，使H.rs.m成为一/个大顶堆（对其中记录的关键字而言）H.r0=H.rs;/暂存根结点的记录for(j=2*s;j=m;j*=2)/沿关键字较大的孩子结点向下筛选if(jm&H.rj.key=H.rj.key)break;/不需要调整，跳出循环H.rs=H.rj;s=j;/将大关键字记录往上调/forH.rs=H.r0;/回移筛选下来的记录/HeapAdjust方法：对待排序的记录，建成相应的完全二叉树从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选第一个问题解决方法第一个问题解决方法含含8个元素的无序序列（个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097例例5 5算法描述算法描述void HeapSort(SqList&H)/对顺序表H进行堆排序for(i=H.length/2;i0;-i)/将 H.r1.H.length 建成大顶堆HeapAdjust(H,i,H.length);H.r1 H.rH.length;/互换堆顶和堆底的记录for(i=H.length-1;i1;-i)HeapAdjust(H,1,i);/从根开始调整，将 H.r1.i 重新调整为大顶堆H.r1 H.ri;/互换堆顶和当前的堆底，使已有序的记录沉积在底部/for/HeapSort最坏情况下：算法评价算法评价T(n)=O(nlogn)时间复杂度：时间复杂度：S(n)=O(1)空间复杂度：空间复杂度：排序过程设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1两两合并，得到n/2个长度为2或1的有序子序列再两两合并，如此重复，直至得到一个长度为n的有序序列为止10.5 10.5 归并排序归并排序归并归并将两个或两个以上的有序表组合成一个新的有序表，叫归并。2-路归并排序：路归并排序：例例1 1初始关键字：初始关键字：49 38 65 97 76 13 27一趟归并后：一趟归并后：38 49 65 97 13 76 27二趟归并后：二趟归并后：38 49 65 97 13 27 76三趟归并后：三趟归并后：13 27 38 49 65 76 97void Merge(RcdType SR,RcdType TR,int i,int m,int n)/将有序的SR i.m 和SR m+1.n 归并为有序的TR i.n for(j=m+1,k=i;i=m&j=n;+k)/将SR中记录按关键字从小到大地复制到TR中 /K用来指示新表TR的当前元素下标if(SRi.key=SRj.key)TRk=SRi+;else TRk=SRj+;while(i=m)TRk+=SRi+;/将剩余的 SRi.m 复制到TRwhile(j=n)TRk+=SRj+;/将剩余的 SRj.n 复制到TR/Merge算法描述算法描述void MSort(RcdType SR,RcdType TR1,int s,int t)/对SRs.t进行归并排序，排序后的记录存入TR1s.tif(s=t)TR1s=SRs;else m=(s+t)/2;/将 SRs.t 平分为 SRs.m 和 SRm+1.tMsort(SR,TR2,s,m);/递归地将 SRs.m 归并为有序的 TR2s.mMsort(SR,TR2,m+1,t);/递归地将SRm+1.t归并为有序的TR2m+1.tMerge(TR2,TR1,s,m,t);/将TR2s.m和TR2m+1.t 归并到 TR1s.t/else/MSortvoid MergeSort(SqList&L)/对顺序表L作2-路归并排序MSort(L.r,L.r,1,L.length);/MergeSort算法评价算法评价时间复杂度：时间复杂度：T(nT(n)=O(nlog)=O(nlog2 2n)n)空间复杂度：空间复杂度：S(nS(n)=)=O(nO(n)10.6 10.6 基数排序基数排序 前面讨论的排序主要是通过关键字之间的比较和移动记录来实现，而基数排序不需进行关键字之间的比较，它是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。多关键字排序多关键字排序例1：对52 张扑克牌按以下次序排序：2 3 A 2 3 A 2 3 A 2 3 A两个关键字：花色（）面值（23A）并且“花色”地位高于“面值”。定义：定义：假设有n个记录的序列R=R1,R2,Rn，且每个记录Ri中含有d个关键字(Ki0,Ki1,Kid-1)，则称序列 R对关键字(K0,K1,Kd-1)有序是指：对于序列R中任意两个记录Ri和Rj(1=ij=n)都满足下列有序关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)其中，K0称为最主位关键字，Kd-1称为最次位关键字。最高位优先法（最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干个子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列。最低位优先法最低位优先法(LSD)：从最低位关键字kd进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k1排序后，便成为一个有序序列。多关键字排序方法多关键字排序方法MSD与与LSD的的不同特点不同特点 按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序。按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序。基数排序：基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法。链式基数排序：链式基数排序：用链表作存储结构的基数排序。链式基数排序链式基数排序设置10个队列，fi和ei分别为第i个队列的头指针和尾指针。第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配分配至10个链队列中，每个队列记录的关键字的个位相同。第一趟收集收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表。重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列。链式基数排序步骤：链式基数排序步骤：例例2 2初始状态：初始状态：278109063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配930063083184505278008109589269一趟收集：一趟收集：505008109930063269278083184589二趟收集：二趟收集：083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二二趟趟分分配配008109278930063083184505278008109589269一趟收集：一趟收集：008008063063083083109109184184269269278278505505589589930930三趟收集：三趟收集：109109008008184184930930e0e0e1e1e2e2e3e3e4e4e5e5e6e6e7e7e8e8e9e9f0f0f1f1f2f2f3f3f4f4f5f5f6f6f7f7f8f8f9f9三三趟趟分分配配063063083083269269278278505505589589505505008008109109930930063063269269278278083083184184589589二趟收集：二趟收集：算法评价算法评价时间复杂度：时间复杂度：分配：T(n)=O(n)收集：T(n)=O(rd)总时间复杂度：T(n)=O(d(n+rd)其中：n记录数 d关键字数 rd关键字取值范围 空间复杂度：空间复杂度：S(n)=2rd个队列指针+n个指针域空间基数10.7 10.7 各种内部排序方法的比较讨论各种内部排序方法的比较讨论直接插入排序、直接选择排序和冒泡排序是三种简单的排序方法，它们的时间复杂度均为O（n2），空间复杂度均为O（1）；但由于它们的时间复杂度的系数不同，所以直接插入排序快于直接选择排序，而直接选择排序又快于冒泡排序。堆排序、快速排序和归并排序是三种较快的排序方法，它们的时间复杂度均为O（nlogn），但平均速度最快的是快速排序；它们的空间复杂度均为O（1）、O（logn）和O（n）。本章讨论的排序算法多数是在顺序存储结构上实现的，因此在排序过程中需进行大量的记录移动。当n很大时，很耗费时间，此时宜采用静态链表作存储结构。如表插入排序、链式基数排序，以修改指针代替移动记录。快速排序和堆排序无法实现链式排序。若Ki=Kj，排序前ij，排序后仍保持ij，此排序属稳定排序。一般来说，排序过程中的“比较”是在“相邻两个记录关键字”间进行的排序方法是稳定的。基数排序，以及时间复杂度为O（n2）的简单排序方法是稳定的。快速排序，堆排序，希尔排序等时间性能较好的排序方法都是不稳定的。综合题十 作作 业业