1

我有这个 QuickSort 算法，它似乎对给定的输入数组进行排序但不完全：

public static int partition(int[] A,int low,int high){
    int pivot=A[high-1];
    int i=low-1;
    int temp=0;
    for(int j=low;j<A.length-1;j++){
        if(A[j]<pivot){
            i++;
            temp = A[j];
            A[j]=A[i];
            A[i]=temp;
        }
    }
    temp=A[high-1];
    A[high-1]=A[i+1];
    A[i+1]=temp;
    return i+1;
}

public static void Qsort(int[] A,int low,int high){
    if(low<high){
        int p=partition(A,low,high);
        Qsort(A,low,p-1);
        Qsort(A,p+1,high);
      }
}

我在 main 这样调用方法 Qsort

Qsort(arr,0,arr.length);

例如这个数组是正确排序的

6,5,3,7,1,2

但是这个

{6,5,3,7,1,2,4} is sorted like this {1 3 2 4 5 6 7}

如果我将最后一个索引更改为 8 而不是 4 它可以工作。这很令人困惑。我认为错误很小，但我找不到。

谢谢您的帮助。

编辑： 问题的正确解决方案：

public static int partition(int[] A,int low,int high){
   int pivot=A[high];
   int i=low;
   int temp=0;
   for(int j=low;j<high;j++){
      if(A[j]<pivot){
         temp = A[j];
         A[j]=A[i];
         A[i]=temp;
         i++;
      }
  }
  temp=A[high];
  A[high]=A[i];
  A[i]=temp;
  return i;
}

并且在 main 中对 Qsort 的调用应该是：（这很重要）

Qsort(arr,0,arr.length-1);

感谢大家的帮助。

4

1 回答 1

0 
public static int partition(int[] A,int low,int high){
    int pivotIndex=0;
    int pivot=A[pivotIndex];
    int i=low;    
    int temp=A[pivotIndex];
    A[pivotIndex]=A[high];
    A[high]=temp;
    for(int j=low;j<high;j++){
        if(A[j]<pivot){
            temp = A[j];
            A[j]=A[i];
            A[i]=temp;
            i++;
        }
    }
    temp=A[high-1];
    A[high-1]=A[i+1];
    A[i+1]=temp;
    return i;
}

要使其正常工作，需要进行一些改进：

  1. 选择不那么高的枢轴索引-1，为简单起见，我们取0
  2. 在进入 for 循环之前将元素 pivotIndex 与 high 交换
  3. 交换后增加你的 storeIndex i，而不是之前
  4. 返回 storeIndex i 而不是 i++
于 2013-10-27T20:39:10.007 回答