数组的几种排序方式

大家好，欢迎来到IT知识分享网。

　　由于面试几次均遇到过数组排序，自己只擅长选择排序，所以写篇博客对排序做一个总结，加深记忆和理解（排序的复杂度涉及到算法等问题，本人菜鸟就不深入了，等掌握一些算法知识后，再回头把这些知识点补上）。主要总结三种方式：（1）冒泡排序（2）选择排序（3）快速排序

（一）冒泡排序：

　　　　　 原理：是相邻的两个数进行比较，符合条件的进行交换位置；

　　　　　 举例解析：比如数组  int[] arr = {22,36,18,43,14,19,6};

　　　　　 我们升序来排第一遍：最大数第一遍排完会放在最后一位

　　　　　 arr[0]与arr[1]比较之后的顺序：{22,36,18,43,14,19,6}（22<36，不交换）

　　　　　 arr[1]与arr[2]比较之后的顺序：{22,18,36,43,14,19,6}（18<36，交换）

　　　　　 arr[2]与arr[3]比较之后的顺序：{22,18,36,43,14,19,6}（36<43，不交换）

　　　　　 arr[3]与arr[4]比较之后的顺序：{22,18,36,14,43,19,6}（14<43，交换）

　　　　　 arr[4]与arr[5]比较之后的顺序：{22,18,36,14,19,43,6}（19<43，交换）

　　　　　 arr[5]与arr[6]比较之后的顺序：{22,18,36,14,19,6,43}（6<43，交换）

　　　　　第一遍排完43是最大数，放在了最后，这就像水泡往上升一样，慢慢升到了水平面上；第一遍比较了6次，数组长度为7；接着{22,18,36,14,19,6,43}进行第二遍遍历比较：

　　　　　arr[0]与arr[1]比较之后的顺序：{18,22,36,14,19,6,43}（18<22，交换）

 　　　　  arr[1]与arr[2]比较之后的顺序：{18,22,36,14,19,6,43}（22<36，不交换）

　　　　　arr[2]与arr[3]比较之后的顺序：{18,22,14,36,19,6,43}（14<36，不交换）

　　　　　arr[3]与arr[4]比较之后的顺序：{18,22,14,19,36,6,43}（19<36，交换）

　　　　　arr[4]与arr[5]比较之后的顺序：{18,22,14,19,6,36,43}（6<36，交换）

　　　　  第二遍走完，36排到了正确的位置，比较了5次(下面交不交换就不写了)，接着{18,22,14,19,6,36,43}进行第三遍比较:

　　　　   arr[0]与arr[1]比较之后的顺序：{18,22,14,19,6,36,43}

 　　　　  arr[1]与arr[2]比较之后的顺序：{18,14,22,19,6,36,43}

　　　　　arr[2]与arr[3]比较之后的顺序：{18,14,19,22,6,36,43}

　　　　　arr[3]与arr[4]比较之后的顺序：{18,14,19,6,22,36,43}

　　　　  第三遍走完，22排到了正确的位置，比较了4次，接着{18,14,19,6,22,36,43}进行第四遍比较:

　　　　  arr[0]与arr[1]比较之后的顺序：{14,18,19,6,22,36,43}

 　　　　 arr[1]与arr[2]比较之后的顺序：{14,18,19,6,22,36,43}

　　　　  arr[2]与arr[3]比较之后的顺序：{14,18,6,19,22,36,43}

　　　　  第四遍走完，19排到了正确的位置，比较了3次，接着{14,18,6,19,22,36,43}进行第五遍比较:

　　　　  arr[0]与arr[1]比较之后的顺序：{14,18,6,19,22,36,43}

　　　     arr[1]与arr[2]比较之后的顺序：{14,6,18,19,22,36,43}

　　　　  第五遍走完，18排到了正确的位置，比较了2次，接着{14,6,18,19,22,36,43}进行第六遍比较:

　　　　  arr[0]与arr[1]比较之后的顺序：{6,14,18,19,22,36,43}

             第六遍终于排完了（汗！！！(⊙﹏⊙)）。数组长度为7，排了6遍，第一遍比较6次，第二遍5次….第六遍1次；下面看代码：

 1 public class ArraySortDemo {
 2     
 3     public static void main(String[] args) {
 4         
 5         int[] arr = {22,36,18,43,14,19,6};
 6         MaoPaoSort(arr);
 7         printArray(arr);
 8         
 9     }
10     
11     //冒泡排序的方法
12     public static void MaoPaoSort(int[] arr){
13         //排了六遍，所以外层循环六次
14         for(int i=0;i<arr.length-1;i++){
15             //内层循环，每次比较的次数都在递减，所以可以得出如下的条件
16             for (int j = 0; j < arr.length-1-i; j++) {
17                 if(arr[j]>arr[j+1]){
18                     int temp = arr[j];
19                     arr[j] = arr[j+1];
20                     arr[j+1] = temp;
21                 }
22             }
23         }
24     }
25     
26     //打印数组的方法
27     public static void printArray(int[] arr){
28         System.out.print("[");
29         for (int i = 0; i < arr.length; i++) {
30             if(i<arr.length-1) 
31                 System.out.print(arr[i]+",");
32             else
33                 System.out.print(arr[i]+"]");
34         }
35     }
36     
37 }

