二郎泡泡排序

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) -> 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).

如果我们谈论效率,我们显然不应该首先考虑泡沫排序.