在Prolog中对列表进行排序

Question

对于Prolog，其处理方式非常独特，尤其是因为几乎每个操作都涉及某种形式的递归。

每种语言都有一个经典示例，即将整数列表按升序排序。

如何以最优的方式（不使用太多内置谓词，当然这也排除了sort/2谓词）对随机整数列表进行排序？

- Raceimaztion

Answer 1

Roman Barták的Prolog编程网站提供了不同排序算法的示例，最终包括一个优化后的快速排序。点击此处查看。

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)

- dommer

---

请注意：该断言（使用您提供链接中实现的pivoting/4）执行降序排序，您需要反转pivoting/4的比较运算符以进行升序排序。 - gusbro

Answer 2

据我所知，用Prolog编写的最佳排序算法直接使用某种形式的归并排序，而不参考任何特殊的内置函数。

一个经常使用的优化方法是从已经排序好的段开始合并，而不是从长度为1的列表开始合并。

也就是说，对于要排序的列表[4,5,3,6,2,7,1,2]，应该合并[4,5]，[3,6]，[2,7]和[1,2]这些已经排好序的列表。

甚至可以进一步优化，不仅按升序组装排序列表，还可以按照其他方向组装。对于上面的例子，排序段将按以下方式组装：

[4,5|_]
[3,4,5|_]
[3,4,5,6|_]
...

请注意，在Prolog中，扩展列表的开头和结尾都很简单。

因此，我们只需要合并[1,2,3,4,5,6,7]和[2]。

使用Richard O'Keefe原始实现（约1984年）的当前系统是Ciao-Prolog，位于ciao-1.15/lib/sort.pl中。

- false

---

@j4nbur53：下载当前版本的Ciao。 - false

我最喜欢用树来进行排序，参见https://dev59.com/yHA75IYBdhLWcg3weZDu#33380747 ，但是Prolog树涉及比Java树更多的复制。 - user502187