时间戳

首页 > 解决方案 > 快速排序出错（添加了一些重复项）

java - 快速排序出错（添加了一些重复项）

问题描述

我是排序算法的新手，似乎无法弄清楚出了什么问题。对于 int [] uArr = {5,2, 10, 7, 6, 0, 8, 1, 9} 的未排序数组，我得到 0,1,2,5,5,6,8,10 ( org. 数组中的 9 被重复的 5 替换，并且 7 丢失了）。如果我将重复项添加到数组中，则在对数组进行排序后会得到更多重复项以及更多丢失的数字。

 public static void main(String args[]){
     int [] uArr = {5,2, 10, 7, 6, 0, 8, 1, 9};

     qSort(uArr, 0, 8);
     
 }

 public static void qSort(int [] A, int low, int high){
    
    if (low < high){
   int pivotL = partition(A, low, high);
   qSort(A, low, pivotL);
 qSort(A, pivotL+1, high);
    }       
}
public static int partition(int [] arr, int low, int high){
 int pivot = arr[low];
 int leftwall = low;
 for (int i = low + 1; i < high; i++){
if (arr[i] < pivot){
 int temp = arr[i];
 arr[i] = arr[leftwall];
arr[leftwall] = temp;
leftwall += 1;

}  
}

int temp2 = pivot;
pivot = arr[leftwall];
arr[leftwall] = temp2;
return leftwall;
}
}

标签： javasortingquicksort

解决方案

因此，您应该认真做的一件事是开始编写文档。尽管这是一个小程序，但您在编写代码时似乎已经忘记了自己在做什么。

例如，数组中有 9 个元素，您传入要排序的偏移量，包括 0 到 8：

  qSort( uArr, 0, 8 );

但是然后在分区例程中，您只对小于该high值的元素进行排序：

 for( int i = low + 1; i < high; i++ ) {

与您不同，数组中的最后一个值 9 对我来说从未被触及，也从未排序。所以这是个问题。弄清楚您是否希望索引具有包容性。对我来说，边走边写文档可以帮助我保持这些想法。

我仍在寻找其他问题，例如重复。

更新：我将在我弄清楚它们时发布这些，作为我如何寻找问题的一种意识流。我很早就被教导的一件事是，将打印语句添加到代码中比使用调试器要快。所以（在重新格式化你的代码之后，因为你发布的格式坦率地说是废话）我添加了这个：

 public static void qSort( int[] A, int low, int high ) {
    System.out.println( Arrays.toString( A ) + " low=" + low + " high=" + high );

并得到了这个输出：

run:
[5, 2, 10, 7, 6, 0, 8, 1, 9] low=0 high=8
[2, 0, 1, 5, 6, 5, 8, 10, 9] low=0 high=3
[0, 1, 2, 5, 6, 5, 8, 10, 9] low=0 high=2
[0, 1, 2, 5, 6, 5, 8, 10, 9] low=0 high=0
[0, 1, 2, 5, 6, 5, 8, 10, 9] low=1 high=2
[0, 1, 2, 5, 6, 5, 8, 10, 9] low=1 high=1
[0, 1, 2, 5, 6, 5, 8, 10, 9] low=2 high=2
[0, 1, 2, 5, 6, 5, 8, 10, 9] low=3 high=3
[0, 1, 2, 5, 6, 5, 8, 10, 9] low=4 high=8
[0, 1, 2, 5, 5, 6, 8, 10, 9] low=4 high=5
[0, 1, 2, 5, 5, 6, 8, 10, 9] low=4 high=4
[0, 1, 2, 5, 5, 6, 8, 10, 9] low=5 high=5
[0, 1, 2, 5, 5, 6, 8, 10, 9] low=6 high=8
[0, 1, 2, 5, 5, 6, 8, 10, 9] low=6 high=6
[0, 1, 2, 5, 5, 6, 8, 10, 9] low=7 high=8
[0, 1, 2, 5, 5, 6, 8, 10, 9] low=7 high=7
[0, 1, 2, 5, 5, 6, 8, 10, 9] low=8 high=8
[0, 1, 2, 5, 5, 6, 8, 10, 9]
BUILD SUCCESSFUL (total time: 0 seconds)

我确实不得不盯着输出看了一会儿，但接下来我注意到的是两件事。5 几乎立即被复制，并且 5 也是第一个元素，这意味着您的partition代码将选择它作为枢轴。所以看起来你在将枢轴与数组重新合并时遇到了问题。

更新 2：OK 发现另一个问题。这是我通过手工写出你的数组并遍历每个值而找到的i，leftwall因为它构成了第一个分区。这里的问题：

当枢轴点 5 遇到数组中的元素0时，数组的其余部分尚未排序。, 10,7等6不小于枢轴并且没有被触及。所以当你进行交换时，你会看到这个：

[2, 5, 10, 7, 6, 0, 8, 1, 9]

为了这：

[2, 5, 0, 7, 6, 5, 8, 1, 9]

这是因为leftwall是 1（它已与 the2但没有任何其他数字交换，所以它只增加了一次）并且也有重复和丢失的数字。我将停在那里，因为你有一些非常大的问题。

在这种情况下，您需要做的是用 . 交换10，而不是枢轴0。这至少需要一个额外的指针。快速排序算法需要找到数组中的最低和最高，并且在外循环中有两个循环for。您在这里拥有的是一种奇怪的递归插入排序。您需要多考虑一下如何做到这一点，但是需要另外两个循环，嵌套在第一个循环中。

推荐阅读