Haskell通用快速排序实现：如何适配任意类型列表？

当然可以修改这个算法，让它支持任意类型的列表，核心思路就是把原本依赖Ord类型类的比较逻辑，作为额外参数传入函数中，完全由调用者定义排序规则。

修改后的实现（基于布尔比较函数） #

这个版本接受一个a -> a -> Bool类型的函数，用来判断第一个元素是否应该排在第二个元素的前面（对应原逻辑中的“小于等于基准值”）：

quicksort :: (a -> a -> Bool) -> [a] -> [a]
quicksort _ [] = []
quicksort shouldComeBefore (x:xs) =
    let smallerSorted = quicksort shouldComeBefore (filter (\y -> shouldComeBefore y x) xs)
        biggerSorted = quicksort shouldComeBefore (filter (\y -> not (shouldComeBefore y x)) xs)
    in smallerSorted ++ [x] ++ biggerSorted

使用示例

• 还原原算法的整数排序：

  -- 传入(<=)函数，和原快排行为完全一致
  quicksort (<=) [3,1,4,1,5,9,2,6]
  

• 自定义类型排序（比如按Person的年龄或名字排序）：

  data Person = Person { name :: String, age :: Int } deriving Show
  
  -- 按年龄升序排序
  sortByAge :: [Person] -> [Person]
  sortByAge = quicksort (\p1 p2 -> age p1 <= age p2)
  
  -- 按名字字典序排序
  sortByName :: [Person] -> [Person]
  sortByName = quicksort (\p1 p2 -> name p1 <= name p2)
  

更通用的Ordering版本 #

如果需要更精细的比较逻辑（比如区分等于、小于、大于），可以改用返回Ordering类型的比较函数，逻辑更清晰：

quicksort :: (a -> a -> Ordering) -> [a] -> [a]
quicksort _ [] = []
quicksort compareFn (x:xs) =
    let smallerSorted = quicksort compareFn (filter (\y -> compareFn y x /= GT) xs)
        biggerSorted = quicksort compareFn (filter (\y -> compareFn y x == GT) xs)
    in smallerSorted ++ [x] ++ biggerSorted

调用时可以直接用标准库的compare函数（对于实现了Ord的类型），或者自定义比较逻辑：

-- 整数降序排序
quicksort (\a b -> compare b a) [3,1,4,1,5]

核心变化说明 #

原算法依赖Ord a约束，只能处理实现了默认排序逻辑的类型；修改后的版本去掉了这个约束，把排序规则完全交给传入的比较函数，因此可以处理任意类型，只要调用者提供对应的比较逻辑即可。

内容的提问来源于stack exchange，提问作者dumbQuestions