在面試的時候偶爾會被問到排序的算法，有時候也會被要求把排序算法寫出來，可一直也沒當回事。直到前天面試的時候被要求當場寫出一個程序對給定的數組進行排序。當時本來想寫一個冒泡排序算法，寫到最後才發現寫了一個不倫不類的排序程序，冒泡不冒泡、插入不插入，回來之後想著是需要好好研究一些這些排序算法了，於是就決定把這幾種常用的排序算法總結一下。
排序要求：把長度為n的數組a按照從小到大的順序進行排序。
冒泡排序思路：給定一個長度為n的數組a，循環n-1次，每次循環找出a[0]到a[n-i-1]中最大數的數，然後把該數放在a[n-1]的位置。
如何找出a[0]到a[n-i-1]中的最大數？：循環一遍，比較a[i]和a[i+1]的大小，如a[i]<a[i+1],兩數交換位置，然後繼續判斷a[i+1]和a[i+2]的大小，以此循環結束。
排序示例：
原數組： 2、0、3、6、8、4、9、5、1、7、
第1次循環排序結果: 0、2、3、6、4、8、5、1、7、9、
第2次循環排序結果: 0、2、3、4、6、5、1、7、8、9、
第3次循環排序結果: 0、2、3、4、5、1、6、7、8、9、
第4次循環排序結果: 0、2、3、4、1、5、6、7、8、9、
第5次循環排序結果: 0、2、3、1、4、5、6、7、8、9、
第6次循環排序結果: 0、2、1、3、4、5、6、7、8、9、
第7次循環排序結果: 0、1、2、3、4、5、6、7、8、9、
第8次循環排序結果: 0、1、2、3、4、5、6、7、8、9、
第9次循環排序結果: 0、1、2、3、4、5、6、7、8、9、
public void myBubbleSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
int num = array[j];
array[j] = array[j + 1];
array[j + 1] = num;
}
}
}
}
注意兩次循環的范圍：
外循環次數： n-1次，固定不變的，即使在n-m(0<m<n)之前已經完成排序（注意排序示例中的7.8.9次循環），程序仍要循環n-m 到n-1。
內循環次數： 根據外循環變化而變化，次數為 （n-i-1）+……+2++1
