013数组的排序方法（升序、降序、冒泡排序法、快速排序法、选择排序法、直接插入排序法）

013数组的排序⽅法（升序、降序、冒泡排序法、快速排序法、选择排序法、直接插⼊排序法）⾸先要知道数组中的排序有升序和降序，（这就需要去好好看看数据结构的排序⽅法原理了）排序⽅法对应的有冒泡排序法，快速排序法，选择排序法，直接插⼊排序法等⽅法我们先搞明⽩这些排序⽅法的思想和基本原理，然后再去看代码应该怎么写。下⾯⼀⼀介绍。（⼀）排序（1）升序使⽤java.util.Arrays类中的sort()⽅法对数组进⾏升序分为以下两步：1.导⼊java.util.Arrays包。2.使⽤Arrays.sort(数组名)语法对数组进⾏排序，排序规则是从⼩到⼤，即升序。例1：假设在数组scores中存放了5名学⽣的成绩，现在要实现从低到⾼排列的功能。在这⾥使⽤Arrays.sort()⽅法来实现，具体代码如下：publicstaticvoidmain(String[]args){//定义含有5个元素的数组double[]scores=newdouble[]{78,45,85,97,87};System.out.println("排序前数组内容如下：");//对scores数组进⾏循环遍历for(inti=0;i<scores.length;i++){System.out.print(scores[i]+"\t");}System.out.println("\n排序后的数组内容如下：");//对数组进⾏排序Arrays.sort(scores);//遍历排序后的数组for(intj=0;j<scores.length;j++){System.out.print(scores[j]+"\t");}}如上述代码所⽰，要对⼀个数组进⾏升序排列，只需要调⽤Arrays.sort()⽅法即可。运⾏后的输出结果如下所⽰。排序前数组内容如下：78.045.085.097.087.0排序后的数组内容如下：45.078.085.087.097.0（2）降序使⽤sort实现降序有两种⽅法，简单了解即可。1）利⽤Collections.reverseOrder()⽅法（Collections是⼀个包装类。⼤家可以学习《》⼀节详细了解）：publicstaticvoidmain(String[]args){Integer[]a={9,8,7,2,3,4,1,0,6,5};//数组类型为IntegerArrays.sort(a,Collections.reverseOrder());for(intarr:a){System.out.print(arr+"");}}输出结果如下：98765432102）实现Comparator接⼝的复写compare()⽅法，代码如下:publicclassTest{publicstaticvoidmain(String[]args){/**注意，要想改变默认的排列顺序，不能使⽤基本类型（int,double,char）⽽要使⽤它们对应的类*/Integer[]a={9,8,7,2,3,4,1,0,6,5};//定义⼀个⾃定义类MyComparator的对象Comparatorcmp=newMyComparator();Arrays.sort(a,cmp);for(intarr:a){System.out.print(arr+"");}}}//实现Comparator接⼝classMyComparatorimplementsComparator<Integer>{@Overridepublicintcompare(Integero1,Integero2){/**如果o1⼩于o2，我们就返回正值，如果o1⼤于o2我们就返回负值，这样颠倒⼀下，就可以实现降序排序了,反之即可⾃定义升序排序了*/returno2-o1;}}输出结果如下所⽰。9876543210注意：使⽤以上两种⽅法时，数组必须是包装类型，否则会编译不通过。（⼆）排序⽅法基本原理：1.⽐较相邻的元素。如果第⼀个⽐第⼆个⼤，就交换他们两个。2.对每⼀对相邻元素做同样的⼯作，从开始第⼀对到结尾的最后⼀对。在这⼀点，最后的元素应该会是最⼤的数。3.针对所有的元素重复以上的步骤，除了最后⼀个。4.持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。优化：针对问题：数据的顺序排好之后，冒泡算法仍然会继续进⾏下⼀轮的⽐较，直到arr.length-1次，后⾯的⽐较没有意义的。⽅案：设置标志位flag，如果发⽣了交换flag设置为true；如果没有交换就设置为false。这样当⼀轮⽐较结束后如果flag仍为false，即：这⼀轮没有发⽣交换，说明数据的顺序已经排好，没有必要继续进⾏下去。特点：冒泡排序的算法⽐较简单，排序的结果稳定，但时间效率不太⾼。假设待排序序列为(5,1,4,2,8)，如果采⽤冒泡排序对其进⾏升序（由⼩到⼤）排序，则整个排序过程如下所⽰：1)第⼀轮排序，此时整个序列中的元素都位于待排序序列，依次扫描每对相邻的元素，并对顺序不正确的元素对交换位置，整个过程如图1所⽰。2)第⼆轮排序，此时待排序序列只包含前4个元素，依次扫描每对相邻元素，对顺序不正确的元素对交换位置，整个过程如图2所⽰。3)第三轮排序，此时待排序序列包含前3个元素，依次扫描每对相邻元素，对顺序不正确的元素对交换位置，整个过程如图3所⽰。4)第四轮排序，此时待排序序列包含前2个元素，对其进⾏冒泡排序的整个过程如图4所⽰。5)（优化后，这⼀步不需要了）当进⾏第五轮冒泡排序时，由于待排序序列中仅剩1个元素，⽆论再进⾏相邻元素的⽐较，因此直接将其并⼊已排序序列中，此时的序列就认定为已排序好的序列（如图5所⽰）例2获取⽤户在控制台输⼊的5个成绩信息，将这些成绩保存到数组中，然后对数组应⽤冒泡排序，并输出排序后的结果，实现步骤如下。(1)创建⼀个Test24类⽂件，在main()⽅法中开始编码。⾸先创建Scanner类的实例后声明double类型的score数组，然后接收⽤户在控制台输⼊的成绩，并保存到元素中。代码如下：publicstaticvoidmain(String[]args){Scannerscan=newScanner(System.in);double[]score=newdouble[5];for(inti=0;i<score.length;i++){System.out.print("请输⼊第"+(i+1)+"个成绩：");score[i]=scan.nextDouble();}}(2)在对score数组排序之前，⾸先输出数组中各个元素的值。代码如下：System.out.println("排序前的元素值：");for(doubleval:score){System.out.print(val+"\t");}System.out.println();(3)通过冒泡排序⽅法实现对score数组的排序，在实现时需要借助⼀个临时变量。代码如下：publicstaticvoidmain(String[]args){System.out.println("通过冒泡排序⽅法对数组进⾏排序：");for(inti=0;i<score.length-1;i++){//⽐较相邻两个元素，较⼤的数往后冒泡for(intj=0;j<score.length-1-i;j++){if(score[j]>score[j+1]){doubletemp=score[j+1];//把第⼀个元素值保存到临时变量中score[j+1]=score[j];//把第⼆个元素值转移到第⼀个元素变量中score[j]=temp;//把临时变量（第⼀个元素的原值）保存到第⼆个元素中}System.out.print(score[j]+"");//对排序后的数组元素进⾏输出}System.out.print("【");for(intj=score.length-1-i;j<score.length;j++){System.out.print(score[j]+"");}System.out.println("】");}}(4)运⾏前⾯的代码进⾏测试，如下所⽰。请输⼊第1个成绩：77请输⼊第2个成绩：90请输⼊第3个成绩：68请输⼊第4个成绩：59请输⼊第5个成绩：80排序前的元素值：77.090.068.059.080.0通过冒泡排序⽅法对数组进⾏排序：77.068.059.080.0【90.0】68.059.077.0【80.090.0】59.068.0【77.080.090.0】59.0【68.077.080.090.0】基本原理：(1)⾸先设定⼀个分界值，通过该分界值将数组分成左右两部分。(2)将⼤于或等于分界值的数据集中到数组右边，⼩于分界值的数据集中到数组的左边。此时，左边部分中各元素都⼩于或等于分界值，⽽右边部分中各元素都⼤于或等于分界值。(3)然后，左边和右边的数据可以独⽴排序。对于左侧的数组数据，⼜可以取⼀个分界值，将该部分数据分成左右两部分，同样在左边放置较⼩值，右边放置较⼤值。右侧的数组数据也可以做类似处理。(4)重复上述过程，可以看出，这是⼀个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。例1：利⽤快速排序法对⼀数组进⾏排序(1)声明静态的getMiddle()⽅法，该⽅法需要返回⼀个int类型的参数值，在该⽅法中传⼊3个参数。代码如下：publicstaticintgetMiddle(int[]list,intlow,inthigh){inttmp=list[low];//数组的第⼀个值作为中轴（分界点或关键数据）while(low<high){while(low<high&&list[high]>tmp){high--;}list[low]=list[high];//⽐中轴⼩的记录移到低端while(low<high&&list[low]<tmp){low++;}list[high]=list[low];//⽐中轴⼤的记录移到⾼端}list[low]=tmp;//中轴记录到尾returnlow;//返回中轴的位置}(2)创建静态的unckSort()⽅法，在该⽅法中判断low参数是否⼩于high参数，如果是则调⽤getMiddle()⽅法，将数组⼀分为⼆，并且调⽤⾃⾝的⽅法进⾏递归排序。代码如下publicstaticvoidunckSort(int[]list,intlow,inthigh){if(low<high){intmiddle=getMiddle(list,low,high);//将list数组⼀分为⼆unckSort(list,low,middle-1);//对低字表进⾏递归排序unckSort(list,middle+1,high);//对⾼字表进⾏递归排序}}(3)声明静态的quick()⽅法，在该⽅法中判断传⼊的数组是否为空，如果不为空，则调⽤unckSort()⽅法进⾏排序。代码如下：publicstaticvoidquick(int[]str){if(str.length>0){//查看数组是否为空unckSort(str,0,str.length-1);}}(4)在main()⽅法中声明int类型的number数组，接着输出该数组中的元素。然后调⽤⾃定义的quick()⽅法进⾏排序，排序后重新输出数组中的元素。代码如下：int[]number={13,15,24,99,14,11,1,2,3};System.out.println("排序前：");for(intval:number){System.out.print(val+"");}quick(number);System.out.println("\n排序后：");for(intval:number){System.out.print(val+"");}运⾏前⾯的代码进⾏测试，输出结果如下：排序前：131524991411123排序后：123111314152499（3）选择排序法⼯作原理：每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最⼩（⼤）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。类别常见的选择排序可以分为（Straightselectionsort）、（Tree-typeselectionsort）以及（Heapsort）。（1）。①基本思想。实现思想是每步从排序记录中选出排序码最⼩（最⼤）的记录，放在已排序记录序列的最后（前）；②算法特点。直接选择排序算法n个记录的⽂件的直接选择排序可经过n-1趟直接选择排序得到有序结果。（2）。①基本思想。其实现思想是保存先前⽐较的结果以减少⽐较次数，是⼀种不稳定的排序⽅法。⾸先对n个记录的关键字进⾏两两⽐较，然后在n/2个较⼩者之间再进⾏两两⽐较，如此重复，直⾄选出最⼩的记录为⽌。（3）。①基本思想。堆排序是⼀种树形选择排序，是对直接选择排序的有效改进；②算法描述。从算法描述来看，堆排序需要两个过程，即建⽴堆和堆顶与堆的最后⼀个元素交换位置。所以堆排序有两个函数组成，⼀是建堆的渗透函数，⼆是反复调⽤渗透函数实现排序的函数；③算法特点。堆排序可通过树形结构保存部分⽐较结果，可减少⽐较次数。但由于建初始堆所需的⽐较次数较多，所以堆排序不适宜于记录数较少的⽂件。例1：使⽤选择排序法重新对number（该数组中的元素依次是13、15、24、99、4和1）中的元素进⾏排序。//第⼀趟选择排序13、15、24、1、4、99//第⼆趟选择排序13、15、4、1、24、99//第三趟选择排序13、1、4、15、24、99//第四趟选择排序4、1、13、15、24、99//第五趟选择排序1、4、13、15、24、99例2：代码。利⽤选择排序⽅法通过编程的⽅式实现对number数组的排序，并输出已排序的数组元素。int[]number={13,15,24,99,4,1};Stringend="\n";intindex;for(inti=1;i<number.length;i++){index=0;for(intj=1;j<=number.length-i;j++){if(number[j]>number[index]){index=j;//查找最⼤值}}end=number[index]+""+end;//定位已排好的数组元素inttemp=number[number.length-i];number[number.length-1]=number[index];number[index]=temp;System.out.print("【");for(intj=0;j<number.length-i;j++){System.out.print(number[j]+"");}System.out.print("】"+end);}结果：【13152414