搜索
《数据结构（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