View Code

　　　　 结果如下：

（二）选择排序：原理是arr[0]，与余下的所有数比较，符合条件的进行交换，这样，第一遍就把最小（或最大）的数固定在了第一个位置；然后第二遍是从arr[1]，与arr[2],arr[3]…..进行比较，然后把第二小的（或次大的）数固定在第二个位置了；然后第三遍，第四遍….依次这样排下去；

　　举例解析：比如数组  int[] arr = {22,36,18,43,14,19,6};

　　第1遍：arr[0]与arr[1]比较之后顺序：{22,36,18,43,14,19,6}；

　　　　　　arr[0]与arr[2]比较之后顺序：{18,36,22,43,14,19,6}；

　　　　　　arr[0]与arr[3]比较之后顺序：{18,36,22,43,14,19,6}；

　　　　　   arr[0]与arr[4]比较之后顺序：{14,36,22,43,18,19,6}；

　　　　　　arr[0]与arr[5]比较之后顺序：{14,36,22,43,18,19,6}；

　　　　　　arr[0]与arr[6]比较之后顺序：{6,36,22,43,18,19,14}；

　　第1遍结束，比较6次，6到了第一位，接着{6,36,22,43,18,19,14}从arr[1]开始比较第1遍:

　　　　　　arr[1]与arr[2]比较之后顺序：{6,22,36,43,18,19,14}；

　　　　　　arr[1]与arr[3]比较之后顺序：{6,22,36,43,18,19,14}；

　　　　　　arr[1]与arr[4]比较之后顺序：{6,18,36,43,22,19,14}；

　　　　　　arr[1]与arr[5]比较之后顺序：{6,18,36,43,22,19,14}；

　　　　　　arr[1]与arr[6]比较之后顺序：{6,14,36,43,22,19,18}；

　　第2遍结束，比较5次，14到了第2位，接着{6,14,36,43,22,19,18}从arr[2]开始比较第3遍:

　　           arr[2]与arr[3]比较之后顺序：{6,14,36,43,22,19,18}；

　　　　　　arr[2]与arr[4]比较之后顺序：{6,14,22,43,36,19,18}；

　　　　　　arr[2]与arr[5]比较之后顺序：{6,14,19,43,36,22,18}；

　　　　　　arr[2]与arr[6]比较之后顺序：{6,14,18,43,36,22,19}；

　　第3遍结束，比较4次，18到了第3位，接着{6,14,18,43,36,22,19}从arr[3]开始比较第4遍:

　　　　　　arr[3]与arr[4]比较之后顺序：{6,14,18,36,43,22,19}；

　　　　　　arr[3]与arr[5]比较之后顺序：{6,14,18,22,43,36,19}；

　　　　　　arr[3]与arr[6]比较之后顺序：{6,14,18,19,43,36,22}；

　　第4遍结束，比较3次，19到了第4位，接着{6,14,18,19,43,36,22}从arr[4]开始比较第5遍:

　　　　　　arr[4]与arr[5]比较之后顺序：{6,14,18,19,36,43,22}；

　　　　　　arr[4]与arr[6]比较之后顺序：{6,14,18,19,22,43,36}；

　　第5遍结束，比较2次，22到了第5位，接着{6,14,18,19,22,43,36}从arr[5]开始比较第6遍:

　　　　　　arr[5]与arr[6]比较之后顺序：{6,14,18,19,22,36,43}

　　第6遍结束,总共比排序排了6遍，第一遍比较6次，第二遍5次….第六遍1次，每一遍的比较次数，依次比上一遍少一次，代码方法如下

 1 //选择排序的方法
 2     public static void selectSort(int[] arr){
 3         //外层循环依旧是排六次
 4         for (int i = 0; i < arr.length-1; i++) {
 5             //内层循环，每次开始的角标在增加，注意i+1,后i=6,i+1等于7，角标会越界，所以外层i < arr.length-1
 6             for (int j = i+1; j < arr.length; j++) {
 7                 if(arr[i]>arr[j]){
 8                     int temp = arr[i];
 9                     arr[i] = arr[j];
10                     arr[j] = temp;
11                 }
12             }
13         }
14     }

