我在 Kotlin 中的快速排序功能返回错误的输出

Question

我试着做了一个链表的快速排序功能，它可以根据给定的变量对对象进行排序。但我有一个问题，即快速排序功能的输出既没有排序也没有改变。相反，它完全不同。

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

例如，这里是我要排序的列表的控制台输出： (翻译:"Sein name ist": "His name his") :

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
          }
           }

辅助功能： fun getFirst():Eintrag{ return 首先？: 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

如果您的 class 将实现 Comparable interface docs here and 而不是将其作为单独的值，您可以使用像这样的简单快速排序实现。

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 class，因为当您调试某些东西时，最好尽可能减少代码（这就是为什么也是关于创建最小可重现示例的建议），然后开始添加到它，然后你可以轻松检测你的比较器是否关闭，或者你的 classes 是否关闭等。

我在 Kotlin 中的快速排序功能返回错误的输出

My quick Sort Function in Kotlin give the wrong output back

quicksort

kotlin