最近，在通過(guò)《算法4》這本書(shū)來(lái)重新學(xué)習(xí)一下算法，從最初級(jí)的排序算法翩伪。初級(jí)的排序算法有3種：選擇排序微猖、插入排序、希爾排序缘屹。
選擇排序
假定我們有一組沒(méi)有順序的數(shù)組凛剥，如{5,8,1,7,3,9,4,6}。那么轻姿，選擇排序是這樣的：
1犁珠、找到這個(gè)數(shù)組中最小的元素，然后與第一個(gè)元素交換互亮；
2犁享、在剩下的元素中找到最小的元素，與第二個(gè)元素交換豹休；
如此重復(fù)炊昆，直至整個(gè)數(shù)組中的所有元素都按順序排列，這樣的方法就被稱為選擇排序威根。
簡(jiǎn)單排序如果用java來(lái)實(shí)現(xiàn)的話是這樣的凤巨。
選擇排序
pubic class Selection{
????????public static void sort(int[] numbers){
????????????????int length = numbers.length;
????????????????for(int i = 0; i < N; i++){
? ? ? ? ? ? ? ??????????int min = i;????//最小的數(shù)從第i位開(kāi)始排起
????????????????????????for(int j = i+1; j < N ; j++){
????????????????????????????????//循環(huán)判斷，獲取最小的數(shù)值的下標(biāo)
????????????????????????????????if(numbers[min] > numbers[j]){
????????????????????????????????????????min = j;
????????????????????????????????}
????????????????????????}
????????????????????????//更換最小值的位置
????????????????????????int t = numbers[i];
????????????????????????numbers[i] ?= numbers[min];
????????????????????????numbers[min] = t;
????????????????}
????????? ? //打印出重新排序后的數(shù)值
????????????for(int i : numbers)
????????????????????System.out.print(i + " ");?
????????}
}
其實(shí)洛搀，這和我們用眼睛在一堆數(shù)字里面找最小值沒(méi)什么區(qū)別敢茁，而這個(gè)算法只是把找的步驟完整的復(fù)述出來(lái)而已。
插入排序
玩過(guò)撲克牌的知道留美，每一次抽牌彰檬，我們都會(huì)把牌插入手里牌組中合適的位置。而在計(jì)算機(jī)中独榴，每次數(shù)據(jù)要插入的時(shí)候僧叉，都得先移動(dòng)一下已有的數(shù)據(jù)，騰出一個(gè)空間來(lái)給這個(gè)數(shù)據(jù)插入棺榔。比如瓶堕，在一個(gè)有序的數(shù)據(jù)集【1，5症歇，8郎笆，15】中，要插入【6】忘晤，我們可以直觀的看出是插入在5和8之間宛蚓。但是，在計(jì)算機(jī)中设塔，它是一個(gè)固定數(shù)組凄吏，由固定的4個(gè)空間存放這四個(gè)數(shù)字，如果要插入6，就必須把8和15往后移動(dòng)一個(gè)空間痕钢，騰出來(lái)的位置才能插入6图柏。
從這里可以看出，每一次的插入排序其實(shí)是把拿到的數(shù)字去與已經(jīng)排好順序的數(shù)組（即使一開(kāi)始沒(méi)有排好序的數(shù)組也不影響）進(jìn)行對(duì)比任连，然后把它插入到合適的順序中蚤吹。
用代碼說(shuō)事
插入排序
public?void?insertionSort(){??
??????int[ ] a = new int[ ]{3,6,9,1,5,2,8};
? ? ??int?len?=?a.length; ?
???????for(int?i=1;i<len;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+" ");
??????}
???}?
首先，第一個(gè)數(shù)不進(jìn)行排序随抠，從第二個(gè)數(shù)開(kāi)始裁着，當(dāng)這個(gè)數(shù)小于它的前一個(gè)數(shù)時(shí)，則兩個(gè)數(shù)交換位置拱她。交換完后通過(guò)j--繼續(xù)與前一個(gè)數(shù)進(jìn)行比較二驰，直至找到合適的位置。然后再用第三個(gè)數(shù)進(jìn)行比較椭懊，直接全部排序完诸蚕。這樣就通過(guò)插入排序得到了一個(gè)從小到大的數(shù)組步势。
因?yàn)椴迦肱判蛎看沃荒鼙容^合交換相鄰的兩個(gè)數(shù)字氧猬，如果數(shù)據(jù)規(guī)模過(guò)大的話，效率就顯得很低了坏瘩。
希爾排序
希爾排序是在插入排序的基礎(chǔ)上做一定改進(jìn)來(lái)加快排序的速度盅抚。
希爾排序
public class Shell{
????public static void sort(Comparable[] a){
????????int N = a.length;
????????int h = 1;
????????//通過(guò)不斷除以3，得到一個(gè)比N/3略大的數(shù) 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;
????????}
????}
}
希爾排序本質(zhì)上還是插入排序倔矾，區(qū)別在于希爾排序一開(kāi)始是把整個(gè)數(shù)組分成了若干份（這若干份數(shù)組中的元素在整個(gè)大數(shù)組中是間隔的妄均，間隔距離是h），對(duì)這若干份先一一進(jìn)行排序哪自，然后再重新分成更少的若干份丰包，再進(jìn)行排序，直到最后只剩下一份壤巷，也就是整個(gè)數(shù)組時(shí)邑彪，這時(shí)候整個(gè)數(shù)組的排序已經(jīng)接近我們想要的排序了，進(jìn)行一次插入排序胧华，需要移動(dòng)的元素就很少了寄症。相對(duì)來(lái)說(shuō)，也就比直接使用插入排序會(huì)高效很多矩动。
