使用Haskell实现一个高效的排序算法

Haskell是一种纯函数式编程语言，使用纯函数式编程风格可以实现高效的排序算法。在Haskell中，我们可以使用递归和模式匹配等特性来实现各种排序算法。下面我们将介绍两种经典的排序算法，分别是快速排序和归并排序，并给出它们的Haskell实现和使用例子。

1. 快速排序（Quick Sort）：

快速排序是一种分治算法，基本思想是通过一个元素（通常是数组的 个元素）将数组划分为较小和较大的两个子数组，然后递归地对这两个子数组进行排序。

Haskell实现快速排序算法的代码如下：

quickSort :: (Ord a) => [a] -> [a]
quickSort [] = []
quickSort (x:xs) =
    let smallerSorted = quickSort [a | a <- xs, a <= x]
        biggerSorted = quickSort [a | a <- xs, a > x]
    in smallerSorted ++ [x] ++ biggerSorted

使用例子：

main :: IO ()
main = do
    let list = [5, 2, 9, 1, 6, 4, 8, 3, 7]
    putStrLn "Original list:"
    print list
    putStrLn "Sorted list:"
    print (quickSort list)

输出结果：

Original list:
[5,2,9,1,6,4,8,3,7]
Sorted list:
[1,2,3,4,5,6,7,8,9]

2. 归并排序（Merge Sort）：

归并排序是一种基于分治的算法，在归并排序中，将数组划分为两个子数组，递归地对子数组进行排序，然后将排好序的子数组进行合并。

Haskell实现归并排序算法的代码如下：

mergeSort :: (Ord a) => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort list =
    let mid = length list div 2
        leftHalf = take mid list
        rightHalf = drop mid list
    in merge (mergeSort leftHalf) (mergeSort rightHalf)

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge (x:xs) (y:ys)
    | x <= y = x : merge xs (y:ys)
    | otherwise = y : merge (x:xs) ys

使用例子：

main :: IO ()
main = do
    let list = [5, 2, 9, 1, 6, 4, 8, 3, 7]
    putStrLn "Original list:"
    print list
    putStrLn "Sorted list:"
    print (mergeSort list)

输出结果：

Original list:
[5,2,9,1,6,4,8,3,7]
Sorted list:
[1,2,3,4,5,6,7,8,9]

以上是使用Haskell实现快速排序和归并排序的示例代码。这两种排序算法都是效率较高的排序算法，快速排序在平均情况下具有O(nlogn)的时间复杂度，而归并排序具有稳定的O(nlogn)时间复杂度。