数据结构Java版第3章--排序分析ppt课件.ppt

《数据结构Java版第3章--排序分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构Java版第3章--排序分析ppt课件.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确数据结构（数据结构（Java版）版）叶核亚叶核亚在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确数据结构（数据结构（Java版）版）第1章 绪论第2章 线性表第3章 排序第4章 栈与队列第5章 数组和广义表第6章 树和二叉树第7章 查找第8章 图第9章 综合应用设计在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确第3章 排序3.1 排序的基本概念3.2 插入排序3.3

2、交换排序3.4 选择排序3.5 归并排序在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.1 排序的基本概念1数据序列数据序列（datalist）是待排序的数据元素的有限集合。2关键字通常数据元素由多个数据项组成，以其中某个数据项作为排序依据，则该数据项称为关键字（key）。3排序算法的稳定性在数据序列中，如果有两个数据元素ri和rj，它们的关键字ki等于kj，且在未排序时，ri位于rj之前。如果排序后，元素ri仍在rj之前，则称这样的排序算法是稳定的（stable），否则是不稳定的排序算法。在整堂课的教学中，刘教师总是让学生带着问

3、题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确4内排序与外排序n内排序：在待排序的数据序列中，数据元素个数较少，整个排序过程中所有的数据元素都可以保留在内存，则这样的排序称为内排序。n外排序：待排序的数据元素非常多，以至于它们必须存储在磁盘等外部存储介质上，则这样的排序称为外排序。显然，外排序过程中需要多次访问外存。5排序算法的性能评价n排序算法的时间复杂度：指算法执行中的数据比较次数、数据移动次数与待排序数据序列的元素个数n之间的关系。n排序算法的空间复杂度：指算法执行中，除待排序数据序列本身所占用的内存空间外，需要的附加内存空间与待排序数据序列的元素个数n之间的关系。

4、在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.2 插入排序n插入排序（insertion sort）的基本思想是：每趟将一个待排序的数据元素，按其关键字大小，插入到已排序的数据序列中，使得插入后的数据序列仍是已排序的，直到全部元素插入完毕。n3.2.1 直接插入排序n3.2.2 希尔排序在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.2.1 直接插入排序1直接插入排序算法2顺序存储结构线性表的直接插入排序图3.1 直接插入排序算法描述在整堂课的教学中，刘教师总是让学

5、生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确【例3.1】顺序表的直接插入排序的算法实现与测试。数据结构（Java版）叶核亚在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3算法分析n直接插入排序的平均比较次数为 n平均移动次数为n直接插入排序的时间复杂度为O(n2)。n直接插入排序算法是稳定的。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确4链表的直接插入排序图3.2 双向链表的插入排序算法描述在整堂课的教学中，刘教师总是让学生带着问题来学习

6、，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确【例3.2】双向链表的直接插入排序数据结构（Java版）叶核亚在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.2.2 希尔排序图3.3 希尔排序算法描述在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确希尔排序算法描述n希尔排序算法共有三重循环n最外层循环while语句控制增量jump，初值为数组长度n的一半，以后逐次减半（jump=jump/2），直至为1。n中间循环for语句进行一轮相隔jump的元素进行比较、

7、交换。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版）叶核亚在整堂课的教学中，刘教师总是让学生

8、带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.3 交换排序n3.3.1 冒泡排序n3.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;jthis.get(j+1)this.swap(j,j+1);/反序时，交换 System.out.print(第+i+趟 );this.output();2算法分析

9、时间复杂度为O(n2)，空间复杂度为O(1)。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3改进的冒泡排序数据结构（Java版）叶核亚在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确改进的冒泡排序算法描述在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.3.2 快速排序图3.6 快速排序算法描述图3.6 快速排序算法描述在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提

10、出的问题也很明确1快速排序算法数据结构（Java版）叶核亚在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确2算法分析n快速排序的平均比较次数为O(nlog2n)，时间复杂度为O(nlog2n)。n由于快速排序是递归算法，系统调用时需要设立一个栈（stack）存放参数，最大递归调用层次数为。因此，算法的空间复杂度为O(nlog2n)。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.4 选择排序1顺序表的直接选择排序算法 public void selectsort()int

11、 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();在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3单向链表的直接选择排序图3.8 单向链表的直接选择排序算法描述在整堂课的教学中，刘教师

12、总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确单向链表的直接选择排序算法数据结构（Java版）叶核亚在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3.5 归并排序1归并排序算法描述n所谓归并，就是将两个已排序的数据序列合并，形成一个已排序的数据序列，又称两路归并。图3.9 归并排序算法描述在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确顺序存储线性表的归并排序算法描述在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定

13、的梯度，由浅入深，所提出的问题也很明确2顺序表的归并排序算法实现数据结构（Java版）叶核亚在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确3算法分析n归并排序算法的时间复杂度为 。n归并排序算法的空间复杂度为O(n)，与存储数据序列的空间量相等。n归并排序算法是稳定的。在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确4链表的归并排序算法在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确归并两条已排序的单向链表数据结构

14、（Java版）叶核亚在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确实习31实习目的：学习多种排序算法，灵活运行排序算法解实际问题2题意（1）九宫排序问题n在一个方框盘中放上8个方块，分别写上1，2，8，另有一个位置空着，如图3.12（a）所示。做此游戏时，只能将与空格相邻的方块移入空格内。要求对任意给定的初始状态，判断是否能够移成如图3.12（b）的目标状态，若能则给出移动步伐，否则输出不能移动信息。图3.12 九宫排序图在整堂课的教学中，刘教师总是让学生带着问题来学习，而问题的设置具有一定的梯度，由浅入深，所提出的问题也很明确（2）多项式相加问题n用单向链表可以表示含有一个未知数的多项式。每个结点包含3个成员：指数，系数和指向后继结点的链。例如，多项式3x4-6x25x-10可表示为图3.13所示的链表。图3.13 多项式链表