牛小飞《数据结构》7.1排序问题、插入排序和希尔排序.ppt
排序问题和插入排序,排序问题,插入排序,小结和作业,排序的定义,内部排序和外部排序,内部排序方法的分类,排序问题,稳定性,排序的定义,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的序列调整为“有序”的序列。,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,插入排序,一趟（one pass）插入排序的实现步骤：,3将Ri 插入(复制)到Rj+1的位置上。,2将Rj+1.i-1中的所有记录均后移 一个位置；,1在R0.i-1中查找Ri的插入位置，R0.j Ri Rj+1.i-1；,插入排序分类,1.直接插入排序7.2（基于顺序查找）,2.希尔排序7.4（基于逐趟缩小增量）,直接插入排序,基本操作：将一个记录插入到已经排好序的有序表中。,利用“顺序查找”实现“在R0.i-1中查找Ri的插入位置”,直接插入排序,算法实现要点：,从Ri-1起向前进行顺序查找，,R0,j,Ri,j=i-1,插入位置,tmp=Ri,直接插入排序,38,65,97,76,13,27,49,38,i=1:,49,38,49,65,97,76,13,27,38,65,i=2:,49,38,65,97,i=3:,49,38,65,97,49,65,97,76,13,27,38,76,i=4:,76,97,直接插入排序,49,65,76,97,13,27,38,49,65,76,97,13,27,38,13,i=5:,49,38,65,76,97,13,38,49,65,76,97,27,13,27,i=6:,49,38,65,76,97,27,直接插入排序,算法实现要点：,tmp=Ri;,循环结束表明Ri的插入位置为 j+1,for(j=i-1;j=0/从后往前找,直接插入排序,public static void InsertionSort(AnyType a)/直接插入排序 int i,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)通过比较相距一定间隔的元素来工作；各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。故又称为缩小增量排序。,基本思想：对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是，“跳跃式”的插入排序。,希尔排序,希尔排序使用一个增量序列(increment sequence)h1,h2,ht在使用增量hk的一趟排序之后，对于每一个i，都有aiai+hk，即所有间隔(gap)hk的元素都被排序，此时称文件是hk排序的(hk-sorted)。,一趟hk排序的作用就是对hk个独立的子数组执行一次插入操作。,希尔排序,gap=h1=5,0 1 2 3 4 5 6 7 8 9,65,97,76,13,27,49,55,04,49,38,第一趟,0 1 2 3 4 5 6 7 8 9,49,55,04,49,38,65,97,76,13,27,希尔排序,gap=h2=3,第二趟,0 1 2 3 4 5 6 7 8 9,49,55,04,49,38,65,97,76,13,27,0 1 2 3 4 5 6 7 8 9,49,38,27,49,55,65,97,76,13,04,希尔排序,gap=h3=1,第三趟,0 1 2 3 4 5 6 7 8 9,49,38,27,49,55,65,97,76,13,04,0 1 2 3 4 5 6 7 8 9,27,38,49,49,55,65,97,76,04,13,希尔排序,算法描述举例,int h=5,3,1;,0 1 2 3 4 5 6 7 8 9,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,希尔排序,算法描述举例,int h=5,3,1;,0 1 2 3 4 5 6 7 8 9,27,49,55,04,49,38,65,97,76,13,27,04,38,55,第二趟,tmp=,gap=h1=3,04,38,j-gap,55,希尔排序,算法描述举例,int h=5,3,1;,0 1 2 3 4 5 6 7 8 9,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,希尔排序,public static void ShellSort(AnyType a,int h)/增量为h 的希尔排序 for(int k=0;kh.length;+k)ShellInsert(a,hk);/一趟增量为hk的插入排序,希尔排序,private static void ShellInsert(AnyType a,int gap)/一趟希尔排序 int j;for(int i=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，1，8，10，7进行排序，给出的步长依次是4，2，1，则排序需 趟，写出第一趟结束后，数组中数据的排列次序,小结和作业,1.有关排序的基础知识,1定义,2分类,3稳定性和存储方式,4排序算法的评价,2.直接插入排序,1基本思想,2实例模拟,3算法描述,4算法的复杂度,3.希尔排序,作业：p212,7.1 7.4,
