quicksort - 这个快速排序稳定吗？

Question

我在此指出，很难进行稳定的快速排序。但是，我的快速排序似乎很稳定。

quicksortBy _ []=[]
quicksortBy key (pivot:rest)=
    (quicksortBy key [little|little<-rest, key little < key pivot])
    ++ [pivot] ++
    (quicksortBy key [big|big<-rest, key big >= key pivot])

然后我做:

*Main> let items = [(4,0),(1,1),(10,2),(6,3),(4,4),(6,5), (1,6)]
*Main> quicksortBy fst items
[(1,1),(1,6),(4,0),(4,4),(6,3),(6,5),(10,2)]

通过使用第一个项目作为轴心，重复项向右移动。这是错误的，还是人们不使用它，因为它对排序数据效率低下。还是我发现了一些新东西？

Answer 1

是的，您描述的算法是稳定的，通常称为“朴素”快速排序。这个算法的问题在于它需要 O(n) 的额外空间来对数组进行排序。更节省空间的快速排序版本使用就地交换来修改数组，这会破坏稳定性，但会将空间成本降低到 O(log n) - 实际上只是递归调用的堆栈。