牛小飞《数据结构》7.1排序问题、插入排序和希尔排序

排序问题和插入排序,排序问题,插入排序,小结和作业,排序的定义,内部排序和外部排序,内部排序方法的分类,排序问题,稳定性,排序的定义,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的序列调整为“有序”的序列。,52,49,80,36,14,58,61,23,97,75,14,23,36,49,52,58,61,75,80,97,排序的定义,一般情况下，假设含n个记录的序列为R1,R2,，Rn其相应的关键字序列为K1,K2,，Kn,这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系：Kp1Kp2Kpn,按此固有关系将上式记录序列重新排列为Rp1,Rp2,，Rpn的操作称作排序。,排序的定义,关键字(key):数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据，称为关键字。也称为排序码。,排序的定义,为简单起见，假设排序例子中的数组只包含整数，当然程序也允许更一般的对象。被排序的对象属于Comparable类型。,排序方法的稳定性,如果在对象序列中有两个对象ri和rj,它们的排序码ki=kj,且在排序之前,对象ri排在rj前面。如果在排序之后,对象ri仍在对象rj的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的。,内部排序和外部排序,由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为：,1.内部排序：整个排序过程不需要访问外存便能完成。,2.外部排序：参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成。,内部排序方法的分类,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。,有序序列区,无序序列区,有序序列区,无序序列区,内部排序方法的分类,基于不同的“扩大”有序序列长度的方法，内部排序方法大致可分下列几种类型：,1.插入排序,2.交换排序,3.选择排序,4.归并排序,5.基数排序,内部排序方法,插入排序：将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。,各种排序方法的定义,交换排序：通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,选择排序：,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,各种排序方法的定义,归并排序：,通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。,基数排序：,是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。,各种排序方法的定义,插入排序,一趟插入排序的基本思想：,有序序列R0.i-1,Ri,无序序列Ri.n-1,有序序列R0.i,无序序列Ri+1.n-1,插入排序,一趟（onepass）插入排序的实现步骤：,3将Ri插入(复制)到Rj+1的位置上。,2将Rj+1.i-1中的所有记录均后移一个位置；,1在R0.i-1中查找Ri的插入位置，R0.jRi=0/从后往前找,直接插入排序,publicstaticvoidInsertionSort(AnyTypea)/直接插入排序inti,j;for(i=1;i=0,直接插入排序性能分析,实现内部排序的基本操作有两个：,2）“移动”记录。,1）“比较”序列中两个关键字的大小；,直接插入排序性能分析,2(n-1),关键字在记录序列中顺序有序,关键字在记录序列中逆序有序,O(n2),时间复杂度：,稳定性：,是一种稳定的排序方法,直接插入排序-练习,1、直接插入排序在最好情况下的时间复杂度为（）,A.O(logn)B.O(n)C.O(nlogn)D.O(n2),2、用直接插入排序法对下面四个序列进行排序（由小到大），元素比较次数最少的是（）,A.94,32,40,90,80,46,21,69,B.32,40,21,46,69,94,90,80,C.21,32,46,40,80,69,90,94,D.90,69,80,46,21,32,94,40,希尔排序,希尔排序(Shellsort)通过比较相距一定间隔的元素来工作；各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。故又称为缩小增量排序。,基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。,希尔排序,希尔排序使用一个增量序列(incrementsequence)h1,h2,ht在使用增量hk的一趟排序之后，对于每一个i，都有aiai+hk，即所有间隔(gap)hk的元素都被排序，此时称文件是hk排序的(hk-sorted)。,一趟hk排序的作用就是对hk个独立的子数组执行一次插入操作。,希尔排序,gap=h1=5,0123456789,65,97,76,13,27,49,55,04,49,38,第一趟,0123456789,49,55,04,49,38,65,97,76,13,27,希尔排序,gap=h2=3,第二趟,0123456789,49,55,04,49,38,65,97,76,13,27,0123456789,49,38,27,49,55,65,97,76,13,04,希尔排序,gap=h3=1,第三趟,0123456789,49,38,27,49,55,65,97,76,13,04,0123456789,27,38,49,49,55,65,97,76,04,13,希尔排序,算法描述举例,inth=5,3,1;,0123456789,38,65,97,76,13,27,49,55,04,49,38,65,97,76,13,27,49,55,04,49,第一趟,tmp=,13,27,49,55,04,gap=h0=5,希尔排序,算法描述举例,inth=5,3,1;,0123456789,27,49,55,04,49,38,65,97,76,13,27,04,38,55,第二趟,tmp=,gap=h1=3,04,38,j-gap,55,希尔排序,算法描述举例,inth=5,3,1;,0123456789,04,49,38,27,49,55,65,97,76,13,38,04,13,49,第三趟,tmp=,gap=h2=1,04,38,27,49,38,27,97,76,76,希尔排序,publicstaticvoidShellSort(AnyTypea,inth)/增量为h的希尔排序for(intk=0;kvoidShellInsert(AnyTypea,intgap)/一趟希尔排序intj;for(inti=gap;i=0/插入/for,希尔排序,算法分析：,增量序列可以有各种取法，但序列中最后1个值必须是1，序列中的值没有除1以外的公因子。增量序列的一个流行的选择是使用Shell建议的序列：ht=n/2和hk=hk+1/2。,不是稳定的算法,希尔增量复杂度是(n2)Hibbard增量复杂度是(n3/2),希尔排序,用希尔排序对数组98，36，-9，0，47，23，