由于面试几次均遇到过数组排序，自己只擅长选择排序，所以写篇博客对排序做一个总结，加深记忆和理解（排序的复杂度涉及到算法等问题，本人菜鸟就不深入了，等掌握一些算法知识后，再回头把这些知识点补上）。主要总结三种方式：（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
我靠，竟然写出来了，看来慢慢分析还是有用的，代码有可待优化的地方，暂时这样，更好理解，写的有点啰嗦！