快速排序执行错误的java

我在做什么错误的，我下面的quicksort实现：快速排序执行错误的java

public static void quicksort(int[] array, int start, int end) { 
    while (start < end) { 
     int pIndex = partition(array, start, end); 
     quicksort(array, start, pIndex - 1); 
     quicksort(array, pIndex + 1, end); 
    } 
} 

public static int partition(int[] array, int start, int end) { 
    int pivot = array[end]; 
    int pIndex = start; 
    for (int i = start; i <= end - 1; i++) { 
     if (array[i] <= pivot) { 
      int tmp = array[pIndex]; // swap values 
      array[pIndex] = array[i]; 
      array[i] = tmp; 
      pIndex++; 
     } 
    } 
    int tmpVal = array[pIndex]; 
    array[pIndex] = pivot; 
    array[end] = tmpVal; 
    return pIndex; 
}

当运行此针对数组{的测试用例7,5，3，6，8，1，2， 4}，它将数组重新排列为{1,2,3,4,8,5,7,6}，在那里它排列数组的左边，然后输入似乎是无限循环的数组{ 1，2}并且永不离开递归调用。我已经尝试添加一个基本的情况下，如果array.length小于2，然后返回;但这没有什么区别。

这是我的code的链接。

任何人都知道什么可能是错的？

来源

2015-09-07 OpMt

是我们必然要使用现有的代码，或者我们可以把它扔掉，并开始了新的？ –

我现有的代码，因为我们试图调试这个实现XD – OpMt

你的循环

for (int i = 0; i <= end - 1; i++) {

在partition应该

for (int i = start; i <= end - 1; i++) {

有了出这是你的p食指可以为您的recusive调用快速排序将具有相同start到end，那边范围之外参数。

编辑

未上面显示与ideone代码的另一个问题是

if (array.length < 2) { return; }

在quicksort你不改变你的阵列的长度，以便array.length将总是8.

第三个问题，导致无限循环的问题是

while (start < end) {

在quicksort之内您在此循环期间没有更改开始或结束的值，因此此循环将永远不会退出。有关工作示例，请参阅https://ideone.com/wY23C6。

来源

2015-09-07 04:57:34

这并没有解决这个错误，它仍然在同一个地方循环，我编辑我的链接代码。但它仍然不起作用。 – OpMt

while (start < end) { 
    int pIndex = partition(array, start, end); 
    quicksort(array, start, pIndex - 1); 
    quicksort(array, pIndex + 1, end); 
}

应该

if (start < end) { 
    int pIndex = partition(array, start, end); 
    quicksort(array, start, pIndex - 1); 
    quicksort(array, pIndex + 1, end); 
}

来源

2015-09-07 05:15:29 Atvoid

快速排序执行错误的java

回答

相关问题