数据结构(Java版)排序

排序深圳职业技术学院软件系排序2基本概念排序：将n个数字按一定顺序排列（比如：升序，或者降序）班上有30个学生，按照学号进行由小到大的排序排序3基本概念内部排序：若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序外部排序：若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序排序4几种常用的排序方法冒泡排序选择排序快速排序插入排序希尔排序归并排序排序5冒泡排序基本思想：对所有相邻记录的关键字值进行比较，如果是逆序（a[j]a[j+1]），则将其交换，最终达到有序化排序6冒泡排序实例初始关键字序列：5133629687172851第一趟排序结果：33516287172851[96]第二趟排序结果：335162172851[8796]第三趟排序结果：3351172851[628796]第四趟排序结果：33172851[51628796]第五趟排序结果：172833[5151628796]第六趟排序结果：[1728335151628796]51336296872817513351628717512896排序7课堂练习与算法设计一组关键字（19,01,26,92,87,11,43,87,21），进行冒泡排序，试列出每一趟排序后的关键字序列19,1,26,92,87,11,43,87,21i=111926871143872192i=211926114387218792i=311911264321878792i=411119262143878792i=511119212643878792i=611119212643878792i=711119212643878792i=811119212643878792算法设计：for(inti=1;i=a.length-1;i++)for(j=0;ja.length-1-i;j++)if(a[j]a[j+1])交换a[j]和a[j+1]编程实现排序8选择排序基本思想：依次从待排序记录序列中选择出关键字值最小（或最大）的记录、关键字值次之的记录、……，并分别将它们定位到序列左侧（或右侧）的第1个位置、第2个位置、……，从而使待排序的记录序列成为按关键字值由小到大（或由大到小）排列的有序序列。选择排序种类：直接选择排序和堆排序排序9直接选择排序实例初始关键字序列：5133629687172851↑↑第一趟排序后：[17]33629687512851↑↑第二趟排序后：[1728]629687513351↑↑第三趟排序后：[172833]9687516251第四趟排序后：[17283351]87966251第五趟排序后：[1728335151]966287第六趟排序后：[172833515162]9687第七趟排序后：[1728335151628796]排序10课堂练习与算法设计选择排序过程：3412452187263i=13124521872634i=23124521872634i=33122145872634i=43122126874534i=53122126344587i=63122126344587算法设计：n=a.length;for(i=0,in-1;i++){从a[i]…a[n-1]中找出最小的元素放到a[i]处min=i;for(j=i-1jn-1;j++)if(a[min]a[j])min=j;if(min!=i)交换a[min]和a[i]}排序11插入排序主要思想：不断地将待排序的数值插入到有序序列中，使有序序列逐渐扩大，直至所有数值都进入有序序列中位置插入排序种类：直接插入排序、折半插入排序、二路插入排序、表插入排序和希尔排序排序12直接插入排序基本思想：将记录R[i]插入到有序子序列R[0..i-1]中，使记录的有序序列从R[0..i-1]变为R[0..i]排序13直接插入排序实例初始关键字序列：[51]33629687172851i=1(33)[3351]629687172851i=2(62)[335162]9687172851i=3(96)[33516296]87172851i=4(87)[3351628796]172851i=5(17)[173351628796]2851i=6(28)[17283351628796]51i=7(51)[1728335151628796]排序14一组关键字（19,1,26,92,87,11,43,87,21），进行插入排序，试列出每一趟排序后的关键字序列19,1,26,92,87,11,43,87,21i=11,19,26,92,87,11,43,87,21i=21,19,26,92,87,11,43,87,21i=31,19,26,92,87,11,43,87,21i=41,19,26,87,92,11,43,87,21i=51,11,19,26,87,92,43,87,21i=61,11,19,26,43,87,92,87,21i=71,11,19,26,43,87,87,92,21i=81,11,19,21,26,43,87,87,92算法设计：voidinsertSort(inta[]){n=a.length;for(i=1;in;i++){将a[i]插入到a[0]…a[i-1]中,保持原来的排序1在a[0]…a[i-1]中找到插入的位置j2把a[j]…a[i-1]逐个后移一个位置(a[i-1]移到a[i],…a[j]移到a[j+1]])3把a[i]放到a[j]处}}课堂练习与算法设计排序15快速排序基本思想：首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选取一个记录（通常可选第一个记录），以它的关键字作为枢轴（或支点）（pivot），凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后排序16快速排序一趟排序过程初始关键字序列：[51]33629687172851R[0]=51i↑j↑第一次交换之后：[28]3362968717[28]51i↑j↑第二次交换之后：2833[62]968717[62]51i↑j↑第三次交换之后：2833[17]9687[17]6251i↑j↑第四次交换之后：283317[96]87[96]6251i↑j↑完成一趟排序：283317[51]87966251排序17快速排序结果初始关键字序列：5133629687172851一趟排序之后：[283317]51[87966251]分别进行快速排序：[17]28[33][5162]87[96]51[62]有序序列：1728335151628796排序18课堂练习与算法设计给出一组关键字，快速排序的每一趟的排序结果：46,58,15,45,90,18,10,62,87,23t=4623,58,15,45,90,18,10,62,87,23ijt=4623,58,15,45,90,18,10,62,87,58ijt=4623,10,15,45,90,18,10,62,87,58ijt=4623,10,15,45,90,18,90,62,87,58ijt=4623,10,15,45,46,18,90,62,87,58ij算法设计：voidquickSort(inta[],ints,intt){if(st){k=partion(a,s,t);quickSort(a,s,k-1)quickSort(a,k+1,t)}}intpartion(inta[],intl,intr){temp=a[l];j=r;i=l;while(ij){从j位置逐个比较temp和a[j],把比temp小的元素调到a[i]处；从i位置逐个比较temp和a[i],把比temp大的元素调到a[j]处；}returnj;}}排序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个数进行排序，计算并比较各种排序的时间。运行界面如下.