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