迭代快速排序法

Question

我正在尝试实现一个循环运行的hoare快速排序方法。我正在使用下面的算法。所以现在它输入: 10，7，8，9，15，例如，当我运行它时，输出:5，7，8，9，1，10，它只从数组中切换2个元素。为什么要停下来？我哪里出错了？

算法：

1. 创建N/2元素的左、右数组，其中数组a中的N元素数。
2. 将左分配给0，右分配给数组a的最后一个元素(N1)。赋给变量stackpos值1。
3. 将变量stackpos的值减少1。将左stackpos设为l，右stackpos分配给r
4. ，将变量中值值赋给m。中介必须在元素a l到r.
5. 之间选择，将变量l的值赋给变量i，将r赋给变量j.
6. ，如果a i小于m，则增加i.
7. ，如果j大于m，则减少j.
8. ，如果变量i小于或等于j，则: a)使用三杯原理交换元素a i和j。( b)增加一倍。c)将j减少1。如果i小于或等于j，则返回到步骤6。如果我小于r，则返回到以下步骤：( a)将左stackpos赋值给i. b)将r stackpos赋给r. c) )将变量stackpos增加1。如果变量l小于r，则返回到步骤4。如果变量l小于r，则返回到步骤4。如果stackpos变量大于0，则返回到步骤3H 226G 227/code>。

代码：

public static void swap (int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

public static int median (int []a) {
    int rnd = new Random().nextInt(a.length);
    int M = a[rnd];
    return M;
}

private static int partition(int[] a, int i, int M, int j) {
    while (i <= j) {
        while (a[i] < M) {
            i++;
        }
        while (a[j] > M) {
            j--;
        }
        if (i <= j) {
            swap(a,i, j);
            i++;
            j--;
        }
    }
    return i;
}

public static int[] secondMethod(int[] a) {
    int N=a.length;
    int left [] = new int [N/2];
    int right [] = new int [N/2];
    left[0]=0;
    right[0]=a[N-1];

    int stackpos = 1;
    stackpos--;
    int I = left[stackpos];
    int r = right[stackpos];

    int M=median(a);

    int i=I;
    int j=r;

    partition(a,i,M,j);

    if (i<=j) {
        while (a[i] < M) {
            i++;
        }
    }

    if (i<r) { //10.
        left[stackpos]=i;
        right[stackpos]=r;
        stackpos++;
    }
    r=j;  //11.
    if (I<r) {
        while(true) {
            M = median(a);
            break;
        }
    }

    if (stackpos>0) {
        while(true) {
            stackpos--;
            I = left[stackpos];
            r = right[stackpos];
            break;
        }
    }
    return a;
}

public static void main(String[] args) {
  int []a = {10, 7, 8, 9, 1, 5};
  a = secondMethod(a);
  System.out.println("result :");
  for (int i = 0; i <  a.length; i++)
    System.out.print(a[i] + " ");
  }
}

Answer 1

有几件事是不对的。

right[0]=a[N-1];   # <-------------- pretty sure this should just be N-1, not a[N-1]

第二个，也许更糟糕的是，分区只被调用一次。

你得把整件事想清楚。您解释算法的方式和立即突破的while(true)循环使这一点变得显而易见。

我的建议是:先做一个递归的快速排序，让自己熟悉算法。也是为了摆脱你的反复思维。然后熟悉将递归转换为迭代方法的一般方法(堆栈、动态规划)。然后把你所学到的东西应用到快速排序中。

如果您愿意，您当然可以在线寻找迭代的快速排序实现。我找到了一个使用堆栈而不是递归的。老实说，这是一个很好的练习，但我怀疑快速排序是否真的能从迭代中获益。然而，其他算法肯定是这样的，所以实践总是很好的。