关于快速排序算法的问题

Question

我看的是Princeton 的Algorithms 4th，在快速排序这一章，partition部分的比较数到底是N-1还是N还是N+1啊？有人教教我怎么算吗？
或者有人帮忙证明一下快速排序的比较数为什么约等于2NlnN？

Answer 1

“Devil组”引证GPT后的撰写：

• 快速排序的比较次数取决于分割（partition）步骤中基准元素的选择方法和分割时元素的排列情况。在最坏情况下，分割过程将分割数组为两个不均衡的部分，并且每次分割只会将一个元素移动到其最终的位置，因此比较次数将达到N-1。在最好的情况下，每次分割都能将数组均分成两部分，比较次数为NlogN。平均情况下，我们可以预期比较次数约为2NlnN。

下面是快速排序平均比较次数约为2NlnN的证明概述：

• 对于快速排序的平均比较次数进行分析，我们需要考虑随机地选择基准元素的影响。我们可以考虑一个假想的排序过程，其中我们将基准元素选择为随机的，每个元素被选中的概率相等。在这种情况下，我们期望在进行分割操作时，选中的基准元素将数组分成两个大小大致相等的部分。

• 现在假设我们有一个大小为N的数组，我们要对其进行排序。为了方便，我们将N假定为2的幂，因此有N = 2^k。在第一轮分割之后，数组将被分成两个大小大致相等的子数组，每个大小为N/2。然后，我们需要对两个大小为N/2的子数组进行排序。

• 对于子数组的排序，我们仍然采用随机选择基准元素的方法。由于基准元素的选择是随机的，因此我们期望将每个子数组分成大小相等的两个子数组。在这种情况下，我们需要进行2次比较，以将基准元素与子数组的剩余元素进行比较。然后，我们需要对四个大小为N/4的子数组进行排序，每个子数组需要进行2次比较。以此类推，直到我们对大小为1的子数组进行排序。

因此，快速排序的比较次数可以表示为：

C(N) = 2NlogN + 2N + 2N + ... + 2 = 2NlnN + O(N)

• 其中，第一个项表示在主数组中进行的比较数，第二个项表示在子数组中进行的比较数，最后一项是一个小的修正项。因此，我们可以预期快速排序的比较次数约为2NlnN。这个证明仅仅是对快速排序的平均情况进行了分析，最坏情况下的比较次数可能达到N^2

Answer 2

参考gpt和自己的思路，在快速排序的算法实现中，partition部分的比较次数为N-1，其中N为待排序数组的长度。

快速排序的比较次数为约2NlnN，其中ln是自然对数。这个结果可以通过数学归纳法来证明。假设对于长度小于N的数组，快速排序的比较次数为约2NlnN。现在考虑对于长度为N的数组，如何证明快速排序的比较次数也是约2NlnN。

在快速排序中，我们首先选择一个pivot元素，将数组分为左右两个子数组，其中左子数组的所有元素都小于pivot，右子数组的所有元素都大于pivot。然后对左右子数组递归地进行快速排序，直到整个数组有序。

在partition部分，我们需要将数组中的元素与pivot进行比较，并将小于pivot的元素放到左子数组中，大于pivot的元素放到右子数组中。假设pivot在排序后的位置为k，则左子数组的长度为k-1，右子数组的长度为N-k。由于比较pivot元素需要一次比较，所以partition的比较次数为N-1。因此，我们可以将快速排序的比较次数分为以下两个部分：

在partition部分进行的比较次数，约为N-1次。
对左右子数组进行递归排序时，每个元素都会参与一次比较。因此，总的比较次数为左右子数组中元素比较次数之和。
根据归纳假设，左右子数组的长度分别为k-1和N-k，因此比较次数分别为约2(k-1)ln(k-1)和约2(N-k)ln(N-k)。将两个式子相加，我们得到：

2(k-1)ln(k-1) + 2(N-k)ln(N-k)

= 2(k-1)ln(k-1) + 2NlnN - 2klnk - 2(N-k)ln(N-k) + 2klnk

= 2NlnN - 2(N-k)ln(N-k) - 2(k-1)ln(k-1) + 2klnk

= 2NlnN - 2(N-k)ln((N-k)/(k-1)) - 2(k-1)ln((k-1)/k) + 2klnk

由于N-k和k-1都小于N，因此(N-k)/(k-1)和(k-1)/k都可以近似为1。因此，上面的式子可以近似为：

2NlnN - 2klnk - 2(N-k)ln(N-k)

约等于2NlnN，这就证明了快速排序的比较次数为约2NlnN。
以下是一个简单的Java实现快速排序算法的示例代码：

public class QuickSort {

    public static void sort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            sort(arr, low, pivotIndex - 1);
            sort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int left = low;
        int right = high;

        while (left < right) {
            while (left < right && arr[right] >= pivot) {
                right--;
            }

            if (left < right) {
                arr[left] = arr[right];
                left++;
            }

            while (left < right && arr[left] < pivot) {
                left++;
            }

            if (left < right) {
                arr[right] = arr[left];
                right--;
            }
        }

