时间戳

首页 > 解决方案 > 快速排序乱序执行

java - 快速排序乱序执行

问题描述

我正在尝试使用 Lomuto 分区方案实现快速排序算法。这里和那里有一些小错误，但现在它对数组进行排序。

输入为：3 4 15 1。

问题是它不会终止，更奇怪的是代码看起来像这样：

public void quickSort(int start, int end) {
    System.out.println("Quicksorting...\n Start: " + start + " End: " + end);
    System.out.println("Is start<end: " + (start < end ? "true" : "false") + "!!!!!!!!!!");
    while (start < end) {
        System.out.println("In case: (start:end) = " + start + "; " + end);
        partitionPoint = partition_lomuto(start, end);
        System.out.println("partition point: " + partitionPoint);
        System.out.println("\n\nCalling quickSort left...");
        quickSort(start, partitionPoint);   // On left of the pivot.
        System.out.println("\n\nCalling quickSort right...");
        quickSort(partitionPoint+1, end);   // On right of the pivot.
    }
    System.out.println("Cancel qs call");
}

像这样被执行（看似）：

Calling quickSort right...
Quicksorting...
Start: 3 End: 3
Is start<end: false!!!!!!!!!!
Cancel qs call
In case: (start:end) = 2; 3  // UNEXPLAINABLE BEHAVIOUR LINE
1 3 15 4 
partition point: 2

在我看来，“无法解释的行为行”下的任何内容都不应该存在，或者至少日志应该显示已使用另一个“开始”和“结束”索引调用了快速排序。此外，正如您所看到的那样，它开始围绕已经排序的数组的值进行洗牌，并且实际上并没有终止。

我在 Linux 上运行它。

我计算了左侧分区排序和右侧分区排序的数量，它们的数量相等。我正在寻找的只是对上述情况如何发生的解释。

标签： javaalgorithmsortingquicksort

解决方案

推荐阅读