数据结构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

1 / 32
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功