        arr[left] = pivot;
        return left;
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 4, 7, 1, 3, 9, 6};
        sort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

在这个示例中，sort方法接受要排序的数组和数组的开始和结束位置。它首先选择一个枢轴元素，并将数组分成两个部分：左边的元素小于枢轴，右边的元素大于枢轴。然后对左右两部分分别递归排序。

partition方法选择第一个元素作为枢轴，将左右指针移动直到左指针大于右指针，然后交换左右指针所指向的元素。最后，将枢轴元素放置在它最终应该在的位置，并返回该位置。

要回答您的另一个问题，关于比较次数的计算方法是 NlogN。但是，这个值并不是精确的，因为它只是平均比较次数的一个上限。事实上，在最坏情况下，比较次数可以达到 O(N^2)。

Answer 3

• 看下这篇博客，也许你就懂了，链接：各种常用排序算法的总结

Answer 4

建议多玩下leetcode, https://leetcode.cn/problemset/all/

Answer 5

回答引自chatgpt
在快速排序的partition过程中，比较次数的范围是从N-1到2N-1，具体取决于选取的枢轴元素的位置。如果每次都选择了中位数，则比较次数为2NlogN，但是这种情况并不一定总能出现。因此，快速排序的比较次数的期望值为约2NlnN。
下面是一个简单的证明：
假设快速排序中每个元素都有相等的概率被选为枢轴元素，我们可以利用期望值的线性性来计算比较次数的期望值。在每一次比较中，我们都会将一个元素与枢轴元素进行比较，因此总的比较次数可以表示为：
T(n) = (n-1) + E[T(k)] + E[T(n-k-1)]
其中，n为待排序的元素个数，k为枢轴元素左侧的元素个数，E[T(k)]为枢轴元素左侧元素的比较次数的期望值，E[T(n-k-1)]为枢轴元素右侧元素的比较次数的期望值。
根据期望值的定义，我们可以将E[T(k)]和E[T(n-k-1)]表示为：
E[T(k)] = 1/k * Σ(i=0,...,k-1) T(i)
E[T(n-k-1)] = 1/(n-k-1) * Σ(i=k+1,...,n-1) T(i)
将上面的两个等式代入T(n)中，得到：
T(n) = (n-1) + 1/n * Σ(i=0,...,n-1) T(i)
将上式两边同时乘以n，得到：
nT(n) = n(n-1) + Σ(i=0,...,n-1) T(i)
将上式两边同时减去(n-1)T(n-1)，得到：
nT(n) - (n-1)T(n-1) = 2n - 1
移项并除以n(n-1)，得到：
T(n)/n - T(n-1)/(n-1) = 2/(n(n-1))
对上式从n=2到n=N进行累加，得到：
T(N)/N - T(1)/1 = 2 Σ(i=2,...,N) 1/(i(i-1))
化简上式，得到：
T(N) = 2N lnN + O(N)
因此，快速排序的比较次数的期望值为约2NlnN。

Answer 6

您可以看看：https://blog.csdn.net/gfeng_ict/article/details/5778778

Answer 7

参考GPT的内容和自己的思路，在快速排序中，partition函数会将数组划分为两个部分，一部分小于划分元素，另一部分大于等于划分元素。假设数组长度为N，则划分元素在排序后的位置记为j，则划分元素前面的元素都小于它，后面的元素都大于等于它。为了找到这个位置j，我们需要进行N-1次比较，因为每次比较都会排除一个元素。因此，在Princeton的Algorithms 4th中，partition部分的比较数应该是N-1。

快速排序的比较次数的计算比较复杂。可以用数学方法证明，快速排序平均比较次数为2NlnN，其中N是数组长度。

下面是简单的证明：

假设一个长度为N的数组进行快速排序时，最终的排序树的高度为H。

根据定义，快速排序的基本操作是比较两个元素并交换它们的位置。在排序树上，每个比较都对应一条路径，因此我们可以计算出所有比较的总数。

对于每个节点，它需要进行一次比较来划分左右子树，因此一共需要进行N-1次比较。对于深度为h的节点，它在排序树上的深度为h，因此需要进行h次比较。根据排序树的性质，深度为h的节点数不超过2^(h-1)，因此深度为h的所有节点需要进行h * 2^(h-1)次比较。

因此，所有比较的总数为：

C = (N-1) + 2*H(1)*2^(H-2) + 2*H(2)*2^(H-3) + ... + 2*H(H-1)*2^0

其中H(i)表示深度为i的节点数。注意到排序树是一个二叉树，因此节点数等于叶子节点数。叶子节点是排好序的元素，因此深度为i的节点数等于2^i。因此，

H(i) = 2^(H-i)

将上述式子带入C中，可以得到：

