相关疑难解决方法(0)

Haskell的网站介绍了一个非常有吸引力的5行快速排序功能,如下所示.

quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

它们还包括"C中的真正快速排序".

// To sort array a[] of size n: qsort(a,0,n-1)

void qsort(int a[], int lo, int hi) 
{
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p)) 
          l …

我有一种算法可以对给定长度的列表进行并行排序：

import Control.Parallel (par, pseq)
import Data.Time.Clock (diffUTCTime, getCurrentTime)
import System.Environment (getArgs)
import System.Random (StdGen, getStdGen, randoms)


parSort :: (Ord a) => [a] -> [a]
parSort (x:xs)    = force greater `par` (force lesser `pseq`
                                         (lesser ++ x:greater))
    where lesser  = parSort [y | y <- xs, y <  x]
          greater = parSort [y | y <- xs, y >= x]
parSort _         = []

sort :: (Ord a) => [a] -> [a]
sort (x:xs) = lesser ++ x:greater
    where lesser …

我目前正在阅读有关功能数据结构和算法的内容，并尝试了不同的快速排序实现。然而，我注意到他们的表演有很多变化。

下面是我要讨论的一些精选的（所有程序都已经编译（ghc program.hs）进行测试（括号中的时间是优化-O标志获得的时间），要排序的列表是（最坏的情况已经排序了（这意味着所花费的时间在O (n^2))) [1 .. 20000] 列表中）：

qs1 []             = []
qs1 (pivot : rest) = qs1 lower ++ [pivot] ++ qs1 upper  where
  lower = [ x | x <- rest, x <= pivot ]
  upper = [ x | x <- rest, x >  pivot ]

这是我们学习语言时看到的经典类型。在这里，rest列表被遍历两次以首先过滤小于或等于枢轴的元素，然后是大于枢轴的元素。所用时间为 6.45 (4.42) 秒。

qs2 []             = []
qs2 (pivot : rest) = qs2 lower ++ [pivot] ++ qs2 upper  where
  (lower, upper) = …