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 ) 與矩型排序列在後段介紹。