※ 引述《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