数据结构Java版第3章 排序.ppt

《数据结构Java版第3章 排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、《数据结构（Java版）》叶核亚《数据结构（Java版）》第1章绪论第2章线性表第3章排序第4章栈与队列第5章数组和广义表第6章树和二叉树第7章查找第8章图第9章综合应用设计第3章排序3.1排序的基本概念3.2插入排序3.3交换排序3.4选择排序3.5归并排序3.1排序的基本概念1．数据序列数据序列（datalist）是待排序的数据元素的有限集合。2．关键字通常数据元素由多个数据项组成，以其中某个数据项作为排序依据，则该数据项称为关键字（key）。3．排序算法的稳定性在数据序列中，如果有两个数据元素ri和rj，它们的关键字ki等于kj，且在未排序时，ri位于rj之前。如

2、果排序后，元素ri仍在rj之前，则称这样的排序算法是稳定的（stable），否则是不稳定的排序算法。4．内排序与外排序内排序：在待排序的数据序列中，数据元素个数较少，整个排序过程中所有的数据元素都可以保留在内存，则这样的排序称为内排序。外排序：待排序的数据元素非常多，以至于它们必须存储在磁盘等外部存储介质上，则这样的排序称为外排序。显然，外排序过程中需要多次访问外存。5．排序算法的性能评价排序算法的时间复杂度：指算法执行中的数据比较次数、数据移动次数与待排序数据序列的元素个数n之间的关系。排序算法的空间复杂度：指算法执行中，除待排序数据序列本身所占用的内存空间外，需要的

3、附加内存空间与待排序数据序列的元素个数n之间的关系。3.2插入排序插入排序（insertionsort）的基本思想是：每趟将一个待排序的数据元素，按其关键字大小，插入到已排序的数据序列中，使得插入后的数据序列仍是已排序的，直到全部元素插入完毕。3.2.1直接插入排序3.2.2希尔排序3.2.1直接插入排序1．直接插入排序算法2．顺序存储结构线性表的直接插入排序图3.1直接插入排序算法描述【例3.1】顺序表的直接插入排序的算法实现与测试。数据结构（Java版）》叶核亚3．算法分析直接插入排序的平均比较次数为平均移动次数为直接插入排序的时间复杂度为O(n2)。直接插入排序算

4、法是稳定的。4．链表的直接插入排序图3.2双向链表的插入排序算法描述【例3.2】双向链表的直接插入排序数据结构（Java版）》叶核亚3.2.2希尔排序图3.3希尔排序算法描述希尔排序算法描述希尔排序算法共有三重循环最外层循环while语句控制增量jump，初值为数组长度n的一半，以后逐次减半（jump=jump/2），直至为1。中间循环for语句进行一轮相隔jump的元素进行比较、交换。最内层循环while语句，将第j个元素值this.get(j)与相隔jump的第j-jump个元素值this.get(j+jump)进行比较，如果两者是反序的，则执行swap(j,j+j

5、ump)交换两个值。重复往前与相隔jump的元素再比较、交换，j=j–jump，当this.get(j)>this.get(j+jump)时，表示该元素this.get(j)已在这趟排序后的位置，不需交换，则退出最内层循环。希尔排序算法数据结构（Java版）》叶核亚3.3交换排序3.3.1冒泡排序3.3.2快速排序3.3.1冒泡排序1．冒泡排序算法publicvoidbubblesort(){inti,j,n=this.length();for(i=1;i

6、>this.get(j+1))this.swap(j,j+1);//反序时，交换System.out.print("第"+i+"趟");this.output();}}2．算法分析时间复杂度为O(n2)，空间复杂度为O(1)。3．改进的冒泡排序数据结构（Java版）》叶核亚改进的冒泡排序算法描述3.3.2快速排序图3.6快速排序算法描述图3.6快速排序算法描述1．快速排序算法数据结构（Java版）》叶核亚2．算法分析快速排序的平均比较次数为O(nlog2n)，时间复杂度为O(nlog2n)。由于快速排序是递归算法，系统调用时需要设立一个栈（stack）存放参数，最大递归

7、调用层次数为。因此，算法的空间复杂度为O(nlog2n)。3.4选择排序1．顺序表的直接选择排序算法publicvoidselectsort(){inti,j,min,k,n=this.length();for(i=1;i