Re: [請益] 快速排序的問題

看板CSSE (電腦科學及軟體工程)作者yauhh (喲)時間12年前 (2012/04/16 23:54)推噓1(1推 0噓 1→)

留言2則, 1人參與討論串2/3 (看更多)

※ 引述《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 []) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.112.229.87