4.5 Erlang并发编程-常用列表处理函数sort

sort

程序3.1是著名的快速排序的一个变体。sort(X)对列表X的元素排序，将结果放入一个新列表并将之返回。

-module(sort).
-export([sort/1]).

sort([]) -> [];
sort([Pivot|Rest]) ->
    {Smaller, Bigger} = split(Pivot, Rest),
    lists:append(sort(Smaller), [Pivot|sort(Bigger)]).

split(Pivot, L) ->
    split(Pivot, L, [], []).

split(Pivot, [], Smaller, Bigger) ->
    {Smaller,Bigger};
split(Pivot, [H|T], Smaller, Bigger) when H > Pivot ->
    split(Pivot, T, [H|Smaller], Bigger);
split(Pivot, [H|T], Smaller, Bigger) when H >= Pivot ->
    split(Pivot, T, Smaller, [H|Bigger]).

此处选取列表的第一个元素为中轴。元列表被分为两个列表Smaller和Bigger：Smaller的所有元素都小于中轴Pivot而Bigger的所有元素都大于等于Pivot。之后，再对列表Smaller和Bigger分别排序并将结果合并。

函数split({Pivot, L})返回元组{Smaller, Bigger}，其中所有Bigger中的元素都大于等于Pivot而所有Smaller中的元素都小于Pivot。split(Pivot, L)通过调用一个辅助函数split(Pivot, L, Smaller, Bigger)完成任务。两个累加列表，Smaller和Bigger分别用于存储L中小于和大于等于Pivot的元素。split/4的代码与reverse/2非常相像，只是多用了一个累加列表。例如：

> lists:split(7,[2,1,4,23,6,8,43,9,3]).
{[3,6,4,1,2],[9,43,8,23]}

如果我们调用sort([7,2,1,4,23,6,8,43,9,3])，首先就会以7为中轴来调用split/2。这将产生两个列表：所有元素都小于中轴7的[3,6,4,1,2]，以及所有元素都大于等于中轴的[9,43,8,23]。

假设sort工作正常，则sort([3,6,4,1,2])⇒[1,2,3,4,6]而sort([9,43,8,23])⇒[8,9,23,43]。最后，排好序的列表被拼装在一起：

> append([1,2,3,4,6], [7 | [8,9,23,43]]).
[1,2,3,4,6,7,8,9,23,43]

再动一点脑筋，都append的调用也可以省掉，如下所示：

qsort(X) ->
    qsort(X, []).

%% qsort(A,B)
%%   Inputs:
%%      A = unsorted List
%%      B = sorted list where all elements in B
%%          are greater than any element in A
%%   Returns
%%      sort(A) appended to B

qsort([Pivot|Rest], Tail) ->
    {Smaller,Bigger} = split(Pivot, Rest),
    qsort(Smaller, [Pivot|qsort(Bigger,Tail)]);
qsort([], Tail) ->
    Tail.

我们可以利用BIFstatistics/1（用于提供系统性能相关的信息，参见附录??）将之与第一版的sort做一个对比。如果我们编译并执行以下代码片段：

...
statistics(reductions),
lists:sort([2,1,4,23,6,7,8,43,9,4,7]),
{_, Reductions1} = statistics(reductions),
lists:qsort([2,1,4,23,6,7,8,43,9,4,7]),
{_, Reductions2} = statistics(reductions),
...

我们可以得知sort和qsort的归约（函数调用）次数。在我们的示例中sort花费93次归约，而qsort花费74次，提升了百分之二十。