用haskell实现选择排序

发表于 更新于 阅读次数：

《haskell趣学指南》这本书里有一个快速排序的例子, 如下:

1
2
3
4
5
6
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

太简练了！受其启发，写了一个选择排序函数，如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
-- 取得某个list的最大值
maxList ::(Ord a)=> [a]->a
maxList [x] = x
maxList (x:xs) = max x (maxList xs)

-- 取得某个值在List中的位置（开始为1）
orderList::(Ord a, Num b)=>a->[a]->b
orderList _ [] = error "empty list"
orderList a all@(x:xs)
    |not (elem a all) = error "not found"
    |a==x = 1
    |otherwise = (orderList a xs) + 1

-- 去掉某个list中的某个位置的数据
except::Int->[a]->[a]
except n xs = (take (n-1) xs) ++ (drop n xs)

-- 选择排序
seleSort::(Ord a)=>[a]->[a]
seleSort [] = []
seleSort [x] = [x]
seleSort xs =
    let first = maxList xs
        posOfFirst = orderList first xs
        lefts = except posOfFirst xs
    in first : (seleSort lefts)

运行正常，只做了从大到小的排序。顺便写了几个列表函数:-)

—July 6更新
比较一下C语言的选择排序,同样使用的递归算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selects(int from,int size,int sort_meth){
    if(from==size-1)
        return;
    int m_pos=from;
    int m_value=to_sort[from];
    for(int i=from;i<size;i++){
        if(sort_meth ^ (to_sort[i]<m_value)){
            m_pos=i;
            m_value=to_sort[i];
        }
    }
    to_sort[m_pos]=to_sort[from];
    to_sort[from]=m_value;
    selects(from+1,size,sort_meth);
}