list 在 Prolog 中对列表进行排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/8429479/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Sorting a list in Prolog
提问by Raceimaztion
Prolog has a unique way of handling things, especially since practically every operation involves recursion of one sort or another.
Prolog 有一种独特的处理方式，特别是因为实际上每个操作都涉及一种或另一种递归。
One of the classic examples every language has is sorting a list of integers into ascending order.
每种语言都有的经典示例之一是将整数列表按升序排序。
What is an optimal way (without using too many built-in predicates, which precludes a sort/2 predicate, of course) to sort a random list of integers?
对随机整数列表进行排序的最佳方法是什么（不使用太多内置谓词，当然，这排除了 sort/2 谓词）？
采纳答案by dommer
Roman Barták's Prolog Programming site gives examples of different sort algorithms, ending with an optimized quicksort.
Roman Barták 的 Prolog Programming 站点提供了不同排序算法的示例，以优化的快速排序结束。
quick_sort2(List,Sorted):-q_sort(List,[],Sorted).
q_sort([],Acc,Acc).
q_sort([H|T],Acc,Sorted):-
pivoting(H,T,L1,L2),
q_sort(L1,Acc,Sorted1),q_sort(L2,[H|Sorted1],Sorted)
回答by false
As far as I know the best sorting algorithms written in Prolog directly, without reference to any special built-ins use some form of merge sort.
据我所知，最好的排序算法直接用 Prolog 编写，没有参考任何特殊的内置函数，使用某种形式的归并排序。
A frequent optimization is to start merging not with lists of length 1 but with already sorted segments.
一个频繁的优化是不与长度为 1 的列表而是与已经排序的段开始合并。
That is, to sort the list [4,5,3,6,2,7,1,2], the lists [4,5],[3,6],[2,7],[1,2]would be merged.
也就是说，对列表进行排序[4,5,3,6,2,7,1,2]，列表[4,5]，[3,6]，[2,7]，[1,2]将被合并。
This can be optimized even further by assembling sorted lists not only in ascending direction, but also in the other direction. For the example above this would mean that the sorted segment is assembled as follows:
这可以通过不仅在升序方向上，而且在另一个方向上组合排序列表来进一步优化。对于上面的示例，这意味着已排序的段按如下方式组装：
[4,5|_]
[3,4,5|_]
[3,4,5,6|_]
...
Note that in Prolog it is straight forward to extend a list both in the beginning and at the end.
请注意，在 Prolog 中，可以直接在开头和结尾扩展列表。
Thus, we have to merge [1,2,3,4,5,6,7]and [2]only.
因此，我们必须合[1,2,3,4,5,6,7]并且[2]仅。
A current system that uses the original implementation (~1984) of Richard O'Keefe is Ciao-Prologin ciao-1.15/lib/sort.pl.
使用 Richard O'Keefe 的原始实现 (~1984) 的当前系统是Ciao-Prologin ciao-1.15/lib/sort.pl。
