排序算法

整活, 整一个排序算法.

插入排序

插入排序的基本思路就是, 选择一个元素, 将他插入到一个合适的地方. 例如如果是从小到大的排序, 选择一个元素, 插入到一个左边比他小, 右边比他大的位置. 将所有的元素都放置到合适的位置之后, 排序就完成了.

先来整个插入

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

排序就像之前说的, 不停的进行冒泡操作, 直到没有一个元素被冒泡为止.

未完…

发表评论

电子邮件地址不会被公开。 必填项已用*标注