我的快速排序实现使用了太多比较但无法确定原因

Question

我正在尝试在 Java 中实现快速排序，并且正在努力以有效的方式实现它。我相信问题出在我的递归调用上，但我无法确定如何解决它。我正在使用比较来查看进行了多少次比较，以期确定问题出在哪里。我唯一能想到的是在我的递归语句周围需要一个条件，因为无论输入的数组是否已经排序或看似随机，所需的比较量都是相同的。

public int quickSort(int[] arr, int left, int right) {

    //left is lowest index

    //right is highest index

    int compares = 0;

    //calls insertion sort once subsets get smaller than 7 elements

    if (right - left < 6) {

      compares += insertSort(arr, left, right);

      return compares;

    }

        //calculate random pivot

        int pivotIndex = randomInt(left, right);

        int pivotValue = arr[pivotIndex];

        //moves pivot value to rightmost index

        int temp;

        temp = arr[pivotIndex];

        arr[pivotIndex] = arr[right];

        arr[right] = temp;

        int pivotFinal = left;

        //determines how many values are lower than the pivot, swapping 

        //smaller values with larger values along the way

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

            compares++;

            if (arr[i] <= pivotValue) {

                temp = arr[i];

                arr[i] = arr[pivotFinal];

                arr[pivotFinal] = temp;

                pivotFinal++;

            }

        }

        //moves pivot to final position so that quicksort is complete

        temp = arr[pivotFinal];

        arr[pivotFinal] = arr[right];

        arr[right] = temp;

        compares += quickSort(arr, left, pivotIndex - 1);

        compares += quickSort(arr, pivotIndex + 1, right);

        return compares;

}

public void main() {

    QuickSort qs = new QuickSort();

    int n = 60;

    int[] array = qs.GenerateRandomSequence(n);

    int compares = qs.quickSort(array);

}

当 n 为 60 时，其中一个序列需要超过 400 万次比较，这比实际的最坏情况运行时要差得多。

Answer 1

您的索引有几个错误。您的递归需要使用您的最终支点位置。compares += quickSort(arr, left, pivotFinal - 1);compares += quickSort(arr, pivotFinal + 1, right);你在不同的地方以不同的方式对待你的“正确”索引。可能最容易在循环中使用“<=”for (int i = left; i < right; i++) // assumes right is after the last indexarr[pivotIndex] = arr[right]; // assumes right IS the last index