《数据结构(Java版)排序ppt课件.ppt》由会员分享,可在线阅读,更多相关《数据结构(Java版)排序ppt课件.ppt(20页珍藏版)》请在三一办公上搜索。
1、排序,深圳职业技术学院软件系,排序,2,基本概念,排序: 将n个数字按一定顺序排列(比如:升序,或者降序)班上有30个学生,按照学号进行由小到大的排序,排序,3,基本概念,内部排序 :若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序 外部排序:若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序,排序,4,几种常用的排序方法,冒泡排序选择排序快速排序插入排序希尔排序归并排序,排序,5,冒泡排序,基本思想:对所有相邻记录的关键字值进行比较,如果是逆序(ajaj+1),则将其交换,最终达到有序化,排序,6,冒泡排序实例,初始关键字序列: 51
2、33 62 96 87 17 28 51第一趟排序结果: 33 51 62 87 17 28 51 96 第二趟排序结果: 33 51 62 17 28 51 87 96 第三趟排序结果: 33 51 17 28 51 62 87 96 第四趟排序结果: 33 17 28 51 51 62 87 96 第五趟排序结果: 17 28 33 51 51 62 87 96 第六趟排序结果: 17 28 33 51 51 62 87 96,51,33,62,96,87,28,17,51,33,51,62,87,17,51,28,96,排序,7,课堂练习与算法设计,一组关键字(19,01,26,92,8
3、7,11,43,87,21),进行冒泡排序,试列出每一趟排序后的关键字序列19,1,26,92,87,11,43,87,21i=1 1 19 26 87 11 43 87 21 92 i=2 1 19 26 11 43 87 21 87 92 i=3 1 19 11 26 43 21 87 87 92 i=4 1 11 19 26 21 43 87 87 92 i=5 1 11 19 21 26 43 87 87 92 i=6 1 11 19 21 26 43 87 87 92i=7 1 11 19 21 26 43 87 87 92i=8 1 11 19 21 26 43 87 87 92,
4、算法设计:for(int i=1;iaj+1) 交换aj和aj+1,编程实现,排序,8,选择排序,基本思想:依次从待排序记录序列中选择出关键字值最小(或最大)的记录、关键字值次之的记录、,并分别将它们定位到序列左侧(或右侧)的第1个位置、第2个位置、,从而使待排序的记录序列成为按关键字值由小到大(或由大到小)排列的有序序列。 选择排序种类:直接选择排序和堆排序,排序,9,直接选择排序实例,初始关键字序列: 51 33 62 96 87 17 28 51 第一趟排序后: 17 33 62 96 87 51 28 51 第二趟排序后: 17 28 62 96 87 51 33 51 第三趟排序后:
5、 17 28 33 96 87 51 62 51第四趟排序后: 17 28 33 51 87 96 62 51第五趟排序后: 17 28 33 51 51 96 62 87 第六趟排序后: 17 28 33 51 51 62 96 87 第七趟排序后: 17 28 33 51 51 62 87 96,排序,10,课堂练习与算法设计,选择排序过程: 34 12 45 21 87 26 3i=1 3 12 45 21 87 26 34i=2 3 12 45 21 87 26 34i=3 3 12 21 45 87 26 34i=4 3 12 21 26 87 45 34i=5 3 12 21 26
6、 34 45 87i=6 3 12 21 26 34 45 87,算法设计:n=a.length;for(i=0,iaj)min=j; if(min!=i) 交换amin和ai,排序,11,插入排序,主要思想:不断地将待排序的数值插入到有序序列中,使有序序列逐渐扩大,直至所有数值都进入有序序列中位置 插入排序种类:直接插入排序、折半插入排序、二路插入排序、表插入排序和希尔排序,排序,12,直接插入排序,基本思想:将记录Ri插入到有序子序列R0.i-1中,使记录的有序序列从R0.i-1变为R0.i,排序,13,直接插入排序实例,初始关键字序列: 51 33 62 96 87 17 28 51i=
7、1(33) 33 51 62 96 87 17 28 51i=2(62) 33 51 62 96 87 17 28 51i=3(96) 33 51 62 96 87 17 28 51i=4(87) 33 51 62 87 96 17 28 51i=5(17) 17 33 51 62 87 96 28 51i=6(28) 17 28 33 51 62 87 96 51i=7(51) 17 28 33 51 51 62 87 96,排序,14,一组关键字(19, 1,26,92,87,11,43,87,21),进行插入 排序,试列出每一趟排序后的关键字序列19, 1,26,92,87,11,43,
8、87,21i=1 1,19,26,92,87,11,43,87,21i=2 1,19,26,92,87,11,43,87,21i=3 1,19,26,92,87,11,43,87,21i=4 1,19,26, 87,92,11,43,87,21i=5 1, 11,19,26, 87,92,43,87,21i=6 1, 11,19,26, 43,87,92,87,21i=7 1, 11,19,26, 43,87,87,92,21i=81, 11,19,21,26, 43,87,87,92,算法设计:void insertSort(int a)n=a.length;for(i=1;in;i+) 将
9、ai插入到a0ai-1中,保持原来的排序 1 在a0ai-1中找到插入的位置j 2 把ajai-1逐个后移一个位置 (ai-1移到ai,aj移到aj+1) 3 把ai放到aj处 ,课堂练习与算法设计,排序,15,快速排序,基本思想:首先将待排序记录序列中的所有记录作为当前待排序区域,从中任选取一个记录(通常可选第一个记录),以它的关键字作为枢轴(或支点)(pivot),凡其关键字小于枢轴的记录均移动至该记录之前,反之,凡关键字大于枢轴的记录均移动至该记录之后,排序,16,快速排序一趟排序过程,初始关键字序列: 51 33 62 96 87 17 28 51R0=51 i j第一次交换之后: 2
10、8 33 62 96 87 17 28 51 i j第二次交换之后: 28 33 62 96 87 17 62 51 i j第三次交换之后: 28 33 17 96 87 17 62 51 i j 第四次交换之后: 28 33 17 96 87 96 62 51 i j 完成一趟排序: 28 33 17 51 87 96 62 51,排序,17,快速排序结果,初始关键字序列: 51 33 62 96 87 17 28 51一趟排序之后: 28 33 17 51 87 96 62 51分别进行快速排序:17 28 33 51 62 87 96 51 62 有序序列: 17 28 33 51 51
11、 62 87 96,排序,18,课堂练习与算法设计,给出一组关键字 ,快速排序的每一趟的排序结果:46,58,15,45,90,18,10,62,87,23t=46 23,58,15,45,90,18,10,62,87,23 i jt=46 23,58,15,45,90,18,10,62,87,58 i jt=46 23,10,15,45,90,18,10,62,87,58 i jt=46 23,10,15,45,90,18,90,62,87,58 i jt=46 23,10,15,45,46,18,90,62,87,58 i j,算法设计:void quickSort(int a ,int s,int t) if(st) k=partion(a,s,t); quickSort (a,s,k-1) quickSort (a,k+1,t) int partion(int a,int l,int r) temp=al;j=r;i=l; while(ij) 从j位置逐个比较temp和aj,把比temp小的元素调到ai处; 从i位置逐个比较temp和ai,把比temp大的元素调到aj处; return j; ,排序,19,排序方式比较,排序,20,综合项目实践,164页实战演练:设计一个项目可以对5000个数进行排序,计算并比较各种排序的时间。运行界面如下.,
链接地址:https://www.31ppt.com/p-1350137.html