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

《数据结构(Java版)排序.ppt》由会员分享，可在线阅读，更多相关《数据结构(Java版)排序.ppt（20页珍藏版）》请在三一办公上搜索。

1、排序,排序,2,基本概念,排序：将n个数字按一定顺序排列（比如：升序，或者降序）班上有30个学生，按照学号进行由小到大的排序,排序,3,基本概念,内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序 外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序,排序,4,几种常用的排序方法,冒泡排序选择排序快速排序插入排序希尔排序归并排序,排序,5,冒泡排序,基本思想：对所有相邻记录的关键字值进行比较，如果是逆序（ajaj+1），则将其交换，最终达到有序化,排序,6,冒泡排序实例,初始关键字序列：51 33 62 96 87 17

2、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,87,11,43,87,21），进行冒泡排序

3、，试列出每一趟排序后的关键字序列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,算法设计：for(int i=1;iaj+

4、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 第三趟排序后：17 28 33 96 87 51 62 51第四趟

5、排序后：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 34 45 87i=6 3 12 21 26 34 45 87

6、,算法设计：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=1(33)33 51 62 96 87 17 28 51i=2(62)

7、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,87,21i=1 1,19,26,92,87,11,43,87,21i=2 1,19,2

8、6,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+)将ai插入到a0ai-1中,保持原来的排序 1 在a0ai-1中找到插入的位置j 2 把ajai-1逐个后移一

9、个位置(ai-1移到ai,aj移到aj+1)3 把ai放到aj处,课堂练习与算法设计,排序,15,快速排序,基本思想：首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选取一个记录（通常可选第一个记录），以它的关键字作为枢轴（或支点）（pivot），凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后,排序,16,快速排序一趟排序过程,初始关键字序列：51 33 62 96 87 17 28 51R0=51 i j第一次交换之后：28 33 62 96 87 17 28 51 i j第二次交换之后：28 33 62 96 87 17 62 51 i

10、 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 62 87 96,排序,18,课堂练习与算法设计,给出一组关键字，快速排序的每一趟的排序结果：46,58,15,45,90,18,

11、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个数进行排序，计算并比较各种排序的时间。运行界面如下.,