前言
快速排序作為排序算法的王者,我們沒有理由不掌握它
快速排序的基本思想:
通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹?其中一部分記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小,則可分別對這兩部分記錄繼續(xù)進行排序,以達到整個序列有序的目的.快速排序的快速理解:
把數(shù)據(jù)分成左右兩部分,左邊的所有數(shù)據(jù)都比右邊數(shù)據(jù)小, 再把左右兩部分的數(shù)據(jù)按同樣的方法排序. 很明顯快速排序是不穩(wěn)定的,排序的結(jié)果次序可能不一致.
舉例分析
int s[] = {52,78,12,99,5,18,80,32,66};
畫了一張很簡單的圖, 力求簡單.每個格子想象成一個待挖的坑.
第一步: 我們先隨便從數(shù)組中拿一個數(shù)據(jù)作為基準數(shù)p.便于演示,就用s[0] 吧,即p=s[0] . 注意,我們在s[0]處拿了一個數(shù)據(jù),我們就想象從數(shù)組s中挖了一個坑,而且這個坑的位置就是s[0],下面我們來看看如何填坑
第二步:找 s[k] < p :從索引K的結(jié)尾處開始向前找. 找比s[0] (即p)小的數(shù).如圖中的綠色箭頭方向,標號①表示綠色查找優(yōu)先紅色查找,很明顯s[7]=32 < s[0]=52 , 此時我們把32挖出來去填s[0]的坑, 讓s[0]=s[7] , 所以此時s[0]為32,就是說我們把第一個坑填了. 但是有一個新坑k[7],此時的數(shù)據(jù)順序:
32,78,12,99,5,18,80,32,66
第三步:找 s[i] > p :從索引 i 的開始處從前向后找.找比s[0] (即p)大的數(shù).如圖中的紅色箭頭方向.我們看到 s[1] = 78 > p=52 .所以我們挖出s[1]的數(shù)據(jù)放到上一步的坑中,就是k[7]了.此時我們的新坑i[1] , 讓 s[7]=s[1],此時的數(shù)據(jù)順序:
32,78,12,99,5,18,80,78,66
我們在第二步中得到了K=7,在第三步中得到了i=1.那么在下一輪的查找中k從6開始,然后i從2開始.這樣重復(fù)執(zhí)行第二步然后第三步,直到 i = k . 這樣就完成了左邊的數(shù)據(jù)都是小于右邊的數(shù).之后用同樣的方法從第一步開始分別對左右部分的數(shù)據(jù)進行排序,得到的就是最終的結(jié)果
Java代碼示例
原理講完了,我們來擼一下java的實現(xiàn).
public void quickSort(int arr[],int sIndex,int eIndex){
if (sIndex < eIndex) {
int p = arr[sIndex] , i = sIndex , k = eIndex;
while (i < k) {
while(i < k && arr[k] >= p) // 從右向左找
k--;
if (i < k ) arr[i++] = arr[k];
while(i < k && arr[i] < p) // 從左向右找
i++;
if (i < k ) arr[k--] = arr[i];
}
arr[i] = p;
quickSort(arr, sIndex, i - 1); // 遞歸
quickSort(arr, i + 1, eIndex);
}
}
結(jié)束
快速排序還有很多優(yōu)化版本,但是基本思想都是類似的,很大程度上取決P的選擇,比如如果P處于數(shù)列的中間,那么就趨于平衡樹,效率會提高.總的來說,快速排序名副其實,我們應(yīng)該好好學(xué)習它.謝謝大家!
