数据结构Java版第3章--排序分析

《数据结构（Java版）》叶核亚《数据结构（Java版）》第1章绪论第2章线性表第3章排序第4章栈与队列第5章数组和广义表第6章树和二叉树第7章查找第8章图第9章综合应用设计第3章排序•3.1排序的基本概念•3.2插入排序•3.3交换排序•3.4选择排序•3.5归并排序《数据结构（Java版）》叶核亚3.1排序的基本概念1．数据序列数据序列（datalist）是待排序的数据元素的有限集合。2．关键字通常数据元素由多个数据项组成，以其中某个数据项作为排序依据，则该数据项称为关键字（key）。3．排序算法的稳定性在数据序列中，如果有两个数据元素ri和rj，它们的关键字ki等于kj，且在未排序时，ri位于rj之前。如果排序后，元素ri仍在rj之前，则称这样的排序算法是稳定的（stable），否则是不稳定的排序算法。《数据结构（Java版）》叶核亚4．内排序与外排序内排序：在待排序的数据序列中，数据元素个数较少，整个排序过程中所有的数据元素都可以保留在内存，则这样的排序称为内排序。外排序：待排序的数据元素非常多，以至于它们必须存储在磁盘等外部存储介质上，则这样的排序称为外排序。显然，外排序过程中需要多次访问外存。5．排序算法的性能评价排序算法的时间复杂度：指算法执行中的数据比较次数、数据移动次数与待排序数据序列的元素个数n之间的关系。排序算法的空间复杂度：指算法执行中，除待排序数据序列本身所占用的内存空间外，需要的附加内存空间与待排序数据序列的元素个数n之间的关系。《数据结构（Java版）》叶核亚3.2插入排序插入排序（insertionsort）的基本思想是：每趟将一个待排序的数据元素，按其关键字大小，插入到已排序的数据序列中，使得插入后的数据序列仍是已排序的，直到全部元素插入完毕。3.2.1直接插入排序3.2.2希尔排序《数据结构（Java版）》叶核亚3.2.1直接插入排序1．直接插入排序算法2．顺序存储结构线性表的直接插入排序518765432table(a)k=5，i=1，插入535(b)k=3，在子序列{5}中查找，i=1，{5}向后移动,插入3253(c)k=2，在{3，5}中查找，i=1，{3,5}向后移动,插入227543(e)k=7,在{2，3，4，5}中查找，i=5，插入7(f)k=1，在{2，3，4，5，7}中查找，i=1，{2,3,4,5,7}向后移动,插入11754322543(d)k=4，在{2，3，5}中查找，i=3，{5}向后移动,插入4序号iiiiii1234521图3.1直接插入排序算法描述《数据结构（Java版）》叶核亚【例3.1】顺序表的直接插入排序的算法实现与测试。importds_java.LinearList1;//顺序存储结构的线性表类publicclassInsertSort1extendsLinearList1//直接插入排序{publicInsertSort1(inttable[])//将table数组元素依次插入已排序顺序表{super(table.length);for(inti=0;itable.length;i++)insertdata(table[i]);}publicvoidinsertdata(intk)//插入k值{inti=search(k);//顺序查找System.out.print(k=+k+i=+i+);for(intj=this.length();j=i;j--)《数据结构（Java版）》叶核亚3．算法分析直接插入排序的平均比较次数为平均移动次数为直接插入排序的时间复杂度为O(n2)。直接插入排序算法是稳定的。ninnniC12241434121平均ninnniM1244)1(2平均《数据结构（Java版）》叶核亚4．链表的直接插入排序ppriordatanext∧1headq23∧(a)空表插入(c)中间插入(b)头插入q∧3∧3∧head∧1qheadrearheadrear∧1headq23∧(d)尾插入rearrear4∧图3.2双向链表的插入排序算法描述《数据结构（Java版）》叶核亚【例3.2】双向链表的直接插入排序importds_java.TwolinkNode;//双向链表的结点类importds_java.Twolink1;//双向链表类publicclassTwolink2extendsTwolink1//双向链表插入排序{protectedTwolinkNoderear;//引用链表最后一个结点Twolink2()//建立空链表{super();//head=nullrear=null;}Twolink2(intn)//n个随机值插入双向链表{inti=0,k;System.out.print(insert:);for(i=0;in;i++)《数据结构（Java版）》叶核亚3.2.2希尔排序图3.3希尔排序算法描述8561972318765432table87639521jj+jumpi(a)jump=4(b)jump=2,j=1,交换jj+jump27639581jj+jumpi(d)jump=2,j=4,交换123416543227639581jj+jumpi(c)jump=2,j=2,不交换,j=3,不交换27659381jj+jump18765432i(e)jump=2,j=5,交换27956381jj+jumpi(f)jump=2,j=3,交换27958361ji(g)jump=2,j=6,不交换j+jump19876532(h)jump=11654327序号《数据结构（Java版）》叶核亚希尔排序算法描述希尔排序算法共有三重循环最外层循环while语句控制增量jump，初值为数组长度n的一半，以后逐次减半（jump=jump/2），直至为1。中间循环for语句进行一轮相隔jump的元素进行比较、交换。最内层循环while语句，将第j个元素值this.get(j)与相隔jump的第j-jump个元素值this.get(j+jump)进行比较，如果两者是反序的，则执行swap(j,j+jump)交换两个值。重复往前与相隔jump的元素再比较、交换，j=j–jump，当this.get(j)this.get(j+jump)时，表示该元素this.get(j)已在这趟排序后的位置，不需交换，则退出最内层循环。《数据结构（Java版）》叶核亚希尔排序算法publicvoidshellsort()//对顺序表对象进行希尔排序{//数据元素已存储在table数组中inti,j,jump,n=this.length();jump=n/2;while(jump0)//控制增量{for(i=jump;i=n;i++)//一轮比较、交换{j=i-jump;while(j0)if(this.get(j)this.get(j+jump)){//与相隔jump的元素比较、交换swap(j,j+jump);//反序时，交换j=j-jump;//继续与前面的元素比较}《数据结构（Java版）》叶核亚3.3交换排序3.3.1冒泡排序3.3.2快速排序《数据结构（Java版）》叶核亚3.3.1冒泡排序1．冒泡排序算法publicvoidbubblesort(){inti,j,n=this.length();for(i=1;in;i++)//n-1趟排序{for(j=1;j=n-i;j++)//一轮比较、交换if(this.get(j)this.get(j+1))this.swap(j,j+1);//反序时，交换System.out.print(第+i+趟);this.output();}}2．算法分析时间复杂度为O(n2)，空间复杂度为O(1)。《数据结构（Java版）》叶核亚3．改进的冒泡排序publicvoidbubblesort(){inti=1,j,n=this.length(),index=1;booleanexchange=true;//是否交换的标记while(in&&exchange)//最多n-1趟排序{System.out.print(第+i+趟index=+index+n-i=+(n-i)+);exchange=false;//假定元素未交换j=index;//起始比较位置while(j=n-i)//一轮比较、交换{System.out.print(this.get(j)++this.get(j+1)+?);if(this.get(j)this.get(j+1)){this.swap(j,j+1);//反序时，交换《数据结构（Java版）》叶核亚改进的冒泡排序算法描述1567843218765432table(a)第1趟，i=1,从index到n-i+1的相邻位置元素比较、交换交换index交换交换18567432(b)第2趟，i=2,从index到n-i+1的相邻位置元素比较、交换交换index交换n-i+1n-i+118756432(c)第3趟，i=3，比较、交换交换indexn-i+118765432(d)第3趟，i=4，比较,没有交换，已排序indexn-i+1序号《数据结构（Java版）》叶核亚3.3.2快速排序图3.6快速排序算法描述5713842618765432table(a)vot=5，table[j]vot，不移动，j--ij17685423(i)i++，j--，分成两个子序列（left,j）与(i,right)ijrightleft57138426(b)vot=5，table[j]vot，将table[j]值赋给table[i]，i++ij17138426(c)vot=5，table[i]vot，将table[i]值赋给table[j]，j--ijrightleft17638426(d)vot=5，table[j]vot，将table[j]值赋给table[i]，i++ij17638423(e)vot=5，table[i]vot，i++ij17638423(f)vot=5，table[i]vot，i++ij17638423ij(g)vot=5，table[i]vot，将table[i]值赋给table[j]，j--17688423(h)i==j，将vot值赋给table[i]ij序号图3.6快速排序算法描述《数据结构（Java版）》叶核亚1．快速排序算法publicvoidquicksort(intleft,intright)//实现一趟快速排序{inti,j,n,vot;if(leftright)//左边界小于右边界，序列有效{i=left;j=right;vot=this.get(i);//第一个值作为基准值while(i!=j)//进行一轮比较{while(votthis.get(j)&&ij)j--;//从右向左寻找较小值if(ij){this.set(i,this.get(j));//较小值元素向左移动《数据结构（Java版）》叶核亚2．算法分析快速排序的平均比较次数为O(nlog2n)，时间复杂度为O(nlog2n)。由于快速排序是递归算法，系统调用时需要设立一个栈（stack）存放参数，最大递归调用层次数为。因此，算法的空间复杂度为O(nlog2n)。《数据结构（Java版）》叶核亚3.4选择排序1．顺序表的直接选择排序算法publicvoidselectsort(){inti,j,min,k,n=this.length();for(i=1;in;i++)//n-1趟排序{min=i;//记下本趟最小值位置for(j=i+1;j=n;j++)//一轮比较、交换if(get(j)get(min))min=j;//记下新的最小值位置if(min!=i)swap(i,min);//本趟最小值交换到左边System.out.print(min=+m