如何在Haskell中实现排序算法

Haskell是一种函数式编程语言，它支持许多排序算法的实现。在本文中，我将介绍三种常用的排序算法：冒泡排序、插入排序和快速排序，并且为每种算法提供一个使用例子。在开始之前，请确保您已经安装了Haskell。

1. 冒泡排序（Bubble Sort）：

冒泡排序通过比较相邻元素的大小来排序一个列表。在每一轮迭代中，较大的元素会移动到列表的末尾。该算法的时间复杂度为O(n^2)。

实现冒泡排序的Haskell代码：

bubbleSort :: Ord a => [a] -> [a]
bubbleSort list =
  if swapped then bubbleSort rest else list
  where
    (swapped, rest) = bubbleSortPass list

bubbleSortPass :: Ord a => [a] -> (Bool, [a])
bubbleSortPass (x1:x2:xs) =
  if x1 > x2
    then (True, x2:(fst (bubbleSortPass (x1:xs))))
    else (swapped, x1:ys)
  where
    (swapped, ys) = bubbleSortPass (x2:xs)
bubbleSortPass rest = (False, rest)

示例用法：

main = do
  let unsorted = [4, 2, 9, 6, 3, 1, 8, 7, 5]
  putStrLn $ "Unsorted list: " ++ show unsorted
  let sorted = bubbleSort unsorted
  putStrLn $ "Sorted list: " ++ show sorted

输出：

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

2. 插入排序（Insertion Sort）：

插入排序通过将每个元素插入已排序的子列表中来构建有序列表。它的时间复杂度也是O(n^2)。

实现插入排序的Haskell代码：

insertionSort :: Ord a => [a] -> [a]
insertionSort = foldr insert []

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

示例用法：

main = do
  let unsorted = [4, 2, 9, 6, 3, 1, 8, 7, 5]
  putStrLn $ "Unsorted list: " ++ show unsorted
  let sorted = insertionSort unsorted
  putStrLn $ "Sorted list: " ++ show sorted

输出：

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

3. 快速排序（Quick Sort）：

快速排序使用分治法，将一个列表划分为两个子列表，并通过递归地排序子列表来进行排序。它的时间复杂度通常是O(nlogn)。

实现快速排序的Haskell代码：

quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) =
  quickSort [y | y <- xs, y <= x]
  ++ [x]
  ++ quickSort [y | y <- xs, y > x]

示例用法：

main = do
  let unsorted = [4, 2, 9, 6, 3, 1, 8, 7, 5]
  putStrLn $ "Unsorted list: " ++ show unsorted
  let sorted = quickSort unsorted
  putStrLn $ "Sorted list: " ++ show sorted

输出：

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

这些是在Haskell中实现和使用三种常用排序算法的例子。根据您的需求，您可以使用这些示例作为起点，并根据需要进行扩展和修改。