有时，我们需要将列表中的元素进行排序。SWI-Prolog内置了sort/2谓词用于排序，它用的是自然归并排序算法（natural merge sort），但那个谓词并不是用Prolog编写的，而是用的C，可能是出于运行效率的考虑。
在这里将展示4种Prolog的排序程序：朴素排序、插入排序、冒泡排序、快速排序。我们首先用“<”“@<”等符号设定排列次序，如设定语句order(X, Y) :- X < Y.进行升序排列。
朴素排序
朴素排序（naive sort），首先生成对象的排列，然后测试生成的列表是否按升序排列，如果它们不满足条件，那么我们再生成对象的其他排列，进行测试，直到符合要求。这显然不是一种高效的排序方法。
naisort(L1, L2) :- permutation(L1, L2), sorted(L2), !.
permutation([], []).
permutation(L, [H|T]) :-
append(V, [H|U], L),
append(V, U, W),
permutation(W, T).
sorted([]).
sorted([_]).
sorted([X, Y|L]) :- order(X, Y), sorted([Y|L]).
插入排序
插入排序（insertion sort），每次排序时取未排序的一项，将其插入到已排序列表中的适当位置。下面的代码中，当列表Y是排好序的列表X，则insort(X, Y)目标成功。每个元素都从列表头部移出，并传递给insortx，insortx将元素插入到列表中并进行返回。
insort([], []).
insort([X|L], M) :- insort(L, N), insortx(X, N, M).
insortx(X, [A|L], [A|M]) :-
order(A, X), !, insortx(X, L, M).
insortx(X, L, [X|L]).
冒泡排序
冒泡排序（bubble sort）会检查列表，查看两个相邻元素是否顺序有误，如果是，则交换它们，这个过程不断重复，直到不需要再交换为止。插入排序使元素“下沉”到适当的级别，而冒泡排序之所以如此命名，是因为它使元素“浮动”到适当的级别。
busort(L, S) :-
append(X, [A,B|Y], L),
order(B, A), !,
append(X, [B,A|Y], M),
busort(M, S).
busort(L, L).
append([], L, L).
append([H|T], L, [H|V]) :- append(T, L, V).
快速排序
正如名字所言，快速排序（Quicksort）是在实践中已知最快的排序算法。快速排序是一种更复杂的排序方法。其基本步骤是，如果列表中元素个数是0或1，则直接返回；接着选取列表中任一元素（这个元素在这里被称为“枢纽元”，pivot），将列表中的其余元素分为两个列表，其中一个列表中的元素都小于前面选取的那个元素，而另一个则都大于；然后对这两个列表重复执行上述步骤，得出结果，进行整合。
为了在Prolog中实现快速排序，我们可以将一个由头部H和尾部T组成的列表分成两个列表L和M，并使得：
- L的所有元素都小于H；
- M的所有元素都大于或等于H，并且
- L和M内元素的顺序与[H|T]中的相同。
split(H, [A|X], [A|Y], Z) :- order(A, H), split(H, X, Y, Z).
split(H, [A|X], Y, [A|Z]) :- \+(order(A, H)), split(H, X, Y, Z).
split(_, [], [], []).
quisort([], []).
quisort([H|T], S) :-
split(H, T, A, B),
quisort(A, A1),
quisort(B, B1),
append(A1, [H|B1], S).
参考资料
《Programming In Prolog》
《数据结构与算法分析——C语言描述》
在这里将展示4种Prolog的排序程序：朴素排序、插入排序、冒泡排序、快速排序。我们首先用“<”“@<”等符号设定排列次序，如设定语句order(X, Y) :- X < Y.进行升序排列。
朴素排序
朴素排序（naive sort），首先生成对象的排列，然后测试生成的列表是否按升序排列，如果它们不满足条件，那么我们再生成对象的其他排列，进行测试，直到符合要求。这显然不是一种高效的排序方法。
naisort(L1, L2) :- permutation(L1, L2), sorted(L2), !.
permutation([], []).
permutation(L, [H|T]) :-
append(V, [H|U], L),
append(V, U, W),
permutation(W, T).
sorted([]).
sorted([_]).
sorted([X, Y|L]) :- order(X, Y), sorted([Y|L]).
插入排序
插入排序（insertion sort），每次排序时取未排序的一项，将其插入到已排序列表中的适当位置。下面的代码中，当列表Y是排好序的列表X，则insort(X, Y)目标成功。每个元素都从列表头部移出，并传递给insortx，insortx将元素插入到列表中并进行返回。
insort([], []).
insort([X|L], M) :- insort(L, N), insortx(X, N, M).
insortx(X, [A|L], [A|M]) :-
order(A, X), !, insortx(X, L, M).
insortx(X, L, [X|L]).
冒泡排序
冒泡排序（bubble sort）会检查列表，查看两个相邻元素是否顺序有误，如果是，则交换它们，这个过程不断重复，直到不需要再交换为止。插入排序使元素“下沉”到适当的级别，而冒泡排序之所以如此命名，是因为它使元素“浮动”到适当的级别。
busort(L, S) :-
append(X, [A,B|Y], L),
order(B, A), !,
append(X, [B,A|Y], M),
busort(M, S).
busort(L, L).
append([], L, L).
append([H|T], L, [H|V]) :- append(T, L, V).
快速排序
正如名字所言，快速排序（Quicksort）是在实践中已知最快的排序算法。快速排序是一种更复杂的排序方法。其基本步骤是，如果列表中元素个数是0或1，则直接返回；接着选取列表中任一元素（这个元素在这里被称为“枢纽元”，pivot），将列表中的其余元素分为两个列表，其中一个列表中的元素都小于前面选取的那个元素，而另一个则都大于；然后对这两个列表重复执行上述步骤，得出结果，进行整合。
为了在Prolog中实现快速排序，我们可以将一个由头部H和尾部T组成的列表分成两个列表L和M，并使得：
- L的所有元素都小于H；
- M的所有元素都大于或等于H，并且
- L和M内元素的顺序与[H|T]中的相同。
split(H, [A|X], [A|Y], Z) :- order(A, H), split(H, X, Y, Z).
split(H, [A|X], Y, [A|Z]) :- \+(order(A, H)), split(H, X, Y, Z).
split(_, [], [], []).
quisort([], []).
quisort([H|T], S) :-
split(H, T, A, B),
quisort(A, A1),
quisort(B, B1),
append(A1, [H|B1], S).
参考资料
《Programming In Prolog》
《数据结构与算法分析——C语言描述》
