整活, 整一个排序算法.
插入排序
插入排序的基本思路就是, 选择一个元素, 将他插入到一个合适的地方. 例如如果是从小到大的排序, 选择一个元素, 插入到一个左边比他小, 右边比他大的位置. 将所有的元素都放置到合适的位置之后, 排序就完成了.
先来整个插入
insert :: Int -> [Int] -> [Int]
insert x [] = [x]
insert x (y:ys)
| x < y = x:y:ys
| otherwise = y : insert x ys将一个元素插入到空数组自然得到的是一个只有一个元素的数组.
否则将被插入的元素 x 和数组的第一个元素 y 作比较, 如果 x < y, 那么说明这个元素可能位置就在这里了, 于是插入后的新数组就是 x, y, ....
否则, 说明 x 需要和第二个元素进行比较, 来确定插入到哪里; 同时之前的第一个元素 y 就确定是在第一个的位置了.
然后是排序
insertSort :: [Int] -> [Int]
insertSort [] = []
insertSort (x:xs) = insert x $ insertSort xs而排序步骤显然就是, 将数组的第一个元素 x 插入到已经排序好的剩余数组里面.
于是一个完整的插入排序就整好了.
选择排序
选择排序的思路很简单, 每次从一个数组里面选择一个最小的元素, 将他交换到合适的位置, 或者说, 将他追加到一个新数组的后面.
换个说法, 每次从数组中”拿出”一个最小的元素.
因此首先整一个 exclude, 功能是模拟”拿出”这个操作, 也就是返回从一个数组中”拿走”某个元素之后剩下的子数组.
exclude :: Int -> [Int] -> [Int]
exclude _ [] = []
exclude x (y:ys)
| x == y = ys
| otherwise = y : exclude x ys然后是排序的部分.
selectSort :: [Int] -> [Int]
selectSort [] = []
selectSort xs = min : selectSort tail
where min = minimum xs
tail = exclude min xs排序的步骤就是, 选择一个最小的元素, 放在头部, 然后将剩余的元素进行同样的操作, 追加到最小的元素后面. 递归下去的结果就是, 每次都会从剩下的里面选择最小的元素, 加到次小的后面.
快速排序
快速排序的思想是, 选择一个元素作为基准, 将比他小的元素放在一边, 而比他大的则放在另一边. 然后再将两边分别在进行一次快速排序. 将大数组化成小数组.
有 list comprehension 的话写起来就非常简单了.
quickSort :: [Int] -> [Int]
quickSort [] = []
quickSort (x:xs) = quickSort left ++ [x] ++ quickSort right
where left = [ y | y <- xs, y <= x]
right = [ y | y <- xs, y > x]直接用 list comprehension 把数组分成两部分, 一边大, 一边小, 然后再递归下就好了.
冒泡排序
冒泡排序的话, 元素就像是泡泡一样, 从底端”冒泡”一样的交换上去, 从而最终交换到一个合适的位置上. 一直重复冒泡步骤, 直到没有元素被冒泡为止. 实际上来说, 如果每个元素都被冒泡了一次, 那也一定会排序完成.
首先需要整一个冒泡的函数, bubble, 将第一个元素”冒泡”到一个合适的位置. 将第一个元素和第二个元素比较下, 以此来决定应该怎么”冒泡”.
bubble :: [Int] -> [Int]
bubble [] = []
bubble [x] = [x]
bubble (x:y:ys)
| x > y = y : bubble (x:ys)
| otherwise = x : bubble (y:ys)然后是排序
bubbleSort :: [Int] -> [Int]
bubbleSort xs
| bubble xs == xs = xs
| otherwise = bubbleSort $ bubble xs排序就像之前说的, 不停的进行冒泡操作, 直到没有一个元素被冒泡为止.