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

排序,排序,2,基本概念,排序：将n个数字按一定顺序排列（比如：升序，或者降序）班上有30个学生，按照学号进行由小到大的排序,排序,3,基本概念,内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序 外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序,排序,4,几种常用的排序方法,冒泡排序选择排序快速排序插入排序希尔排序归并排序,排序,5,冒泡排序,基本思想：对所有相邻记录的关键字值进行比较，如果是逆序（ajaj+1），则将其交换，最终达到有序化,排序,6,冒泡排序实例,初始关键字序列：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,排序,7,课堂练习与算法设计,一组关键字（19,01,26,92,87,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,算法设计：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 第三趟排序后：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 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=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,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+)将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第一次交换之后：28 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 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个数进行排序，计算并比较各种排序的时间。运行界面如下.,