重拾算法Day03-快速排序

快速排序基本思想

以 6 1 2 7 9 3 4 5 10 8 按從小到大排序 為例進(jìn)行說明:

  1. 以6為基準(zhǔn),小于6的放在6的左邊轧钓,大于6的放在6的右邊序厉。
  2. 設(shè)置兩個(gè)標(biāo)志器i=0, j=9; i在數(shù)組的最左邊,j在數(shù)組的最右邊毕箍。
  3. j先動(dòng)脂矫,依次比較a[j]<6,如果不成立霉晕,j--; 如果成立則j停止庭再。如果j<i,停止牺堰。
  4. i再動(dòng)拄轻,依次比較a[i]>6, 如果不成立,i++伟葫;如果成立i停止恨搓。如果j<i,停止筏养。
  5. 如果i=j,就將6與a[j]進(jìn)行交換斧抱。
    如此進(jìn)行一輪:等到的結(jié)果是
    3 1 2 5 4 6 9 7 10 8
    6 左邊的都小于6,6右邊的都大于6渐溶。
    然后再排序 3 1 2 5 4
    然后再排序 9 7 10 8

代碼實(shí)現(xiàn)

#include <stdio.h>
int a[100];
int n;

void quicksort(int left, int right)
{
    if (left >= right) {
        return;
    }
    int i, j;
    i=left;
    j=right;
    int temp = a[left]; //基準(zhǔn)數(shù)據(jù)
    while (i!=j) {
        while (a[j]>=temp && j>i) {
            j--;
        }
        while (a[i]<=temp && j>i) {
            i++;
        }
        
        if (i<j) {
            int k = a[i];
            a[i] = a[j];
            a[j] = k;
        }
        
    }
    
    a[left] = a[i];
    a[i] = temp;
    
    quicksort(left, i-1);
    quicksort(i+1, right);
    
    return;
}

int main(int argc, const char * argv[]) {
    // insert code here...
    
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }
    
    quicksort(0, n-1);
    for (int i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    
    return 0;
}

總結(jié)

快速排序之所以比較快辉浦,因?yàn)橄啾让芭菖判颍看谓粨Q都是跳躍式的茎辐。每次排序都設(shè)置一個(gè)基準(zhǔn)點(diǎn)宪郊,將小于等于基準(zhǔn)點(diǎn)的數(shù)全部放在基準(zhǔn)點(diǎn)的左邊掂恕,將大于等于基準(zhǔn)點(diǎn)的數(shù)全部放在基準(zhǔn)點(diǎn)的右邊。這樣在每次交換的時(shí)候就不會(huì)像冒泡排序一樣只能在相鄰的數(shù)之間進(jìn)行交換弛槐。交換的距離也大得多了懊亡。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市乎串,隨后出現(xiàn)的幾起案子店枣,更是在濱河造成了極大的恐慌,老刑警劉巖叹誉,帶你破解...
    沈念sama閱讀 223,002評論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件艰争,死亡現(xiàn)場離奇詭異,居然都是意外死亡桂对,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評論 3 400
  • 文/潘曉璐 我一進(jìn)店門鸠匀,熙熙樓的掌柜王于貴愁眉苦臉地迎上來蕉斜,“玉大人,你說我怎么就攤上這事缀棍≌耍” “怎么了?”我有些...
    開封第一講書人閱讀 169,787評論 0 365
  • 文/不壞的土叔 我叫張陵爬范,是天一觀的道長父腕。 經(jīng)常有香客問我,道長青瀑,這世上最難降的妖魔是什么璧亮? 我笑而不...
    開封第一講書人閱讀 60,237評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮斥难,結(jié)果婚禮上枝嘶,老公的妹妹穿的比我還像新娘。我一直安慰自己哑诊,他們只是感情好群扶,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著镀裤,像睡著了一般竞阐。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上暑劝,一...
    開封第一講書人閱讀 52,821評論 1 314
  • 那天骆莹,我揣著相機(jī)與錄音,去河邊找鬼担猛。 笑死汪疮,一個(gè)胖子當(dāng)著我的面吹牛峭火,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播智嚷,決...
    沈念sama閱讀 41,236評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼卖丸,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了盏道?” 一聲冷哼從身側(cè)響起稍浆,我...
    開封第一講書人閱讀 40,196評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎猜嘱,沒想到半個(gè)月后衅枫,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,716評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡朗伶,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評論 3 343
  • 正文 我和宋清朗相戀三年弦撩,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片论皆。...
    茶點(diǎn)故事閱讀 40,928評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡益楼,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出点晴,到底是詐尸還是另有隱情感凤,我是刑警寧澤,帶...
    沈念sama閱讀 36,583評論 5 351
  • 正文 年R本政府宣布粒督,位于F島的核電站陪竿,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏屠橄。R本人自食惡果不足惜族跛,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望锐墙。 院中可真熱鬧庸蔼,春花似錦、人聲如沸贮匕。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽刻盐。三九已至掏膏,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間敦锌,已是汗流浹背馒疹。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留乙墙,地道東北人颖变。 一個(gè)月前我還...
    沈念sama閱讀 49,378評論 3 379
  • 正文 我出身青樓生均,卻偏偏與公主長得像,于是被迫代替她去往敵國和親腥刹。 傳聞我的和親對象是個(gè)殘疾皇子马胧,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評論 2 361

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

  • 概述 排序有內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序衔峰,而外部排序是因排序的數(shù)據(jù)很大佩脊,一次不能容納全部...
    蟻前閱讀 5,191評論 0 52
  • 概述:排序有內(nèi)部排序和外部排序,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序垫卤,而外部排序是因排序的數(shù)據(jù)很大威彰,一次不能容納全部...
    每天刷兩次牙閱讀 3,733評論 0 15
  • quicksort可以說是應(yīng)用最廣泛的排序算法之一,它的基本思想是分治法穴肘,選擇一個(gè)pivot(中軸點(diǎn))歇盼,將小于pi...
    黎景陽閱讀 449評論 0 1
  • 半夜睡不著,早上又早早的自然醒评抚。像個(gè)有心事的失眠人豹缀,卻滿腦子放空。 坐著發(fā)呆盈咳,想到一個(gè)詞:虛度光陰”咭恚回來后整日的無...
    禾必閱讀 123評論 0 0
  • 一 弟弟的房子交房了组底,他興奮地準(zhǔn)備裝修丈积,目標(biāo)明確:要裝成樣板房那樣。當(dāng)初看到樣板房债鸡,他眼前一亮江滨,這是他夢想中的家。...
    王月冰閱讀 560評論 0 3