数据结构(Java版)排序.ppt
排序排序排序2基本概念基本概念n排序：排序： 将n个数字按一定顺序排列（比如：升序，或者降序）n班上有30个学生，按照学号进行由小到大的排序排序3基本概念基本概念n内部排序内部排序 ：若整个排序过程不需要访问外：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排存便能完成，则称此类排序问题为内部排序序 n外部排序外部排序：若参加排序的记录数量很大，：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序则称此类排序问题为外部排序排序4几种常用的排序方法几种常用的排序方法n冒泡排序n选择排序n快速排序n插入排序n希尔排序n归并排序排序5冒泡排序冒泡排序n基本思想基本思想：对所有相邻记录的关键字值进行比较，如果是逆序（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 51336296872817513351628717512896排序7 课堂练习与算法设计课堂练习与算法设计n一组关键字一组关键字（19,01,26,92,87,11,43,87,21），进行冒），进行冒泡排序，试列出每一趟排序后的关键字序泡排序，试列出每一趟排序后的关键字序列列n19,1,26,92,87,11,43,87,21ni=1 1 19 26 87 11 43 87 21 92 ni=2 1 19 26 11 43 87 21 87 92 ni=3 1 19 11 26 43 21 87 87 92 ni=4 1 11 19 26 21 43 87 87 92 ni=5 1 11 19 21 26 43 87 87 92 ni=6 1 11 19 21 26 43 87 87 92ni=7 1 11 19 21 26 43 87 87 92ni=8 1 11 19 21 26 43 87 87 92算法设计：for(int i=1;i=a.length-1;i+) for(j=0;jaj+1) 交换aj和aj+1编程实现排序8选择排序选择排序n基本思想基本思想：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、，并分别将它们定位到序列左侧（或右侧）的第1个位置、第2个位置、，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。 n选择排序种类选择排序种类：直接选择排序和堆排序排序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,in-1;i+)从aian-1中找出最小的元素放到ai处 min=i; for( j=i-1jaj)min=j; if(min!=i) 交换amin和ai 排序11插入排序插入排序n主要思想主要思想：不断地将待排序的数值插入到：不断地将待排序的数值插入到有序序列中，使有序序列逐渐扩大，直至有序序列中，使有序序列逐渐扩大，直至所有数值都进入有序序列中位置所有数值都进入有序序列中位置 n插入排序种类插入排序种类：直接插入排序、折半插入直接插入排序、折半插入排序、二路插入排序、表插入排序和希尔排序、二路插入排序、表插入排序和希尔排序排序排序12直接插入排序直接插入排序n基本思想基本思想：将记录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 排序14n一组关键字一组关键字（19, 1,26,92,87,11,43,87,21），进行插），进行插入入 排序，试列出每一趟排序后的关排序，试列出每一趟排序后的关键字序列键字序列n19, 1,26,92,87,11,43,87,21ni=1 1,19,26,92,87,11,43,87,21ni=2 1,19,26,92,87,11,43,87,21ni=3 1,19,26,92,87,11,43,87,21ni=4 1,19,26, 87,92,11,43,87,21ni=5 1, 11,19,26, 87,92,43,87,21ni=6 1, 11,19,26, 43,87,92,87,21ni=7 1, 11,19,26, 43,87,87,92,21ni=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快速排序快速排序n基本思想基本思想：首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选取一个记录（通常可选第一个记录），以它的关键字作为枢轴枢轴（或支点）（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排序方式比较排序方式比较排序方法平均时间最坏情况辅助空间直接插入排序直接插入排序O(n2)O(n2)O(1)冒泡排序冒泡排序O(n2)O(n2)O(1)直接选择排序直接选择排序O(n2)O(n2)O(1)希尔排序希尔排序O(n1.3)O(n1.3)O(1)快速排序快速排序O(nlog2n)O(n2)O(log2n)堆排序堆排序O(nlog2n)O(nlog2n)O(1)2路归并排序路归并排序O(nlog2n)O(nlog2n)O(n)排序20综合项目实践综合项目实践164页实战演练：设计一个项目可以对5000个数进行排序，计算并比较各种排序的时间。运行界面如下.
