最近，在通過《算法4》這本書來重新學習一下算法，從最初級的排序算法。初級的排序算法有3種：選擇排序、插入排序、希爾排序。
選擇排序
假定我們有一組沒有順序的數組，如{5,8,1,7,3,9,4,6}。那麼，選擇排序是這樣的：
1、找到這個數組中最小的元素，然後與第一個元素交換；
2、在剩下的元素中找到最小的元素，與第二個元素交換；
如此重複，直至整個數組中的所有元素都按順序排列，這樣的方法就被稱為選擇排序。
簡單排序如果用java來實現的話是這樣的。(編輯器的原因，代碼顯示的格式可能會有混亂，可以拷貝到開發工具中重新排序下即可)
選擇排序
pubic class Selection{
public static void sort(int[] numbers){
int length = numbers.length;
for(int i = 0; i < N; i++){
int min = i; //最小的數從第i位開始排起
for(int j = i+1; j < N ; j++){
//循環判斷，獲取最小的數值的下標
if(numbers[min] > numbers[j]){
min = j;
}
}
//更換最小值的位置
int t = numbers[i];
numbers[i] = numbers[min];
numbers[min] = t;
}
//打印出重新排序後的數值
for(int i : numbers)
System.out.print(i + " ");
}
}
其實，這和我們用眼睛在一堆數字裡面找最小值沒什麼區別，而這個算法只是把找的步驟完整的複述出來而已。
插入排序
玩過撲克牌的知道，每一次抽牌，我們都會把牌插入手裡牌組中合適的位置。而在計算機中，每次數據要插入的時候，都得先移動一下已有的數據，騰出一個空間來給這個數據插入。比如，在一個有序的數據集【1，5，8，15】中，要插入【6】，我們可以直觀的看出是插入在5和8之間。但是，在計算機中，它是一個固定數組，由固定的4個空間存放這四個數字，如果要插入6，就必須把8和15往後移動一個空間，騰出來的位置才能插入6。
從這裡可以看出，每一次的插入排序其實是把拿到的數字去與已經排好順序的數組（即使一開始沒有排好序的數組也不影響）進行對比，然後把它插入到合適的順序中。
用代碼說事
插入排序
public void insertionSort(){
int[ ] a = new int[ ]{3,6,9,1,5,2,8};
int len = a.length;
for(int i=1;i for(int j=i; j>0 && a[j] < a[j-1]; j--){ int k = a[j]; a[j] = a[j-1]; a[j-1] = k; } } for(int b : a){ System.out.print(b+" "); } }
首先，第一個數不進行排序，從第二個數開始，當這個數小於它的前一個數時，則兩個數交換位置。交換完後通過j--繼續與前一個數進行比較，直至找到合適的位置。然後再用第三個數進行比較，直接全部排序完。這樣就通過插入排序得到了一個從小到大的數組。
因為插入排序每次只能比較合交換相鄰的兩個數字，如果數據規模過大的話，效率就顯得很低了。
希爾排序
希爾排序是在插入排序的基礎上做一定改進來加快排序的速度。
希爾排序
public class Shell{
public static void sort(Comparable[] a){
int N = a.length;
int h = 1;
//通過不斷除以3，得到一個比N/3略大的數 h
while(h < N/3){
h = 3 * h + 1;
}
while(h >= 1){
for(int i = h;i < N ; i++){
for(int j = i ;j >= h && a[j] < a[j-h]; j -= h){
int k = a[j];
a[j] = a[j-h];
a[j-h] = k;
}
}
h = h/3;
}
}
}
希爾排序本質上還是插入排序，區別在於希爾排序一開始是把整個數組分成了若干份（這若干份數組中的元素在整個大數組中是間隔的，間隔距離是h），對這若干份先一一進行排序，然後再重新分成更少的若干份，再進行排序，直到最後只剩下一份，也就是整個數組時，這時候整個數組的排序已經接近我們想要的排序了，進行一次插入排序，需要移動的元素就很少了。相對來說，也就比直接使用插入排序會高效很多。
閱讀更多 拿渣仨泰舉 的文章
