# Erlang程式设计与问题解决/排序

## 快速排序

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

```quicksort([]) -> [];
quicksort([X|Xs]) ->
append(
quicksort([Y || Y<-Xs, Y=<X]),
[X | quicksort([Z || Z<-Xs, Z>X]) ]
).
```

## 气泡排序

```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 在此决定了气泡排序的主要运作逻辑，而且，也可以借由改写这个函数，使排序变成选择排序

### 选择排序

```select([X|Xs]) ->
case select(Xs) of
[] ->
[X];
[Y|Ys] ->
if
X > Y ->
[Y,X|Ys];
true ->
[X,Y|Ys]
end
end;
select([]) ->
[].
```

```compare(N, Xs) when N > 0 ->
Rs = select(Xs),
compare(N-1, Xs);
compare(_, Xs) ->
Xs.
```

## 插入排序

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