最近,在通過《算法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),對這若干份先一一進行排序,然後再重新分成更少的若干份,再進行排序,直到最後只剩下一份,也就是整個數組時,這時候整個數組的排序已經接近我們想要的排序了,進行一次插入排序,需要移動的元素就很少了。相對來說,也就比直接使用插入排序會高效很多。
閱讀更多 拿渣仨泰舉 的文章