Erlang程式设计与问题解决/排序

计算机科学 > 编程 > Erlang程式设计与问题解决

快速排序

快速排序是一般接受度较大的排序法。对 Erlang 语言玩家而言，几乎是入门级的排序法，随手可得。

快速排序 ( quick sort ) 是一个递回过程。对任一列表，随意取其中一项当做比对项，将列表分为二部份，其中一部份包含列表全部小于比对项的元素，另一部份包含列表全部大于比对项的元素。然后，要对新分出来的二个部份分别做快速排序，将排序好的结果，资料较小的部份放在一边，资料较大的部份放在另一边。

quicksort([]) -> [];
quicksort([X|Xs]) ->
    quicksort([Y || Y<-Xs, Y=<X]) ++ [X] ++ quicksort([Z || Z<-Xs, Z>X]).

这样，程式构成很简单。虽然程式很简单，但是效能消耗的因素是在列表串接运算子 ++ ，它的计算方式与以下函数相同：

append([], Ys) -> Ys;
append([X|Xs], Ys) -> [X | append(Xs, Ys)].

强化快速排序

函数语言有一个常见的优化法则，称为尾端递回，意思是在函数主体程式中，只在最后做递回。尾端递回可以减低运作时的系统负担。有一项与尾端递回搭配的技巧，叫做累积变数，是将一个变数传入函数中，将一些部份计算结果累积到变数中，然后将变数传递到递回呼叫里。以下用尾端递回和累积变数，将上述 ++ 做一个强化的版本。

append(Xs, Ys) -> append(Xs, [], Ys).

append([], Accumulator, Ys) ->
    lists:reverse(Accumulator) ++ Ys;
append([X|Xs], Accumulator, Ys) ->
    append(Xs, [X|Accumulator], Ys).

随著递回将 [X|Xs] 的元素一个一个反序累积给 Accumulator 。最后，使用 lists:reverse/1 将 Accumulator 反转顺序。总共计算量平均比 ++ 较少。

有了这个优化的 ++/append ， quicksort/1 改写成：

quicksort([]) -> [];
quicksort([X|Xs]) ->
    append(
        quicksort([Y || Y<-Xs, Y=<X]),
        [X | quicksort([Z || Z<-Xs, Z>X]) ]
    ).

气泡排序

气泡排序 ( bubblesort ) 是程序式语言的入门课程，其中步骤充满程序性。对一列不知是否排序的数字，用一个二者比大小的函数来逐项比较、逐项影响数列的排列情况。首先，对这列数字由左向右依序两两比较大小，如果左方数字比较大，就让二个数字互换位置。每做完一次这个步骤，数列中有些数字会左移，有些数字会右移，并且可确定最大的数字会靠到最右边。这样的步骤称为扫瞄。而且，按照数列的数目 N ，重复进行扫瞄步骤 N-1 次，前 N-1 项较大的数字会依序靠右，并且每个都不会比更大的数字靠得更右边。于是数列排列完成。

以上所述的一次扫瞄， Erlang 可以写成：

compare([X,Y|Ys]) when X > Y ->
    [Y|compare([X|Ys])];
compare([X,Y|Ys]) ->
    [X|compare([Y|Ys])];
compare(Xs) ->
    Xs.

那么，气泡排序就是

bubblesort(Xs) ->
    compare(length(Xs)-1, Xs).

compare(N, Xs) when N > 0 ->
    Rs = compare(Xs),
    compare(N-1, Xs);
compare(_, Xs) ->
    Xs.

bubblesort/1 是主程式， compare/2 决定要扫瞄几次， compare/1 进行一次扫瞄并抛回结果。

compare/1 在此决定了气泡排序的主要运作逻辑，而且，也可以借由改写这个函数，使排序变成选择排序。

选择排序

选择排序是，在一列不知是否排序的数字中，找到最小的一个，就把它放到最左边。对 N 个数字做这个动作 N-1 次，就可以保证数字排列完成。在此，一次找到一个最小的数字并放在左边的函数，写成

select([X|Xs]) ->
    case select(Xs) of
        [] ->
            [X];
        [Y|Ys] ->
            if
                X > Y ->
                    [Y,X|Ys];
                true ->
                    [X,Y|Ys]
            end
    end;
select([]) ->
    [].

与以上气泡排序的程序互相比较，主程式和扫瞄次数的格式一模一样。选择排序的 compare/2 ，只要将 bubblesort/1 的 compare/2 改一个呼叫的对象

compare(N, Xs) when N > 0 ->
    Rs = select(Xs),
    compare(N-1, Xs);
compare(_, Xs) ->
    Xs.

同一组程式立刻化身为选择排序了。

插入排序

插入排序 ( insertion sort ) 是 Cormens 等人所著《演算法概论》 ( Introduction to Algorithms ) 书的第一个例子。排序就好像从一列不知是否排序的数字中，随便挑选每一个数字，将数字仔细放到目的地的正确顺序位置。

一个插入数字的动作，是这样的函数

insert(X, []) ->
    [X];
insert(X, [Y|Ys]) when X > Y ->
    [ Y | insert(X, Ys) ];
insert(X, [Y|Ys]) ->
    [X,Y|Ys].

插入排序的主程式是

insertionsort(Xs) ->
    insert_pile(Xs, []).

insert_pile/2 的二个参数，第一个是原数列，第二个是已排序数列。 insert_pile/2 定义为

insert_pile([], Ys) ->
    Ys;
insert_pile([X|Xs], Ys) ->
    Rs = insert(X, Ys),
    insert_pile(Xs, Rs).

其他排序

还有几种排序，需要更多程式工法。 Erlang 提供开源电信平台 ( Open Telecom Platform , OTP ) 程式库，使多数经常使用的程式功能、或是较复杂的演算过程，都可以引用此程式库而加强程式开发效率。因此，像基数排序法 ( radix sort ) 这种较复杂的处理，挪至 Erlang/OTP 介绍之后才讨论。 Shell 排序法是依气泡排序法和插入排序法而设计的加强方法，将来在效率的比较是有趣的讨论。另外，也将合并排序 ( merge sort ) 与矩型排序列在后段介绍。