1.原理
（1）比較相鄰的元素。如果第一個比第二個大，就交換他們兩個；
（2）對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數；
（3）針對所有的元素重復以上的步驟，除了最後一個；
（4）持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
2.一個直接但是低效的實現
public void sort(int[] array) {
//外層循環從第0個元素遍歷到倒數第二個元素，主要是用來控制內層循環的次數
//因為外層循環每跑一次，最大的數就會到最後面
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 temp = array[j+1];
array[j+1] = array[j];
array[j] =temp;
}
}
}
}
3.優化版本（優化的地方是，如果遍歷了一次，發現沒有任何交換，那麼說明已經排好序了，後面就可以不用排了）
public void sort(int[] array) {
boolean swaped;
int n = array.length;
do {
swaped = false;
for (int i = 1; i < n; i++) {
if (array[i - 1] > array[i]) {
//如果這趟有兩個元素換過位置，那麼是否排過序設置成true
//一旦有某一趟沒有任何兩個元素換過位置，說明已經排好了，整個排序過程可以停止了
int temp = array[i - 1];
array[i - 1] = array[i];
array[i] = temp;
swaped = true;
}
}
n--;
} while (swaped);
}
1.原理：
選擇排序是對冒泡排序的改進，因為冒泡排序每次比較後都要互換兩個元素位置，而互換的過程會有幾次賦值，特別耗費時間。
選擇排序的思路：
是每一次從待排序的數據元素中選出最小的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完
2.一個簡單的實現：
public void sort(int[] array) {
for (int i = 0; i < array.length; i++) {
//找到最小元素的索引位置
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
int temp = array[i];
array[i] = array[minIndex];
array[minIndex] = temp;
}
}
3.小結：
選擇排序因為每一次遍歷都要從元素中選擇最小的，所以每次都要遍歷完整個數組，也是一個效率特別低的排序。
1.原理：
插入排序的原理和打牌的時候理牌比較像，就是每步將一個待排序的紀錄，將其插入前面已經排序的序列的適當位置上，直到全部插入完為止。
2.實現代碼版本1：
public void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
//從外層循環的位置開始從前面找，如果j-1位置的數比j位置數大，那麼交換
for (int j = i; j > 0 ; j--) {
if (array[j] < array[j - 1]) {
int temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
//這個else是插入排序比較高效的關鍵，因為如果第i位置的前面的元素都排好序了，所以如果i位置比i-1位置小，就表示這趟排好序了
else{
break;
}
}
}
}
可以看到，插入排序，是把當前i元素插入到之前合適的位置裡，整個遍歷的過程中，有break過程。
它不像選擇排序，為了找到最小的數，必須遍歷完整個數組
3.但是上面的程序稍顯累贅，修改下
public void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
//把break條件放到for循環裡面來，看起來很清爽
for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
int temp = array[j - 1];
array[j - 1] = array[j];
array[j] = temp;
}
}
}
4.上面的程序仍然有問題，可以看到，每次交換都需要交換三個值，可以進一步修改一下
public void sort(int[] array) {
for (int i = 1; i < array.length; i++) {
// 改進後的
int e = array[i];
int j;
for (j = i; j > 0 && array[j - 1] > e; j--) {
array[j] = array[j - 1];
}
array[j] = e;
}
}
稍微解釋一下：
在內層循環中，把第i位置的數存下來，再依次遍歷，如果第j-1位置的數比第j位置的數大，那麼直接把j-1位置的數覆蓋到第j位置
直到找到i位置合適的位置為止，也就是array[j-1] < e 為止。
最後才把剛剛存下來的數，賦值給找到的位置
這樣可以省去很多不必要的賦值過程，效率略顯提高
5.小結：
對於插入排序，還想多說一句，插入排序雖然時間復雜度是O(n^2)，但是在一定的場合，它的效率非常高。比如，在一個基本上有序的序列中，只有那麼幾個數，它的順序不對，那麼這時候，插入排序的效率非常高
1.希爾排序是插入排序一個強力改進版，思路是：
先將整個待排元素序列分割成若干個子序列（由相隔某個“增量”的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序。
因為直接插入排序在元素基本有序的情況下（接近最好情況），效率是很高的，因此希爾排序在時間效率上比前兩種方法有較大提高。
2.實現：
public void sort(int[] arr) {
int n = arr.length;
int h = 1;
while (h < n / 3) {
h = 3 * h + 1;
}
// 計算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
while (h >= 1) {
// h-sort the array
for (int i = h; i < n; i++) {
// 對 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
int e = arr[i];
int j;
for (j = i; j >= h && e < arr[j - h]; j -= h) {
arr[j] = arr[j - h];
}
arr[j] = e;
}
h /= 3;
}
}
