快速排序不排序

所以我想创建一个快速排序方法，但是，它没有正确排序。下面有我的输入和输出
原始阵列：
80.0 10.0 50.0 70.0 60.0 90.0 20.0 30.0 40.0 0.0
排序后的数组：
0.0 30.0 20.0 80.0 40.0 60.0 70.0 10.0 90.0 50.0快速排序不排序

我试图改变for循环for(int i = left; i < right; i++)
但现在的输出是：
0.0 20.0 30.0 40.0 80.0 10.0 60.0 90.0 70.0 50.0

public static void sort(double[] a) 
    { 
     quickSort(a, 0, a.length-1); 
    } 

    public static void quickSort(double [] a, int left, int right) 
    { 
     if (left < right) 
     { 
      int pivotIndex = (left+right)/2; 
      int pos = partition(a,left,right,pivotIndex); 
      quickSort(a,left,pos-1); 
      quickSort(a,pos+1,right); 
     } 
    } 

    private static int partition(double [] a, int left,int right,int pivotIndex) 
    { 
     double temp = a[pivotIndex]; 
     a[pivotIndex] = a[right]; 
     a[right] = temp; 
     int pos = left;//represents boundary between small and large elements 
     for(int i = left; i < right-1; i++) 
     { 
      if (a[i] <= a[pivotIndex]) 
      { 
       double temp2 = a[i]; 
       a[i] = a[pos]; 
       a[pos] = temp2; 
       pos++; 
      } 
     } 
     double temp3 = a[pivotIndex]; 
     a[pivotIndex] = a[pos]; 
     a[pos] = temp3; 
     return pos; 
    }

来源

2010-02-23 Raptrex

这是你想要做什么：

private static void swap(double[] a, int i, int j) { 
    double t = a[i]; 
    a[i] = a[j]; 
    a[j] = t; 
} 

private static int partition(double [] a, int left,int right,int pivotIndex) 
{ 
    swap(a, pivotIndex, right); 
    int pos = left;//represents boundary between small and large elements 
    for(int i = left; i < right; i++) 
    { 
     if (a[i] < a[right]) 
     { 
      swap(a, i, pos); 
      pos++; 
     } 
    } 
    swap(a, right, pos); 
    return pos; 
}

我所做的代码更清晰，由具有辅助swap方法。你必须在原代码3个错误：

循环边界上的一次性错误
您使用了错误的指标，以获得转动部件在循环
您在交换元素循环

来源

2010-02-23 08:25:36 polygenelubricants

将pivotIndex作为参数传递是没有用的，在分区内计算它会更有效率（并且避免所有交换的东西）......无论如何，分区的位置已经被分区返回。 – kriss 2010-02-23 09:30:51

我不想改变他原来的代码太多;我只是想纠正我看到的任何错误。重构交换是为了清晰而不是效率。 – polygenelubricants 2010-02-23 10:04:47

变化

for(int i = left; i < right-1; i++)

到

for(int i = left; i < right; i++)

来源

2010-02-23 08:15:27 ariel

没有工作后错指标，我现在输出的是：0.0 20.0 30.0 40.0 80.0 10.0 60.0 90.0 70.0 50.0 – Raptrex 2010-02-23 08:20:45

最后的交换必须在POS和右派之间，不POS和pivotIndex – ariel 2010-02-23 08:31:15

之间和内环路，枢轴值在'a [right]'，而不是'a [pivotIndex]'。 – polygenelubricants 2010-02-23 08:44:48

快速排序不排序

回答

相关问题