Erlang练习模拟for语句获取list的长度冒泡排序。Erlang的应用实例源码。
% 模拟for语句
for(Max, Max, Fun) -> [Fun(Max)];
for(Ind, Max, Fun) -> [Fun(Ind) | for(Ind + 1, Max, Fun)].
% 完整打印list
list_print(L) -> io:fwrite(“["), list_print2(L), io:fwrite("]~n”).
list_print2([E]) -> io:fwrite(“~p”, [E]);
list_print2([H|T]) -> io:fwrite(“~p, “, [H]), list_print2(T).
% 列表反向
list_reverse(L) -> list_reverse([], L).
list_reverse(L2, []) -> L2;
list_reverse(L2, [H|T]) -> list_reverse([H|L2], T).
% 快排
qsort([]) -> [];
qsort([H|T]) ->
{Left, Right} = qsort_separate([], [], H, T),
Left2 = qsort(Left),
Right2 = qsort(Right),
qsort_combine(Left2, [H|Right2]).
qsort_separate(Left, Right, _Pivot, []) -> {Left, Right};
qsort_separate(Left, Right, Pivot, [H|T]) ->
if H < Pivot -> qsort_separate([H|Left], Right, Pivot, T);
true -> qsort_separate(Left, [H|Right], Pivot, T)
end.
qsort_combine(Left, Right) -> qsort_combine2(list_reverse(Left), Right).
qsort_combine2([], Right) -> Right;
qsort_combine2([H|T], Right) -> qsort_combine2(T, [H|Right]).
% 根据某个条件是否满足，将list分成两个list
list_separate(F, L) -> list_separate(F, [], [], L).
list_separate(_F, TL, FL, []) -> {list_reverse(TL), list_reverse(FL)};
list_separate(F, TL, FL, [H|T]) ->
case F(H) of
true -> list_separate(F, [H|TL], FL, T);
false -> list_separate(F, TL, [H|FL], T)
end.
% 汉诺塔
hanoi(N) -> hanoi(N, a, b, c). % 从a经过b到达c
hanoi(1, A, _B, C) -> io:format(“~p -> ~p~n”, [A, C]);
hanoi(N, A, B, C) ->
hanoi(N-1, A, C, B), % 从A经过C到达B
io:format(“~p -> ~p~n”, [A, C]),
hanoi(N-1, B, A, C). % 从B经过A到达C
% 合并排序(merge sort)
msort(L) ->
LL = msort_scatter([], L), % scatter意为分散，将每个元素都pack成list，LL意为list的list
% io:format(“~w~n”, [LL]),
msort([], LL).
msort(LL, []) -> % LL2为[]
case LL of
[] -> []; % 需要排序的列表为空
[HL] -> HL; % LL只有一个升序列表
[HL|TLL] -> msort([], [HL|TLL]) % LL至少有两个升序列表，LL转到LL2，重新合并
end;
msort(LL, LL2) -> % LL2不为[]
case LL2 of
[HL] -> msort([HL|LL], []); % LL2只有一个升序列表，无法合并，直接将其转到LL中
[HL1, HL2|TLL] -> % 合并LL2开头的两个升序列表，并将其转到LL中
HL3 = msort_msorted(HL1, HL2),
% io:format(“~w + ~w -> ~w~n”, [HL1, HL2, HL3]),
msort([HL3|LL], TLL)
end.
msort_scatter(LL, []) -> LL;
msort_scatter(LL, [H|TL]) -> msort_scatter([[H]|LL], TL).
msort_msorted(L1, L2) -> msort_msorted(L1, L2, []). % 将两个升序的列表合并成一个升序的列表
msort_msorted([], [], L3) -> list_reverse(L3);
msort_msorted([H|T], [], L3) -> msort_msorted(T, [], [H|L3]);
msort_msorted([], [H|T], L3) -> msort_msorted([], T, [H|L3]);
msort_msorted([H1|T1], [H2|T2], L3) ->
case H1 < H2 of
true -> msort_msorted(T1, [H2|T2], [H1|L3]);
false -> msort_msorted([H1|T1], T2, [H2|L3])
end.
% 获取list的长度
list_length(L) -> list_length(0, L).
list_length(N, []) -> N;
list_length(N, [_H|TL]) -> list_length(N+1, TL).
% 冒泡排序挺难写的，如果不用process dictionary，复杂度会上升到O(n^2)，但用了又怕产生side effect。
% 冒泡排序(最大的数冒到最后)
bubble_sort(L) -> bubble_sort(list_length(L), L).
bubble_sort(1, L) -> L; % 在头1个数中冒出最大的数，放在第1个位置
bubble_sort(N, L) -> % 在头N个数中冒出最大的数，放在第N个位置
put(is_sorted, true), % 可能会产生side effect
L2 = bubble(N – 1, L), % 需要进行N-1次比较，判断是否有序
case get(is_sorted) of
true -> L2;
false -> bubble_sort(N – 1, L2)
end.
bubble(0, L) -> L; % 还剩下0次比较
bubble(N, [H1,H2|TL]) -> % 还剩下N次比较
if H1 > H2 -> put(is_sorted, false), [H2|bubble(N-1, [H1|TL])];
H1 =< H2 -> [H1|bubble(N-1, [H2|TL])]
end.
% 冒泡排序(最小的数冒到最前)
bubble_sort2([]) -> []; % L为[]
bubble_sort2(L) -> % L不为[]
put(is_sorted, true), % 可能会产生side effect
[H|T] = bubble2(L), % bubble2的列表必须保证不为[]，否则匹配失败
case get(is_sorted) of
true -> [H|T];
false -> [H|bubble_sort2(T)]
end.
bubble2([H1]) -> [H1];
bubble2([H1, H2|T]) ->
[H3|T3] = bubble2([H2|T]),
if H1 =< H3 -> [H1,H3|T3];
H1 > H3 -> put(is_sorted, false), [H3,H1|T3]
end.
% 插入排序
insert_sort(L) -> insert_sort([], L).
insert_sort(L, []) -> L;
insert_sort(L, [H|T]) -> insert_sort(sorted_insert(L, H), T). % sorted_insert将H插入到升序的L中
sorted_insert([], N) -> [N];
sorted_insert([H|T], N) ->
if H =< N -> [H|sorted_insert(T, N)];
H > N -> [N, H|T]
end.