前言
最近不太忙,有空oj上刷刷水題物舒,遇到幾道排序題目,鄙人習慣用java語言戏锹,也深知很多直接用java封裝好的sort函數(shù)能夠直接解決問題冠胯。但所謂飲水思源,項目之外锦针,還是應該多多關(guān)注眾多排序算法的內(nèi)部細節(jié)荠察。就先總結(jié)平均效率最高的快速排序算法吧。
特點
平均效率最高奈搜,但不穩(wěn)定悉盆。平均時間復雜度o(nlogn),最壞時間復雜度o(n^2)。
思路(升序)
快速排序基于比較和分治馋吗,核心是先讓一個元素找準其位置焕盟,使其左邊的元素都不比它大,右邊的元素都不比它小宏粤。然后再使其左邊集合和右邊集合都遞歸下去脚翘,直到最終有序。
方法
- 選取一個基準(參照物)绍哎,默認選擇第一個元素(當然選擇其他元素也可以)来农。并確定兩個游標,左游標和右游標蛇摸。
- 右游標從右到左掃描备图,若發(fā)現(xiàn)一個小于基準的元素,停止掃描赶袄,將該元素賦值到基準位置揽涮,同時新的基準位置調(diào)整到該元素原來位置。倘若沒發(fā)現(xiàn)饿肺,則當左右游標重合時停止掃描蒋困。
- 左游標從左向右掃描,若發(fā)現(xiàn)一個大于基準的元素敬辣,停止掃描雪标,將該元素賦值到基準位置,同時新的基準位置調(diào)整到該元素原來位置溉跃。倘若沒發(fā)現(xiàn)村刨,則當左右游標重合時停止掃描。
- 2和3一直進行撰茎,直到左右游標重合嵌牺,即基準已找到其位置,將基準值賦值到游標重合位置。
- 雖然已經(jīng)確定了基準的位置逆粹,但總體來看并不一定是有序的募疮,則還需要對其左邊集合和右邊集合分別進行排序,使用遞歸即可僻弹。
例子
代碼實現(xiàn)
public static void quickSort(int a[],int l, int r) {
if(l < r) {
int s = a[l]; //基準
int i = l; //左游標
int j = r; //右游標
while(i < j) {
//從右向左掃描阿浓,當左右游標重合或者掃描到小于基準的值時掃描停止
while(i < j && a[j] > s) {
j--;
}
//將小于基準的值賦值到基準位,右游標位置為新的基準位
a[i] = a[j];
//從左向右掃描蹋绽,當左右游標重合或者掃描到大于基準的值時掃描停止
while(i < j && a[i] < s) {
i++;
}
//將大于基準的值賦值到基準位芭毙,左游標位置為新的基準位
a[j] = a[i];
}
//左右游標重合,基準值的最終位確定
a[j] = s;
//對左邊部分遞歸
quickSort(a,l,i-1);
//對右邊部分遞歸
quickSort(a,j+1,r);
}
}
這是升序的實現(xiàn)蟋字,如要排成降序稿蹲,可在掃描時改變判斷方向扭勉,即從右到左找大于基準的鹊奖,從左到右找小于基準的。很容易實現(xiàn)涂炎,這里就不多說了忠聚。
結(jié)語
根據(jù)快速排序的算法可以知道,快速排序并非在任何情況都是最優(yōu)的唱捣,比如說當集合是有序的時候两蟀,基準選到了最大或者最小的元素,這樣每次只能定一個元素的位置震缭,就等于冒泡排序了赂毯,時間復雜度變成了o(n^2)。不過絕大數(shù)情形拣宰,快速排序是優(yōu)于其他排序的党涕。