2

我刚刚从书中实现了快速排序算法并得到了奇怪的输出。它可以工作，但它按降序而不是升序排序。例如： [1, 5, 2, 10, 6, 9, 8, 3, 7, 4] 排序 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] 似乎不能在我的代码中找到源代码：

private void quicksort(int[] A, int p, int r) {
    if (p < r) {
        int q = partition(A, p, r);
        quicksort(A, p, q);
        quicksort(A, q + 1, r);
    }
}

private int partition(int[] A, int p, int r) {
    int x = A[p]; // pivot
    int i = p;
    int j = r;
    while (true) {

        while (A[i] > x) {
            i++;
        }

        while (A[j] < x) {
            j--;
        }
        if (i < j) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        } else {
            return j;
        }
    }
}

初次通话：

   quicksort(A, 0, A.length - 1);

如何计算快速排序的空间复杂度？

谢谢你们

4

2 回答 2

4

它在您的分区函数中，您按降序排序。

 while(true) {
 //ignore all the numbers greater than X to left
 while (A[i] > x) {
        i++;
    }
 //ignore all numbers lesser than X to right
 while (A[j] < x) {
        j--;
 }

 //swap a number lesser than X on left with a number greater than X on right
    if (i < j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
        i++;
        j--;
    } else {
        //Now the array is so sorted, that all numbers lesser than X are on right of it and greater than X are to left of it. Hence return position of X
        return j;
    }
 }

//对于升序：

 while(true) {

 while (A[i] < x) {
        i++;
 }

 while (A[j] > x) {
        j--;
 }

    if (i < j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
        i++;
        j--;
    } else {
        return j;
    }
}
于 2012-06-25T20:14:35.847 回答
0

这里要注意的关键点是在分区期间创建所有小于枢轴的元素和所有大于枢轴的元素的窗口的部分。您的实现是确保在分区结束时，数组的左半部分将具有大于枢轴的所有元素，而右半部将具有小于枢轴的所有元素。只需执行相反的操作即可使其按升序排列

while (A[i] < x) {
    i++;
}

while (A[j] > x) {
    j--;
}

于 2021-04-11T10:24:30.627 回答