※ 引述《eric80520 (freejustice)》之銘言：
: 因為快速排序是不穩定的，所以相同的值可能會互換
: 那如果有一個資料是 1,1,1,1,1,1,1
: 那會如何排列呢
: 假設第一個1是1_a,第二個1是1_b......
: 拜託了，如果有每一步的過程就太好了
: 謝謝
用Haskell的語法把快速排序的每一步過程介紹給你:
我說有個函數叫qsort/1,意思就是qsort函數名稱可接受一個參數,
而這個參數我說是一列數字. 具體的例子是 qsort [1,1,1,1,1,1,1],
然後它會求這一列數字的快速排序之後的版本.
qsort怎麼定義呢? 我說,以下是第一種定義; 之後我還會說有第二種定義.
我說 (x:xs) 是任何一列數字的縮寫, x 代表第一個數字, xs 代表之後的數列.
例如, [1,2,3,4], x 代表 1, xs 代表 [2,3,4].
qsort的第一種定義如下:
qsort [] = []
qsort (x:xs) = (qsort [ y | y <- xs, y < x]) ++ [x]
++ (qsort [ z | z <- xs, z >= x])
[ y | y <- xs, y < x] 是說從後段數列中取每一個數字,用 y 代表. 選擇小於 x
的 y 值. 簡單說就是從 xs 中取出每個小於 x 的數字. 於是[ z | z <- xs, z >= x]
是從 xs 中取出每個大於或等於 x 的數字. ++ 意思是把左右二串數字連接在一起.
那,這樣來看, qsort [1,1,1,1,1,1,1] 執行第一步的樣子就是:
qsort [1,1,1,1,1,1,1]
= (qsort []) ++ [1] ++ (qsort [1,1,1,1,1,1])
把qsort [1,1,1,1,1,1]繼續推下去, 你應該看得出它怎麼排列.
qsort第二種定義是:
qsort [] = []
qsort (x:xs) = (qsort [ y | y <- xs, y <= x]) ++ [x]
++ (qsort [ z | z <- xs, z > x])
執行一步則是:
qsort [1,1,1,1,1,1,1]
= (qsort [1,1,1,1,1,1]) ++ [1] ++ (qsort [])