Prolog Quicksort使用第二个元素作为枢轴

2024-05-20 • 问答

我一直在尝试学习序言，我想将列表的第二个元素用作快速排序的关键。

我认为使用[Head | [枢纽|尾]]作为方法中的输入可以使用，但是后来我不确定在哪里可以放置“ Head”（第一个元素）。

像这样：

qsort([],[]):- !.
qsort([Head|[Pivot|Tail]],Sorted):-
        split(Pivot,[Head|Tail],Less,Greater),qsort(Less,SortedLess),qsort(Greater,SortedGreater),append(SortedLess,[Pivot|SortedGreater],Sorted).
split(_,[],[]).
split(Pivot,[X|T],[X|Less],Greater):-
        X=<Pivot,split(Pivot,T,Greater).
split(Pivot,[X|Greater]):-
        X>Pivot,Greater).

但是，当我尝试使用qsort([8,3,4,12,25,6,1,9,22,6],Sorted).对列表进行排序时，它只是返回false。我在做什么错了？

但是，当我尝试使用qsort([8,3,4,12,25,6,1,9,22,6],Sorted)对列表进行排序时。它只是返回false。我在做什么错了？

最终，该算法将使用具有一个完全相同的元素的列表进行调用，而您未定义与该列表匹配的qsort/2子句。

您可以通过添加规则来解决此问题：

qsort([],[]).
qsort([X],[X]).
qsort([Head,Pivot|Tail],Sorted):-
        split(Pivot,[Head|Tail],Less,Greater),qsort(Less,SortedLess),qsort(Greater,SortedGreater),append(SortedLess,[Pivot|SortedGreater],Sorted).

这给我们：

?- qsort([8,Sorted).
Sorted = [1,8,12|...] ;
false.

Prolog Quicksort使用第二个元素作为枢轴

zhiyin1985 回答：Prolog Quicksort使用第二个元素作为枢轴

大家都在问