View Code

 （三）快速排序：这个理解的不是很透彻，思路是，要定一个中间值，第一遍排序，要将这个数组分成左右两部分，左半部分全部小于这个中间值，右半部分全部大于这个中间值，

　　　　举例解析：比如数组  int[] arr = {22,36,18,43,14,19,6}，这个数组以第一个22为中间值，那么左半部分就是6,14,18,19（当然顺序不是这样排好的，顺序依旧是散乱的），右半部分应该是36,43，这样第一遍分了两部分之后，再分别对这两部分递归调用该函数；

　　　　第一遍排序：

　　　　　　　　　　从左往右比较：arr[0]=22与arr[6]=6比较,arr[0]>arr[6],交换{6,36,18,43,14,19,22}，接着进行，

　　　　　　　　　　从右往左比较：arr[0]与arr[6]已比较过,所以，arr[6]=22与arr[1]=36比较,arr[6]<arr[1]，交换{6,22,18,43,14,19,36}，接着进行

　　　　　　　　　　从左往右比较：arr[1]与arr[6]已比较过,所以，arr[1]=22与arr[5]=19比较，arr[1]>arr[5],交换{6,19,18,43,14,22,36}，接着进行

　　　　　　　　　　从右往左比较：arr[1]与arr[5]已比较过,所以，arr[5]=22与arr[2]=18比较，arr[5]>arr[2],不交换{6,19,18,43,14,22,36}，接着进行

　　　　　　　　　　因为没交换，所以还是从从右往左比较：即还是arr[5]=22与arr[3]=43比较，arr[3]>arr[5],交换{6,19,18,22,14,43,36}，接着进行

　　　　　　　　　　从左往右比较：arr[3]与arr[5]已比较过,所以，arr[3]=22与arr[4]=14比较，arr[2]>arr[4],交换{6,19,18,14,22,43,36}，接着进行

　　　　第一遍比较结束：这时候数组以22这个中间值就分层了左右两个部分{6,19,18,14} 与{43,36}；然后分别对这两部分采用第一遍的方式进行排序，即是递归调用了；显然右半部分来一次就完成了，左半部分进行排序{6,19,18,14}，arr[0]=6显然以这个为中间值排完后左半部分没有，右半部分为{19,18,14}，然后再以arr[0]=19这个中间值开始排：

　　　　　　　　    从左往右比较：arr[0]=19与arr[2]=14比较，arr[0]>arr[2],交换{14,18,19}，接着进行，

　　　　　　　　　 从右往左比较：arr[2]=19与arr[1]=18比较，显然，不用交换，结果{14,18,19}，排序结束；

整个排序到此就算结束，这样排下来整合就是想要的结果：{6,14,18,19,22,36,43}；关键点：定arr[0]为中间值，先从左往右比较,arr[0]与arr[6]，交换了（比较之后，arr[0]就不参与比较了，下次比较arr[0]的下一个索引，即arr[1]），就换成从右往左比较了，就依然是拿中间值（这时候arr[6]=中间值了）与左边的刚比较过的下一个索引的值比较（即arr[1]）,若是交换了（arr[6]就不参与了，arr[6]的前一个索引值arr[5]，参与比较）依次这样进行下去，当碰到索引在中间的时候就算结束了（即是left++>=right–）所以，需要定义左右两个角标；

终于要上代码了：

 1        //快速排序
 2     public static void quickSort(int[] arr,int start,int end){
 3         //首先判断，start>=end,就不用比较,即所数组里就一个元素的情况
 4         if(start>=end) return;
 5         //定义一个boolen值，确定是从左往右还是从右往左比较
 6         boolean flag = true;
 7         //然后start<end
 8         while(start<end){
 9             //从左往右比较
10             if(flag){
11                 if(arr[start]>=arr[end]){
12                     int temp = arr[start];
13                     arr[start]=arr[end];
14                     arr[end] = temp;
15                     start++;
16                     flag=false;
17                 }else{
18                     //不交换，那么与倒数第二个比较
19                     end--;
20                 }
21             }else{
22                 //从右往左开始比较
23                 if(arr[start]>=arr[end]){
24                     int temp = arr[start];
25                     arr[start]=arr[end];
26                     arr[end] = temp;
27                     end--;
28                     flag=true;
29                 }else{
30                     //不交换，与索引加1
31                     start++;
32                 }
33             }
34             quickSort(arr,0,start-1);
35             quickSort(arr,start+1,end);
36         }
37     }    

View Code

我靠，竟然写出来了，看来慢慢分析还是有用的，代码有可待优化的地方，暂时这样，更好理解，写的有点啰嗦！