数据结构(Java版)排序PPT课件.ppt

排序
深圳职业技术学院软件系
1
-
基本概念
排序：
将n个数字按一定顺序排列（比如：升序，或者降序）
班上有30个学生，按照学号进行由小到大的排序
2
-
基本概念
内部排序 ：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序
外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序
3
-
几种常用的排序方法
冒泡排序
选择排序
快速排序
插入排序
希尔排序
归并排序
4
-
冒泡排序
基本思想：对所有相邻记录的关键字值进行比较，如果是逆序（a[j]>a[j+1]），则将其交换，最终达到有序化
5
-
冒泡排序实例
初始关键字序列： 51 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
6
-
课堂练习与算法设计
一组关键字（19,01,26,92,87,11,43,87,21），进行冒泡排序，试列出每一趟排序后的关键字序列
19,1,26,92,87,11,43,87,21
i=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 92
i=7 1 11 19 21 26 43 87 87 92
i=8 1 11 19 21 26 43 87 87 92
算法设计：
for(int i=1;i<=-1;i++)
for(j=0;j<-1-i;j++)
if(a[j]>a[j+1])
交换a[j]和a[j+1]
编程实现
7
-
选择排序
基本思想：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、……，并分别将它们定位到序列左侧（或右侧）的第1个位置、第2个位置、……，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。
选择排序种类：直接选择排序和堆排序
8
-
直接选择排序实例
初始关键字序列： 51 33 62 96 87 17 28 51
↑ ↑
第一趟排序后： [17] 33 62 96 87 51 28 51
↑ ↑
第二趟排序后： [17 28] 62 96 87 51 33 51
↑ ↑
第三趟排序后： [17 28 33] 96 87 51 62 51
第四趟排序后： [17 28 33 51] 87 96 62 51
第五趟排序后： [17