快速排序的些許總結(jié)(JAVA)

前言


最近不太忙,有空oj上刷刷水題物舒,遇到幾道排序題目,鄙人習慣用java語言戏锹,也深知很多直接用java封裝好的sort函數(shù)能夠直接解決問題冠胯。但所謂飲水思源,項目之外锦针,還是應該多多關(guān)注眾多排序算法的內(nèi)部細節(jié)荠察。就先總結(jié)平均效率最高的快速排序算法吧。

特點


平均效率最高奈搜,但不穩(wěn)定悉盆。平均時間復雜度o(nlogn),最壞時間復雜度o(n^2)。

思路(升序)


快速排序基于比較和分治馋吗,核心是先讓一個元素找準其位置焕盟,使其左邊的元素都不比它大,右邊的元素都不比它小宏粤。然后再使其左邊集合和右邊集合都遞歸下去脚翘,直到最終有序。

方法


  1. 選取一個基準(參照物)绍哎,默認選擇第一個元素(當然選擇其他元素也可以)来农。并確定兩個游標,左游標和右游標蛇摸。
  2. 右游標從右到左掃描备图,若發(fā)現(xiàn)一個小于基準的元素,停止掃描赶袄,將該元素賦值到基準位置揽涮,同時新的基準位置調(diào)整到該元素原來位置。倘若沒發(fā)現(xiàn)饿肺,則當左右游標重合時停止掃描蒋困。
  3. 左游標從左向右掃描,若發(fā)現(xiàn)一個大于基準的元素敬辣,停止掃描雪标,將該元素賦值到基準位置,同時新的基準位置調(diào)整到該元素原來位置溉跃。倘若沒發(fā)現(xiàn)村刨,則當左右游標重合時停止掃描。
  4. 2和3一直進行撰茎,直到左右游標重合嵌牺,即基準已找到其位置,將基準值賦值到游標重合位置。
  5. 雖然已經(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)于其他排序的党涕。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市巡社,隨后出現(xiàn)的幾起案子膛堤,更是在濱河造成了極大的恐慌,老刑警劉巖晌该,帶你破解...
    沈念sama閱讀 216,324評論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件肥荔,死亡現(xiàn)場離奇詭異,居然都是意外死亡朝群,警方通過查閱死者的電腦和手機燕耿,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,356評論 3 392
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來姜胖,“玉大人誉帅,你說我怎么就攤上這事。” “怎么了堵第?”我有些...
    開封第一講書人閱讀 162,328評論 0 353
  • 文/不壞的土叔 我叫張陵吧凉,是天一觀的道長。 經(jīng)常有香客問我踏志,道長阀捅,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,147評論 1 292
  • 正文 為了忘掉前任针余,我火速辦了婚禮饲鄙,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘圆雁。我一直安慰自己忍级,他們只是感情好,可當我...
    茶點故事閱讀 67,160評論 6 388
  • 文/花漫 我一把揭開白布伪朽。 她就那樣靜靜地躺著轴咱,像睡著了一般。 火紅的嫁衣襯著肌膚如雪烈涮。 梳的紋絲不亂的頭發(fā)上朴肺,一...
    開封第一講書人閱讀 51,115評論 1 296
  • 那天,我揣著相機與錄音坚洽,去河邊找鬼戈稿。 笑死,一個胖子當著我的面吹牛讶舰,可吹牛的內(nèi)容都是我干的鞍盗。 我是一名探鬼主播,決...
    沈念sama閱讀 40,025評論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼跳昼,長吁一口氣:“原來是場噩夢啊……” “哼般甲!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起庐舟,我...
    開封第一講書人閱讀 38,867評論 0 274
  • 序言:老撾萬榮一對情侶失蹤欣除,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后挪略,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體历帚,經(jīng)...
    沈念sama閱讀 45,307評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,528評論 2 332
  • 正文 我和宋清朗相戀三年杠娱,在試婚紗的時候發(fā)現(xiàn)自己被綠了挽牢。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,688評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡摊求,死狀恐怖禽拔,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情,我是刑警寧澤睹栖,帶...
    沈念sama閱讀 35,409評論 5 343
  • 正文 年R本政府宣布硫惕,位于F島的核電站,受9級特大地震影響野来,放射性物質(zhì)發(fā)生泄漏恼除。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,001評論 3 325
  • 文/蒙蒙 一曼氛、第九天 我趴在偏房一處隱蔽的房頂上張望豁辉。 院中可真熱鬧,春花似錦舀患、人聲如沸徽级。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,657評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽餐抢。三九已至,卻和暖如春狗超,著一層夾襖步出監(jiān)牢的瞬間弹澎,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,811評論 1 268
  • 我被黑心中介騙來泰國打工努咐, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人殴胧。 一個月前我還...
    沈念sama閱讀 47,685評論 2 368
  • 正文 我出身青樓渗稍,卻偏偏與公主長得像,于是被迫代替她去往敵國和親团滥。 傳聞我的和親對象是個殘疾皇子竿屹,可洞房花燭夜當晚...
    茶點故事閱讀 44,573評論 2 353

推薦閱讀更多精彩內(nèi)容

  • 概述 排序有內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序灸姊,而外部排序是因排序的數(shù)據(jù)很大拱燃,一次不能容納全部...
    蟻前閱讀 5,183評論 0 52
  • 作者:大海里的太陽原文地址:http://www.cnblogs.com/wxisme/ 前言 查找和排序算法是算...
    IT程序獅閱讀 2,498評論 0 63
  • 概述排序有內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進行排序力惯,而外部排序是因排序的數(shù)據(jù)很大碗誉,一次不能容納全部的...
    Luc_閱讀 2,270評論 0 35
  • 前幾天在碼農(nóng)網(wǎng)看到了一篇文章,關(guān)于講objective-c的幾種排序算法的圖形化操作方式父晶,自己也寫了一份代碼溫習下...
    happyte閱讀 729評論 0 5
  • “在北風呼嘯的雪山上整個大地被白雪蓋住在這個深不見底的懸崖上一只通體白色的大狼站在那里哮缺,他有一米高,長兩米甲喝,全身都...
    花殘之夏閱讀 234評論 0 0