Erlang冒泡排序

Question

我正在学习Erlang，并决定在其中实现冒泡排序，这花了我一些努力，结果我成功了，但我发现我的思维方式是错误的，有没有更有效的方法来实现它？

bubble_sort(L) ->
if 
length(L) > 1 ->
    SL=bubble_sort_p(L),
    bubble_sort(lists:sublist(SL,1,length(SL)-1)) ++ [lists:last(SL)];
true -> L
end.

bubble_sort_p([]) -> [];    
bubble_sort_p([F | R]) ->
    case length(R) > 0 of
        true -> case F > hd(R) of
                true ->  [hd(R)] ++ bubble_sort_p([F|tl(R)]);
                false -> [F] ++ bubble_sort_p([hd(R)|tl(R)])
            end;
        false -> [F]
    end.

Answer 1

请允许我以更具可读性的方式重写您的代码(不更改任何语义)：

bubble_sort(L) when length(L) =< 1 ->
    L;
bubble_sort(L) ->
    SL = bubble_sort_p(L),
    bubble_sort(lists:sublist(SL,1,length(SL)-1)) ++ [lists:last(SL)].

bubble_sort_p([])  ->
    [];
bubble_sort_p([F]) ->
    [F];
bubble_sort_p([F,G|T]) when F > G ->
    [G|bubble_sort_p([F|T])];
bubble_sort_p([F,G|T]) ->
    [F|bubble_sort_p([G|T])].

这应该允许更容易地思考程序中实际发生的事情。

Answer 2

从我的头顶开始的实现是：

bubble_sort(L) -> bubble_sort(L, [], false).

bubble_sort([A, B | T], Acc, _) when A > B ->
  bubble_sort([A | T], [B | Acc], true);
bubble_sort([A, B | T], Acc, Tainted) ->
  bubble_sort([B | T], [A | Acc], Tainted);
bubble_sort([A | T], Acc, Tainted) ->
  bubble_sort(T, [A | Acc], Tainted);
bubble_sort([], Acc, true) ->
  bubble_sort(lists:reverse(Acc));
bubble_sort([], Acc, false) ->
  lists:reverse(Acc).

如果我们谈论的是效率，那么我们显然不应该把冒泡排序放在首位。

Answer 3

并使用lists:foldr

bubble(List) ->
    Step = fun
              (E,{S,[]}) -> {S,[E]};
              (E,{_,[X|XS]}) when E > X -> {swapped,[X|[E|XS]]};
              (E,{S,XS}) -> {S,[E|XS]}
           end,
    case lists:foldr(Step, {intact,[]}, List) of
        {intact,XS} -> XS;
        {swapped,XS} -> bubble(XS)
    end.