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

《数据结构（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之前。如果排序后，元素ri仍在rj之前，则称这样的排序算法是稳定的（stable），否则是不稳定的排序算法。 4．内排序与外排序 内排序：在待排序的数据序列中，数据元素个数较少，整个排序过程中所有的数据元素都可以保留在内存，则这样的排序称为内排序。 外排序：待排序的数据元素非常多，以至于它们必须存储在磁盘等外部存储介质上，则这样的排序称为外排序。显然，外排序过程中需要多次访问外存。 5．排序算法的性能评价 排序算法的时间复杂度：指算法执行中的数据比较次数、数据移动次数与待排序数据序列的元素个数n之间的关系。 排序算法的空间复杂度：指算法执行中，除待排序数据序列本身所占用的内存空间外，需要的附加内存空间与待排序数据序列的元素个数n之间的关系。 3.2 插入排序 插入排序（insertion sort）的基本思想是：每趟将一个待排序的数据元素，按其关键字大小，插入到已排序的数据序列中，使得插入后的数据序列仍是已排序的，直到全部元素插入完毕。 3.2.1 直接插入排序 3.2.2 希尔排序 3.2.1 直接插入排序 1．直接插入排序算法 2．顺序存储结构线性表的直接插入排序 【例3.1】 顺序表的直接插入排序的算法实现与测试。 3．算法分析 直接插入排序的平均比较次数为 平均移动次数为 直接插入排序的时间复杂度为O(n2)。 直接插入排序算法是稳定的。 4．链表的直接插入排序 【例3.2】 双向链表的直接插入排序 3.2.2 希尔排序 希尔排序算法描述 希尔排序算法共有三重循环 最外层循环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)已在这趟排序后的位置，不需交换，则退出最内层循环。 希尔排序算法 3.3 交换排序 3.3.1 冒泡排序 3.3.2 快速排序 3.3.1 冒泡排序 1．冒泡排序算法 public void bubblesort() { int i,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) 。 3．改进的冒泡排序 改进的冒泡排序算法描述 3.3.2 快速排序 1．快速排序算法 2．算法分析 快速排序的平均比较次数为O(nlog2n)，时间复杂度为O(nlog2n)。 由于快速排序是递归算法，系统调用时需要设立一个栈（stack）存放参数，最大递归调用层次数为。因此，算法的空间复杂度为O(nlog2n)。 3.4 选择排序 1．顺序表的直接选择排序算法 public void selectsort() { int i,j,min,k,n = this.length(); for(i=1;i