quick sort 問題

用quick sort 排列下面的數列...

[26 5 37 1 61 11 59 15 48 19 ]

第一階段後會變成

[11 5 19 1 15] 26 [59 61 48 37 ]

我知道quick sort的定義是把比標記數小的移到左邊,反之移到右邊

那請問為什麼左邊的數會這樣排列呢?是照什麼順序取的?

Update:

那再請問一下 4,2,6,5,1,7,3,8用quick sort排序

經過第一階段之後結果是什麼?

我拿到的答案是12345678...

怎麼覺得不正確= ="

Update 2:

IRA大大要不要用回答?

因為意見沒辦法選最佳解答....

1 Answer

Rating
  • ?
    Lv 4
    1 decade ago
    Favorite Answer

    其實精神在於以基準點分大小然後切割問題再處理...

    >>左邊的數會這樣排列呢?

    基本上你要怎麼排列都沒差,但要全都比基準點小.

    [26 5 37 1 61 11 59 15 48 19 ]

    我喜歡也可以

    [5 1 11 15 19]26[37 61 59 48]

    (直覺的掃過去...但是這負擔會大一點.但不影響時間複雜度等級)

    為何會這樣?這跟程式撰寫時不想做額外的運算有關...儘量節省運算量.

    2006-09-30 18:06:20 補充:

    過程打給你...

    [26 5 *37 1 61 11 59 15 48 *19 ]

    [26 5 19 1 *61 11 59 *15 48 37 ]

    [26 5 19 1 15 *11 *59 61 48 37 ]

    [26 5 19 1 15 **11 *59 61 48 37 ]

    [11 5 19 1 15] 26 [59 61 48 37 ]

    2006-10-01 04:06:52 補充:

    [4,2,6,5,1,7,3,8]

    pivot is 4!

    [4,2,(L)6,5,1,7,(S)3,8]

    [4,2,3,(L)5,(S)1,7,6,8]

    [4,2,3,(S)1,(L)5,7,6,8]

    [1,2,3],4,[5,7,6,8]

    我不喜歡那套什麼制式化寫法寫出課本中quick sort演算法的第一階段後排序結果...那是不具任何意義.那只能拿來應付考試而已.

    上面就是一個很制式化的回答.

    2006-10-04 07:44:35 補充:

    其實精神在於以基準點分大小然後切割問題再處理...

    >>左邊的數會這樣排列呢?

    基本上你要怎麼排列都沒差,但要全都比基準點小.

    [26 5 37 1 61 11 59 15 48 19 ]

    我喜歡也可以

    [5 1 11 15 19]26[37 61 59 48]

    (直覺的掃過去...但是這負擔會大一點.但不影響時間複雜度等級)

    為何會這樣?這跟程式撰寫時不想做額外的運算有關...儘量節省運算量.

    過程打給你...

    [26 5 *37 1 61 11 59 15 48 *19 ]

    [26 5 19 1 *61 11 59 *15 48 37 ]

    [26 5 19 1 15 *11 *59 61 48 37 ]

    [26 5 19 1 15 **11 *59 61 48 37 ]

    [11 5 19 1 15] 26 [59 61 48 37 ]

    [4,2,6,5,1,7,3,8]

    pivot is 4!

    [4,2,(L)6,5,1,7,(S)3,8]

    [4,2,3,(L)5,(S)1,7,6,8]

    [4,2,3,(S)1,(L)5,7,6,8]

    [1,2,3],4,[5,7,6,8]

    我不喜歡那套什麼制式化寫法寫出課本中quick sort演算法的第一階段後排序結果...那是不具任何意義.那只能拿來應付考試而已.

    上面就是一個很制式化的回答.

    恩....我應該不算啥大大...

    我只是給個意見...大家喜歡而且覺得可以接受就好.

Still have questions? Get your answers by asking now.