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

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 index

arr[pivotIndex] = arr[right]; // assumes right IS the last index