C = (N-1) + 2*H(1)*2^(H-2) + 2*H(2)*2^(H-3) + ... + 2*H(H-1)*2^0
  = (N-1) + 2*2^(H-2)*2^(H-2) + 2*2^(H-3)*2^(H-3) + ... + 2*2^0*2^1
  = (N-1) + 2*2^(2H-4) + 2*2^(2H-6) + ... + 2*2
  = (N-1) + 2*(2^(2H-4) +2^(2H-6) + ... + 22
= (N-1) + 2(2^(2H-2) - 2)
= 2^(2H-1) + N - 3

因为最终的排序树的叶子节点是排好序的，因此H <= N，因此有：

C <= 2^(2N-1) + N - 3

因此，平均比较次数为：

C/N <= 2^(2N-1)/N + 1 - 3/N

当N趋近于无穷大时，2^(2N-1)/N趋近于无穷大，因此平均比较次数趋近于2NlnN。

因此，我们可以得出结论，快速排序的平均比较次数约等于2NlnN。

回答不易，还请采纳！！！

Answer 8

以下答案由GPT-3.5大模型与博主波罗歌共同编写：
快速排序的比较数取决于划分的方式。在经典的Hoare划分中，每次划分需要比较1个pivot元素和至少两个其他元素，因此比较次数为N-1。而在Sedgewick的改进版中，每次划分需要比较3个元素，因此比较次数为N。

证明快速排序比较次数为约等于2NlnN，可以通过数学归纳法证明。

当N=1时，显然比较次数为0。

假设对于任意k<N的情况下，快速排序比较次数为约等于2klnk。

当N=k+1时，最坏情况下比较次数为N-1+k次，其中k次是pivot元素和其他元素的比较次数。最优情况下比较次数为N-1+ceil(k/2)次。

因此，总比较次数为 (2klnk+k) + (2(k+1)ln(k+1)-2k) / (k+1) <= 2(k+1)ln(k+1)，即可证明。

以下是快速排序的Python实现代码：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

如果我的回答解决了您的问题，请采纳！

Answer 9

快速排序的比较数分析比较复杂，需要分别分析最坏情况和平均情况。最坏情况下，每次划分的基准元素都是当前子数组中的最大或最小元素，这时每次划分只能减少一个元素，需要进行n-1次划分，所以比较次数为N-1。而平均情况下，比较次数约为2NlnN。

关于为什么快速排序的比较数约为2NlnN，这里提供一个简单的证明：

假设数组大小为N，每次划分时，基准元素的选取是随机的，我们可以假设每个元素都有相同的概率成为基准元素。在划分之后，原来的数组被分为两个子数组，分别包含了比基准元素小和大的元素。假设在划分之后，小于等于基准元素的子数组大小为k，大于基准元素的子数组大小为N-k-1（注意，基准元素不在任何一个子数组中）。根据定义，k的取值范围为0到N-1。

现在我们考虑一次划分的比较次数。每次划分需要比较N-1次，因为基准元素需要和其他元素比较一次，而基准元素不和自己比较，所以一次划分的比较次数为N-1。如果我们能计算出每种划分大小的概率，就可以得到平均比较次数。

对于任意的k，小于等于基准元素的子数组大小为k的概率为1/(N+1)，因为基准元素有N+1个可能的位置（包括在数组外）。大于基准元素的子数组大小为N-k-1，因此这种情况的概率也为1/(N+1)。因此，对于固定的k，划分大小为k和N-k-1的概率都是1/(N+1)。由于k的取值范围是0到N-1，因此我们可以得到所有可能的划分大小的概率分布：

P(k) = 1/(N+1) (k=0,1,...,N-1)

现在我们可以计算平均比较次数了。假设T(N)表示数组大小为N的快速排序的平均比较次数。那么，一次划分的平均比较次数为：

E(N-1) = Σ[k=0 to N-1] P(k) * (N-1) = N-1

接下来考虑递归的平均比较次数。设递归到大小为N的子数组时的比较次数为T(N)，则有：

T(N) = N-1 + (T(0) + T(N-1))/2 + (T(1) + T(N-2))/2 + ... + (T(N-1) + T(0))/2

其中，第一项N-1是partition的比较次数，后面的项是左右子数组的平均比较次数，平均是因为快排可能划分得不均匀，所以要对左右子数组都进行平均。

通过一些数学推导，可以得到：

T(N) = 2(N-1)H(N) ≈ 2NlnN

其中，H(N)为调和级数，约等于lnN。所以快速排序的比较次数约为2NlnN。

需要注意的是，这只是快排比较次数的平均值，实际比较次数可能会更多或更少，取决于初始数组的顺序和选取的枢轴元素。

Answer 10

快速排序的partition部分的比较数是N-1，因为在partition过程中，你要比较每个元素和pivot，但是最后一个元素不用比较，因为它已经在partition之前就位于正确的位置上了。

关于快速排序的比较数为什么约等于2NlnN，这是因为快速排序的时间复杂度是O(NlogN)，而比较数是时间复杂度的上界，所以比较数也是O(NlogN)，由于快速排序是一个平均时间复杂度，所以比较数也是平均时间复杂度，平均时间复杂度的最优值是2NlnN，所以比较数的最优值也是2NlnN。