快速排序递归

Question

所以我已经成功实现了每次都使用最左边的元素作为基准的快速排序。我一直在尝试使用中间元素实现快速排序并得到一些复杂的结果。我一直在处理快速排序递归调用自身而不在任何类型的条件下包装调用的示例，正如您可能想象的那样，它在第一次调用自身时卡住了。

第一次调用分区与我使用的样本正确地分区数组，然后当它接近尾声时，只是一遍又一遍地交换开头的两个元素。

我尝试的策略是从列表中选择中间元素作为基准，将其存放在数组的末尾，然后继续交换索引。传递完成后，我将枢轴放在分区数组之间。几次通过后看起来不错，但正如我所提到的，早期卡住并且永远不会进行应该对第二个分区进行排序的调用。

如有任何建议，我将不胜感激 - 我也在 groovy 工作，如果您发现任何问题（希望这不会造成任何问题，但我避免为此

原数组为

[100, 305, 2, 2002, 18, 99, 211, 30, 50, 1000, 403, 4, 400, 77]

并且当达到堆栈溢出时数组为

[2, 4, 18, 30, 50, 99, 77, 100, 211, 1000, 403, 305, 400, 2002]

class OtherQuickSort {

static void sort(int[] array){

    quickSort(array, 0, array.length - 1)

}

static void quickSort(int[] array, int first, int last){
        int pivotIndex = partition(array, first, last)

        quickSort(array, first, pivotIndex - 1)
        quickSort(array, pivotIndex, last)
}

static int partition(int[] array, int first, int last){
    int pivotIndex = (first + last) / 2
    int pivotValue = array[pivotIndex]

    swapIndices(array, pivotIndex, last)

    int indexFromRight = last - 1
    int indexFromLeft = first

    while(indexFromLeft <= indexFromRight){
        while(array[indexFromLeft] < pivotValue){
            indexFromLeft++
        }
        while(array[indexFromRight] > pivotValue){
            indexFromRight--
        }

        if(indexFromLeft <= indexFromRight) {
            swapIndices(array, indexFromLeft, indexFromRight)
            indexFromLeft++
            indexFromRight--
        }
    }

    swapIndices(array, indexFromLeft, last)

    indexFromLeft
}

static void swapIndices(int[] array, int left, int right){
    int leftValue = array[left]
    array[left] = array[right]
    array[right] = leftValue
}
}

Answer 1

您需要更新您的快速排序方法。 pivotIndex 的值已经在其排序位置，因此您无需再次传递它。

static void quickSort(int[] array, int first, int last){
    if(last > first){
        int pivotIndex = partition(array, first, last);

        quickSort(array, first, pivotIndex-1);
        quickSort(array, pivotIndex+1, last);
    }
}

快速排序递归

Quicksort Recursion

sorting

recursion

groovy

quicksort