跳转到内容

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/1Accumulator 反转顺序。总共计算量平均比 ++ 较少。

有了这个优化的 ++/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 ) 与矩型排序列在后段介绍。