QuickSort GoOver 1

QuickSort排序過程(正序氧吐,左往右迅细,小到大):

原始 int 數(shù)組 p:
下標(biāo) 0 1 2 3 4 5 6 7 8 9
數(shù)字 6 1 5 8 7 6 4 5 2 4

i=0,j=9,k=p[i]=6(第0個(gè)數(shù)值:6)喜庞。

1. p[j] 往前匹配小于 k 的 p[j] , j=9 時(shí)株搔,p[j] = 4<k (k=6), 將 p[j] 和 [pi] 的位置對調(diào)别洪;
下標(biāo) 0 1 2 3 4 5 6 7 8 9
數(shù)字 4 1 5 8 7 6 4 5 2 6
2. p[i] 往后匹配, i=3, p[i] = 8>k (k=6),將當(dāng)前 p[i] 和 p[j] 的位置對調(diào),此時(shí) i=3, j=9携栋;
下標(biāo) 0 1 2 3 4 5 6 7 8 6
數(shù)字 4 1 5 6 7 6 4 5 2 8
3. 重復(fù)步驟1和步驟2,直到i和j碰頭停止匹配 完成一輪排序搭盾,第一輪排序過后數(shù)組順序?yàn)椋?/h6>
下標(biāo) 0 1 2 3 4 5 6 7 8 9
數(shù)字 4 1 5 2 5 6 4 6 7 8
4. 此時(shí)i=j=7以k為分界點(diǎn),左邊是小于等于k的數(shù)的集合,右邊是大于等于k的數(shù)的集合婉支,將這兩個(gè)集合分開按照1-4的步驟排序直到產(chǎn)生的子集數(shù)的元素?cái)?shù)量小于等于1個(gè)鸯隅,整個(gè)排序結(jié)束,得到排序后的結(jié)果。
下標(biāo) 0 1 2 3 4 5 6 7 8 9
數(shù)字 1 2 4 4 5 5 6 6 7 8

C#實(shí)現(xiàn):

public class QuickSort
{
    public List<int> list = null;
    public QuickSort(List<int> l)
    {
        list = l;
    }
    //從小到大排序
    public void qs(int l, int r)
    {
        int i = l;
        int j = r;
        if (i >= j)//如果當(dāng)前排序集合里面的元素個(gè)數(shù)小于2個(gè)則結(jié)束此分支的排序
        {
            return;
        }
        int key = list[i];//以集合第一個(gè)元素作為界定值
        while (i < j)//排序
        {
            while (i < j && list[j] >= key)//從后往前匹配第一個(gè)小于界定值key的值
            {
                j--;
            }
            list[i] = list[j];//將當(dāng)前j位置的值放到i處
            while (i < j && list[i] <= key)//從前往后匹配第一個(gè)大于界定值key的值
            {
                i++;
            }
            list[j] = list[i];//將當(dāng)前i位置的值放到j(luò)處
        }
        list[i] = key;//這里完成
        //以key為分界將數(shù)字集合分成兩個(gè)集合 遞歸進(jìn)行下一輪排序
        qs(l, i - 1);//小于等于key部分
        qs(i + 1, r);//大于等于key部分
    }
}

這里是單線程蝌以,用遞歸來切入下一輪排序炕舵,用公共的集合比以參數(shù)的形式將集合傳入會節(jié)省點(diǎn)內(nèi)存。

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末跟畅,一起剝皮案震驚了整個(gè)濱河市咽筋,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌徊件,老刑警劉巖奸攻,帶你破解...
    沈念sama閱讀 217,406評論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異虱痕,居然都是意外死亡睹耐,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,732評論 3 393
  • 文/潘曉璐 我一進(jìn)店門部翘,熙熙樓的掌柜王于貴愁眉苦臉地迎上來硝训,“玉大人,你說我怎么就攤上這事新思〗蚜海” “怎么了?”我有些...
    開封第一講書人閱讀 163,711評論 0 353
  • 文/不壞的土叔 我叫張陵夹囚,是天一觀的道長纵刘。 經(jīng)常有香客問我,道長崔兴,這世上最難降的妖魔是什么彰导? 我笑而不...
    開封第一講書人閱讀 58,380評論 1 293
  • 正文 為了忘掉前任蛔翅,我火速辦了婚禮敲茄,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘山析。我一直安慰自己堰燎,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,432評論 6 392
  • 文/花漫 我一把揭開白布笋轨。 她就那樣靜靜地躺著秆剪,像睡著了一般。 火紅的嫁衣襯著肌膚如雪爵政。 梳的紋絲不亂的頭發(fā)上仅讽,一...
    開封第一講書人閱讀 51,301評論 1 301
  • 那天,我揣著相機(jī)與錄音钾挟,去河邊找鬼洁灵。 笑死,一個(gè)胖子當(dāng)著我的面吹牛掺出,可吹牛的內(nèi)容都是我干的徽千。 我是一名探鬼主播苫费,決...
    沈念sama閱讀 40,145評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼双抽!你這毒婦竟也來了百框?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,008評論 0 276
  • 序言:老撾萬榮一對情侶失蹤牍汹,失蹤者是張志新(化名)和其女友劉穎铐维,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體柑贞,經(jīng)...
    沈念sama閱讀 45,443評論 1 314
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡方椎,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,649評論 3 334
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了钧嘶。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片棠众。...
    茶點(diǎn)故事閱讀 39,795評論 1 347
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖有决,靈堂內(nèi)的尸體忽然破棺而出闸拿,到底是詐尸還是另有隱情,我是刑警寧澤书幕,帶...
    沈念sama閱讀 35,501評論 5 345
  • 正文 年R本政府宣布新荤,位于F島的核電站,受9級特大地震影響台汇,放射性物質(zhì)發(fā)生泄漏苛骨。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,119評論 3 328
  • 文/蒙蒙 一苟呐、第九天 我趴在偏房一處隱蔽的房頂上張望痒芝。 院中可真熱鬧,春花似錦牵素、人聲如沸严衬。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,731評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽请琳。三九已至,卻和暖如春赠幕,著一層夾襖步出監(jiān)牢的瞬間俄精,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,865評論 1 269
  • 我被黑心中介騙來泰國打工榕堰, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留竖慧,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,899評論 2 370
  • 正文 我出身青樓,卻偏偏與公主長得像测蘑,于是被迫代替她去往敵國和親灌危。 傳聞我的和親對象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,724評論 2 354

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