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 ) 与矩型排序列在后段介绍。