我在Kotlin中的快速排序函数返回了错误的输出

Question

我试图为链表创建一个快速排序函数，它可以根据给定的变量对对象进行排序。但我遇到的问题是，快速排序函数的输出既没有排序，也没有更改。相反，它完全不同。

我尝试过更改addfirst函数和connect函数，但它没有任何作用。

因此，例如这里的控制台输出我想要排序的列表：(翻译："Sein name ist"："他的名字是他的"(：

Sein Name ist: Haarald(Alter: 3)
Sein Name ist: Mark(Alter: 2)
Sein Name ist: Guenter(Alter: 1)
Sein Name ist: Kai(Alter: 4)

现在控制台输出列表后，我在快速排序函数中给出了它：

Sein Name ist: Haarald(Alter: 3)
Sein Name ist: Mark(Alter: 2)
Sein Name ist: Guenter(Alter: 1)
Sein Name ist: Kai(Alter: 4)
Sein Name ist: Haarald(Alter: 3)
Sein Name ist: Guenter(Alter: 1)
Sein Name ist: Mark(Alter: 2)
Sein Name ist: Guenter(Alter: 1)

所以奇怪的是，输出多于输入。

这里是我使用的函数：

快速分拣功能：

fun quickSort(comparator: Comparator<T>){
if (this.size() < 2)return;
val pivot = this.getFirst().content;     //Vergleichs Element
val less = Liste<T>();
val equal= Liste<T>();
val more = Liste<T>();
for (element in this){
val compared = comparator.compare(pivot,element)
when{
compared >  0 -> less.addfirst(element);
compared == 0 -> equal.addfirst(element);
compared <  0 -> more.addfirst(element);
}
}
less.quickSort(comparator)
more.quickSort(comparator)
this.first = conect(this,conect(equal,less)).first
}

编者：

val intComperator = Comparator<Mensch>{o1: Mensch, o2:Mensch -> when{
o1.alter == o2.alter -> 0
o1.alter < o2.alter -> -1
o1.alter > o2.alter -> 1
else -> 0
}
}

Helper函数：fun getFirst((：Eintrag｛先返回？：throw Exception("(getFirst(此列表中没有元素"(}

fun conect(mainList:Liste<T>,toAdd:Liste<T>):Liste<T> {
mainList.getLast().next = toAdd.first;
return mainList
}

和最后一个代码，实现列表：

class Liste<T>:Iterable<T>{

class Eintrag<T>(val content:T, var next:Eintrag<T>?)
private var first :Eintrag<T>? = null;

这是完整的代码，对不起，我知道它很乱，我需要把代码分解成多个文件，还有一些关于我的格式的东西：https://github.com/TheDarkRiddle/Kotlin-quick-sort

Answer 1

如果您的类在这里和这里实现Comparable interface文档，而不是将其作为一个单独的值，那么您可以使用这样一个简单的快速排序实现。

fun <E : Comparable<E>> List<E>.quickSort(): List<E> =
when {
size < 2 -> this
else -> {
val (l, h) = subList(1, size).partition { it < first() }
l.quickSort() + first() + h.quickSort()
}
}

或者，您可以将其修改为使用比较器val，但老实说，我发现这有点难以理解，并且只适用于Mensch类型的对象。

fun List<Mensch>.quickSort(comparator: Comparator<Mensch>): List<Mensch> =
when {
size < 2 -> this
else -> {
val (l, h) = subList(1, size).partition { intComperator.compare(it, first()) == -1 }
l.quickSort(comparator) + first() + h.quickSort(comparator)
}
}

我在这里没有以任何方式包含Liste类，因为当你调试某个东西时，最好尽可能地减少代码(这就是为什么创建最小可复制示例也是SO的一个建议(，然后开始添加它，然后你可以很容易地检测你的比较器是否关闭，或者你的类是否关闭等等。