《数据结构Java版第3章排序.》由会员分享，可在线阅读，更多相关《数据结构Java版第3章排序.（32页珍藏版）》请在金锄头文库上搜索。
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，它们的关键 字k
2、i等于kj，且在未排序时，ri位于rj之前。如果排序后 ，元素ri仍在rj之前，则称这样的排序算法是稳定的（ stable），否则是不稳定的排序算法。 数据结构（Java版）叶核亚 4内排序与外排序 n内排序：在待排序的数据序列中，数据元素个数较少，整个 排序过程中所有的数据元素都可以保留在内存，则这样的排 序称为内排序。 n外排序：待排序的数据元素非常多，以至于它们必须存储在 磁盘等外部存储介质上，则这样的排序称为外排序。显然， 外排序过程中需要多次访问外存。 5排序算法的性能评价 n排序算法的时间复杂度：指算法执行中的数据比较次数、数 据移动次数与待排序数据序列的元素个数n之间的关系。 n
3、排序算法的空间复杂度：指算法执行中，除待排序数据序列 本身所占用的内存空间外，需要的附加内存空间与待排序数 据序列的元素个数n之间的关系。 数据结构（Java版）叶核亚 3.2 插入排序 n插入排序（insertion sort）的基本思想 是：每趟将一个待排序的数据元素，按 其关键字大小，插入到已排序的数据序 列中，使得插入后的数据序列仍是已排 序的，直到全部元素插入完毕。 n3.2.1 直接插入排序 n3.2.2 希尔排序 数据结构（Java版）叶核亚 3.2.1 直接插入排序 1直接插入排序算法 2顺序存储结构线性表 的直接插入排序 图3.1 直接插入排序算法描述 数据结构（Java版）
4、叶核亚 【例3.1】 顺序表的直接插入排序 的算法实现与测试。 数据结构（Java版）叶核亚 3算法分析 n直接插入排序的平均比较次数为 n平均移动次数为 n直接插入排序的时间复杂度为O(n2)。 n直接插入排序算法是稳定的。 数据结构（Java版）叶核亚 4链表的直接插入排序 图3.2 双向链表的插入排序算法描述 数据结构（Java版）叶核亚 【例3.2】 双向链表的直接插入排序 数据结构（Java版）叶核亚 3.2.2 希尔排序 图3.3 希尔排序算法描述 数据结构（Java版）叶核亚 希尔排序算法描述 n希尔排序算法共有三重循环 n最外层循环while语句控制增量jump，初值为数组长度
5、n 的一半，以后逐次减半（jump=jump / 2），直至为1。 n中间循环for语句进行一轮相隔jump的元素进行比较、交 换。 n最内层循环while语句，将第j个元素值this.get(j)与相隔 jump的第j-jump 个元素值this.get(j+jump)进行比较， 如果两者是反序的，则执行swap(j,j+jump)交换两个值 。重复往前与相隔jump的元素再比较、交换，j=jjump ，当this.get(j)this.get(j+jump)时，表示该元素 this.get(j)已在这趟排序后的位置，不需交换，则退出最 内层循环。 数据结构（Java版）叶核亚 希尔排序算法
6、 数据结构（Java版）叶核亚 3.3 交换排序 n3.3.1 冒泡排序 n3.3.2 快速排序 数据结构（Java版）叶核亚 3.3.1 冒泡排序 1冒泡排序算法 public void bubblesort() int i,j,n=this.length(); for(i=1;in;i+) /n-1趟排序 for(j=1;jthis.get(j+1) this.swap(j,j+1); /反序时，交换 System.out.print(第+i+趟 ); this.output(); 2算法分析 时间复杂度为O(n2)，空间复杂度为O(1) 。 数据结构（Java版）叶核亚 3改进的冒泡排序
7、 数据结构（Java版）叶核亚 改进的冒泡排序算法描述 数据结构（Java版）叶核亚 3.3.2 快速排序 图3.6 快速排序算法描述 图3.6 快速排序算法描述 数据结构（Java版）叶核亚 1快速排序算法 数据结构（Java版）叶核亚 2算法分析 n快速排序的平均比较次数为O(nlog2n)， 时间复杂度为O(nlog2n)。 n由于快速排序是递归算法，系统调用时 需要设立一个栈（stack）存放参数，最 大递归调用层次数为。因此，算法的空 间复杂度为O(nlog2n)。 数据结构（Java版）叶核亚 3.4 选择排序 1顺序表的直接选择排序算法 public void selectsor
8、t() int i,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=+min+ ); this.output(); 数据结构（Java版）叶核亚 3单向链表的直接选择排序 图3.8 单向链表的直接选择排序算法描述 数据结构（Java版）叶核亚 单向链表的直接选择排序算法
9、数据结构（Java版）叶核亚 3.5 归并排序 1归并排序算法描述 n所谓归并，就是将两个已排序的数据序列合并，形成 一个已排序的数据序列，又称两路归并。 图3.9 归并排序算法描述 数据结构（Java版）叶核亚 顺序存储 线性表的 归并排序 算法描述 数据结构（Java版）叶核亚 2顺序表的归并排序算法实现 数据结构（Java版）叶核亚 3算法分析 n归并排序算法的时间复杂度为 。 n归并排序算法的空间复杂度为O(n)，与 存储数据序列的空间量相等。 n归并排序算法是稳定的。 数据结构（Java版）叶核亚 4链表的归并排序算法 数据结构（Java版）叶核亚 归并两条已排序的单向链表 数据结构
10、（Java版）叶核亚 实习3 1实习目的：学习多种排序算法，灵活运行排 序算法解实际问题 2题意 （1）九宫排序问题 n在一个方框盘中放上8个方块，分别写上1，2， ，8，另有一个位置空着，如图3.12（a）所示。做 此游戏时，只能将与空格相邻的方块移入空格内。 要求对任意给定的初始状态，判断是否能够移成如 图3.12（b）的目标状态，若能则给出移动步伐， 否则输出不能移动信息。 图3.12 九宫排序图 数据结构（Java版）叶核亚 （2）多项式相加问题 n用单向链表可以表示含有一个未知数的多项式。 每个结点包含3个成员：指数，系数和指向后继结 点的链。例如，多项式3x4-6x25x-10可表示为图 3.13所示的链表。 图3.13 多项式链表 数据结构（Java版）叶核亚
