第8章-排序要点.ppt

第八章排序，DS，应用实践，插入排序，基数排序，合并排序，交换排序，选择排序，HotTip，本章学习的要点，主要基于各种排序方法的实现的原则及其主要操作(“关键字间的比较”和“记录的移动学习要把握各种排序方法实现的要点，切实把握各种排序过程的排序特征。8.1基本概念、排序定义：将数据元素(或记录)的任何序列按关键字顺序重新排序。 关键字：数据元素中的数据项。 内部排序：将要排序的记录存储在计算机随机存储器中的排序过程。 外部排序：因为要排序的记录数量很多，所以内存不能一次存储所有记录，需要在排序过程中进行外部访问。 假设49385976132749、132738449657697、132738449657697 :方法1 :方法2 :原始序列：Ki=Kj(ij )，Ri在排序前的序列中比Rj领先(即，iRi-1停止比较r I r I-1 ) l-r 0=l-r I ； 设置哨兵for (j=I-1； L-rjL-r0； j-)L-rj 1=L-rj； L-rj 1=L-r0； ，例如493859761327，i=2(49)385959761327，i=1()，49，38，R0，38，例如493859761327，i=2(4938)6565657761327，I=3I=5(3 i=1()，i=7(13273849657697 )，27，97，76，R0，76，65，97，视频服务器(sqlist * l ) inti，j； for(i=2； ilength； I ) if (l-r I r I-1 ) l-r 0=l-r I ； 设置哨兵for (j=I-1； L-rjL-r0； j-)L-rj 1=L-rj； L-rj 1=L-r0； ，算法8.1直接插入排序，直接插入排序算法很容易实现，只需要一个辅助空间来存储要插入的记录(在c语言中利用数组中的0个单元格)和两个int类型变量。 如果要排序的记录较少，则排序速度较快，但是如果要排序的记录数量较多，则大量的比较和移动操作会降低直接插入排序算法的效率，但是，如果要排序的数据元素基本上已排序，则在排序期间直接插入的移动次数会显着减少，效率会降低。 插入排序是一种稳定的排序方法。 另外，在排名对象记录为正序 (即，记录按关键字从小到大的顺序排列)的情况下，必要的关键字比较和记录移动的次数最少，相反，在排名对象记录为逆顺序 (即，记录按关键字从大到小的顺序排列)的情况下另外，如果排序对象的序列是随机的状态，则可以把最坏和最佳状况的平均值用作插入排序的时间性能的尺度。 通常，直接插入排序的时间复杂度为O(n2 )。 希尔排序(ShellSort )也被称为“缩小增量排序”(DiminishingIncrementSort )的基本思想。 首先，将排名对象记录整体分割为几个子序列进行直接插入排序，一次直接插入排序整个记录，直到序列整体的记录成为“基本秩序”。8.2.3希尔排名，具体的步骤假定排名的记录为n个，首先比较取整数dR2后交换的第二条记录和第三条记录，依次类推，直到第n-1条记录和第n条记录比较为止，为止第次巴布结果，关键字最大的记录被放在最后一条记录上，第一条n-1条记录被第二次冒泡，结果，关键字第二条记录被放在第n-1条记录上，直到“第一次排序中不执行交换记录的操作”解：9、5、5、9、4、4、5、5、12、4、12、5、4、9、4、5、5、5、voidbubbblesortc(sqlist*l)inti，j for(i=1； ilength； i )for(j=L-length-1； j=i； j-)if(L-rjL-rj 1)swap(L，j，j 1)； /j和j 1的值互换，voidbubbblesortc (sqlist * l ) inti，j； intflag=TRUE； for(i=1； ilength/有数据交换、持续循环、算法评价时间复杂度最好的情况(正序)比较次数： n-1移动次数： 0，0， 12345，最坏情况(逆序)比较次数：移动次数：空间复杂度： S(n)=O(1)，T(n)=O(n 泡沫排序时间复杂度的分析：最佳情况下，即排序表本身有秩序，时间复杂度为O(n )。 在最坏的情况下，即排序等待表为逆序的情况下，需要比较次数，移动等级的记录。 因此，总的时间复杂性是O(n2 )。8.3.2快速排序(分割交换排序)的基本思想：以现在的无序区R1k中的任一个记录作为比较的“基准”，以该基准将现在的无序区分为左右小的无序区R1i-1和Ri 1k，标准在Ri中。 左侧无序子部分中记录的关键字必须小于或等于标准，右侧无序子部分中记录的关键字必须大于或等于标准。8.3.2快速排序(分割交换排序)排序过程：将排序等待列设置为：Rs，Rs 1，Rt，附加2个指针low和high，基准(旋转透视)记录tp=任意序列元素的初始季节low=s，high while (lowr high =pivot key ) high-； swap(L，low，high ) while (lowr low r min l-r j ) min=j； PS (PS！=最小)交换(l，I， min) ，算法评价时间复杂度记录移动次数，空间复杂度： S(n)=O(1)，T(n)=O(n )，1357911 (秩序)，7911531 (正反顺序)，直接选择排序不稳定，例如221，最佳情况： 0:最坏情况：3(n ) 堆栈的定义： n个要素的数组k1，k2，kn，并且仅在满足以下关系的情况下称为堆栈。 或者，8.4.2叠加排名，例如96、83、27、38、11、9，当对应于该阵列的一维阵列被视为完全二叉树的顺序存储结构时，堆的意思是完全二叉树中的所有非终端节点的值不大于其左右孩子的节点的值(因此，山顶要素一定是序列的最小(大)值。、小根山的萝卜山、(a )小根山的逻辑结构(b )小根山的存储结构、(a )萝卜山的逻辑结构(b )萝卜山的存储结构、堆叠顺序：将无序的顺序设为一个山，输出得到关键字最小(或最大)的记录的炉顶的最小(大)值后，剩下的n-1个元素n个元素的下一个能得到小值的反复执行，得到有序的序列，该过程要按累积顺序解决的两个问题：如何从无序的序列中累积？ 如何在输出堆栈顶部的元素后，调整剩馀的元素使其成为新的堆栈？ 第一个问题解决方法：从无序序列的第n/2个要素(即，与该无序序列对应的完全二叉树的最后的非终止节点)到第一个要素，反复进行选择，例如，包含8个要素的无序序序列(49、38、65、97、76、13、27、50 )、 第二个问题解决方法筛选方法：输出堆栈顶部的要素后，替换堆栈的最后的要素，然后将根节点的值与左、右侧的子树的根节点的值进行比较，反复进行与中小者交换的操作，直到叶的节点为止，得到新的山，从山顶开始例如，(1)在从无序到有秩序的筛选过程中实现voidHeapAdjust(SqList*L，ints，ints )的temp=L-rs； for(j=2*s； PS PS PS；AS； PS (时间=l-r j )中断； L-rs=L-rj； s=j； L-rs=temp； ，(2)堆叠顺序的过程voidHeapSort(SqList*L)inti； for(i=L-length/2； i0； I- ) heap调整(l，I，L-length) for(i=L-length； i1； I- ) 交换(l，1，I )； HeapAdjust(L，1，i-1) ，时间复杂度：最坏的情况T(n)=O(nlogn )空间复杂度： S(n)=O(1 可以认为初始序列(称为-2-合并排名)包含n个记录，具有n个顺序的子序列，每个子序列的长度为一个或两个，得到n/2个长度为2或1的规则子序列，并进一步合并两个，以此方式重复，直到得到长度为n的规则子序列一次合并后： 3849，6597，27，两次合并后： 38496597，132776； 三次合并后： 13273849657697，j 1，i 1，两个规则表SRi.m和SRm 1.n，voidM