Prolog语言中的气泡排序
提问于 2011-01-20 15:02:05
我必须实现气泡排序函数(排序算法)。
我已经实现了bubblesort和swap，这是bubblesort的帮助函数。
swap([X,Y|T1],[Y,X|T1]):-(Y<X,!).
swap([X|T1],[X|T2]):- swap(T1,T2).
bubblesort([],[]) :- !.
bubblesort(T1,T2) :- (bubblesort(swap(T1,T2),T2)).我有一个无限的循环。我必须保留该功能的签名：
布布莱(T1，T2)
我在这个问题上困了两个小时。有人知道我该怎么做吗？
回答 5
Stack Overflow用户
发布于 2014-07-02 03:29:55
在交换程序没有变化之前，请继续交换。如果交换中没有任何更改，那么您已经排序了列表。
bubblesort ( List, SortedList) :-
swap ( List, List1 ), ! ,
bubblesort ( List1, SortedList) .
bubblesort ( List, List).
swap ( [ X, Y | Rest ], [ Y, X | Rest ] ) :-
X > Y, ! .
swap ( [ Z | Rest ], [ Z | Rest1 ] ) : -
swap (Rest, Rest1 ).Stack Overflow用户
发布于 2011-12-18 01:55:35
这个问题是由递归查询引起的。在查询bubblesort(T1, T2)时，它查询bubblesort(swap(T1, T2), T2)，然后通过bubblesort/2的第二个子句，bubblesort(swap(swap(T1, T2), T2'), T2)和T2统一为T2，然后循环。它永远不会得到swap(T1, T2)查询的第一个结果。
Stack Overflow用户
发布于 2011-01-20 17:45:16
简单的气泡排序算法由两个主循环组成：
- 遍历列表，“交换”每对元素，如果它们不是“按顺序”(内循环)。
- 在结果上重复(1)，直到列表被完全排序(外部循环)。
内环(1)可以这样表示：
% performs a single pass of a bubble-sort on a list
do_bubble_sort([], []).
do_bubble_sort([X], [X]).
do_bubble_sort([X0,X1|Xs], [X0|Rem]) :-
X0 =< X1, !,
do_bubble_sort([X1|Xs], Rem).
do_bubble_sort([X0,X1|Xs], [X1|Rem]) :-
do_bubble_sort([X0|Xs], Rem).上面的do_bubble_sort/2接受一个列表，如果它们不满足=<测试(第3子句)，则递归地交换列表中的连续元素。然后，外部循环谓词bubble_sort/2调用这个内环，如下所示：
% repeatedly performs a bubble sort on a list until it is sorted
bubble_sort(L, SL) :-
do_bubble_sort(L, L0),
(sorted_order(L0) ->
SL = L0
; bubble_sort(L0, SL)
).这个谓词接受输入列表并递归地应用do_bubble_sort/2，直到谓词sorted_order/1对结果成功，即如果列表最终被排序。sorted_order/1可以定义如下：
% checks a list of things are in sorted (ascending) order
sorted_order([]).
sorted_order([_]) :- !.
sorted_order([X0,X1|R]) :-
X0 =< X1,
sorted_order([X1|R]).这个谓词接受一个列表，并递归地检查每一对连续元素是否按排序顺序排列(通过=<测试，就像我们在do_bubble_sort/2中使用的一样--这很重要，否则算法可能不会终止！)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4753663
复制
腾讯云开发者
