共计 2139 个字符，预计需要花费 6 分钟才能阅读完成。
前面学习了递归，趁热打铁就把常见的一些算法用递归实现了一遍，找找递归的感觉。
斐波那契数列
用递归函数定义如下：(1) n = 0 时，f(n) = 0(2) n = 1 时，f(n) = 1(3) n > 1 时，f(n) = f(n-1) + f(n-2)
–Haskell
fibonacci :: (Num a, Eq a) => a -> a
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci n = fibonacci (n – 1) + fibonacci (n – 2)
这代码几乎就是上面的递归定义原封不动的“照搬”。当然这个版本性能并不是太高，优化的空间很大，这里不讨论。
插入排序
大部分人在打牌的时候无意中就使用了这个算法。左手拿着排序好的排【一开始没有牌，当然满足条件】，假设按升序排列，每次右手摸完牌都会插入到左手适当的位置来保持左手中的牌是有序的。人的话，可能并没有意识到，实际上你在插入牌的时候，是通过将右手的牌或者从头开始或从尾开始依次跟左手的牌对比，然后找到合适的位置。时间复杂度为 O(n2)。
我们可以递归定义如下：（1）如果列表内没有元素，我们就返回空列表（2）如果列表不为空，对列表元素的排序，可以认为就是将列表首元素插入到已经排好序的其他元素中，这些元素的排序通过插入排序实现。
代码如下：
–Haskell
insertionSort :: Ord a => [a] -> [a]
insertionSort [] = []
insertionSort (x:xs) = insert x $ insertionSort xs
insert :: Ord a => a -> [a] -> [a]
insert x y = let (p,q) = span (<x) y in p ++ [x] ++ q
冒泡排序
这个算法也较为直观，假设升序排列，第一次遍历会将最大的元素移动到列表的右侧，怎么移动的呢？只要从左到右，依次比较当前位置的元素和右侧的元素，交换顺序不对的两个元素的位置。通过多次遍历，最终得到所有元素有序的列表。时间复杂度为 O(n2)。
–Haskell
bubbleSort :: Ord a => [a] -> [a]
bubbleSort [] = []
bubbleSort x = bubbleSort initx ++ [lastx]
where
x’ = swap’ x
initx = init x’
lastx = last x’
swap’ :: Ord a => [a] -> [a]
swap’ [] = []
swap’ [x] = [x]
swap’ (x1:x2:xs)
| x1 > x2 = x2 : swap’ (x1 : xs)
| otherwise = x1 : swap’ (x2 : xs)
归并排序
这个算法的效率较高，时间复杂度为 O(nlogn)，采用了分治思想，即：将元素分为两部分，每一部分分别采用归并排序算法排序，然后将这两部分已排序的部分合并为整体有序。
–Haskell
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort x1) (mergeSort x2)
where
(x1, x2) = splitAt half xs
half = (length xs) `div` 2
merge :: Ord a => [a] -> [a] -> [a]
merge [] ys = ys
merge xs [] = xs
merge x1@(x:xs) y1@(y:ys)
| x > y = y : merge x1 ys
| otherwise = x : merge xs y1
二分算法
在前面实现了一版，如下
–Haskell
import qualified Data.Vector as V
binarySearch :: (Ord a)=> V.Vector a -> Int -> Int -> a -> Maybe Int
binarySearch vec low high e
| low > high = Nothing
| vec V.! mid < e = binarySearch vec (mid+1) high e
| vec V.! mid > e = binarySearch vec low (mid-1) e
| otherwise = Just mid
where
mid = low + ((high-low) `div` 2)
但只能返回一个元素，如果我们想返回所有与 e 相等的元素位置该怎么办呢？一种非递归的方案可能是：使用上面得到的位置，然后使用循环向前和向后搜索，从而得到与之相等的所有元素的索引。下面是递归的版本，与循环版本对应，只不过在找到相等元素的时候继续往下递归即可。
–Haskell
import qualified Data.Vector as V
binarySearch’ :: (Ord a) => V.Vector a -> Int -> Int -> a -> [Int]
binarySearch’ vec low high e
| low > high = []
| vec V.! mid < e = binarySearch’ vec (mid + 1) high e
| vec V.! mid > e = binarySearch’ vec low (mid – 1) e
| otherwise = binarySearch’ vec low (mid – 1) e ++ [mid] ++ (binarySearch’ vec (mid + 1) high e)
where
mid = low + ((high – low) `div` 2)
下一章介绍的快速排序也是递归的范本，下一篇文章介绍。
微信公众号
