当数组有重复值时，为什么快速排序算法持续时间会增加？

Question

我正在尝试使用 std::chrono 时间计算并使用某个范围 [A, B] 内随机生成的整数数组来测量合并排序和快速排序函数的持续时间，数组的大小从 5000 到 100,000 个整数不等。

我的代码的目标是证明当在快速排序中选择（枢轴）的方法得到改进时，快速排序函数最终比合并排序花费更少的时间来处理数组，我选择枢轴的方式是使用随机索引方法来最小化复杂度为 (n^2) 的概率，但是在我将在下面描述的某些情况下，快速排序最终比合并排序花费更多的时间，我想知道为什么会发生这种情况。

情况1：数组中数字的范围很小，这增加了数组中出现重复数字的可能性。

情况 2：当我使用像 clion 这样的本地 IDE 时，快速排序功能比合并排序花费更多的时间，但是像 IDEONE.com 这样的在线编译器在两种排序算法中给出相似的结果（即使生成的整数的范围是小的）

这是我在上述案例中得到的结果（第一行数字是合并排序结果，第二行是快速排序结果）：

1-clion 结果范围很窄（-100、600）

2-clion 结果具有广泛的数字 (INT_MIN, INT_MAX)

3-IDEONE 结果的数字范围很窄（-100、600）

4- IDEONE 结果的范围很广（INT_MIN、INT_MAX）

#include <bits/stdc++.h>
#include <chrono>
#include <random>

using namespace std;

mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
int* generateArray(int size)
{
    int* arr = new int[size];
    uniform_int_distribution<> distribution(INT_MIN, INT_MAX);
    for (int i=0; i < size; ++i)
    {
        arr[i] = distribution(gen);
    }
    return arr;
}
void merge(int* leftArr, int nL, int* rightArr, int nR, int* mainArr)
{
    int i=0, j=0, k=0;
    while (i < nL && j < nR)
    {
        if (leftArr[i] < rightArr[j]) { mainArr[k++] = leftArr[i++]; }
        else { mainArr[k++] = rightArr[j++]; }
    }
    while (i < nL){ mainArr[k++] = leftArr[i++]; }
    while (j < nR){ mainArr[k++] = rightArr[j++]; }
}
void mergeSort (int* mainArray, int arrayLength)
{
    if (arrayLength < 2) { return; }
    int mid = arrayLength/2;
    int* leftArray = new int[mid];
    int* rightArray = new int[arrayLength - mid];
    for (int i=0; i<mid; ++i) {leftArray[i] = mainArray[i];}
    for (int i = mid; i<arrayLength; ++i) {rightArray[i - mid] = mainArray[i];}
    mergeSort(leftArray, mid);
    mergeSort(rightArray, arrayLength-mid);
    merge(leftArray, mid, rightArray, arrayLength-mid, mainArray);
    delete[] leftArray;
    delete[] rightArray;
}


int partition (int* arr, int left, int right)
{
    uniform_int_distribution<> distribution(left, right);
    int idx = distribution(gen);
    swap(arr[right], arr[idx]);
    int pivot = arr[right];
    int partitionIndex = left;
    for (int i = left; i < right; ++i)
    {
        if (arr[i] <= pivot)
        {
            swap(arr[i], arr[partitionIndex]);
            partitionIndex++;
        }
    }
    swap(arr[right], arr[partitionIndex]);
    return partitionIndex;
}
void quickSort (int* arr, int left, int right)
{
    if(left < right)
    {
        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
}

int main()
{
    vector <long long> mergeDuration;
    vector <long long> quickDuration;
    for (int i = 5000; i<= 100000; i += 5000)
    {
        int* arr = generateArray(i);
        auto startTime = chrono::high_resolution_clock::now();
        quickSort(arr, 0, i - 1);
        auto endTime = chrono::high_resolution_clock::now();
        long long duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
        quickDuration.push_back(duration);
        delete[] arr;
    }
    for (int i = 5000; i <= 100000; i += 5000 )
    {
        int* arr = generateArray(i);
        auto startTime = chrono::high_resolution_clock::now();
        mergeSort(arr, i);
        auto endTime = chrono::high_resolution_clock::now();
        long long duration = chrono::duration_cast<chrono::milliseconds>(endTime - startTime).count();
        mergeDuration.push_back(duration);
        delete[] arr;
    }
    for (int i = 0; i<mergeDuration.size(); ++i)
    {
        cout << mergeDuration[i] << " ";
    }
    cout  << endl;
    for (int i = 0; i<quickDuration.size(); ++i)
    {
        cout << quickDuration[i] << " ";
    }
}

Answer 1

众所周知，当输入集包含大量重复项时，快速排序会表现出较差的性能。解决方案是使用维基百科上描述的三向分区：

重复元素

使用上面描述的分区算法（即使是选择好的主元值），快速排序对于包含许多重复元素的输入表现出较差的性能。当所有输入元素都相等时，问题就很明显了：在每次递归时，左分区为空（没有输入值小于主元），而右分区仅减少了一个元素（删除了主元）。因此，该算法需要 二次时间来对相等值的数组进行排序。

为了解决这个问题（有时称为荷兰国旗问题），可以使用替代的线性时间分区例程将值分成三组：小于枢轴的值、等于枢轴的值和大于枢轴的值. ... 等于主元的值已经排序，所以只有小于和大于分区需要递归排序。在伪代码中，快速排序算法变为

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := pivot(A, lo, hi)
        left, right := partition(A, p, lo, hi)  // note: multiple return values
        quicksort(A, lo, left - 1)
        quicksort(A, right + 1, hi)

分区算法返回指向中间分区的第一个（“最左边”）和最后一个（“最右边”）项的索引。分区的每一项都等于 p，因此被排序。因此，分区的项目不需要包含在对快速排序的递归调用中。

以下修改quickSort给出了更好的结果：

pair<int,int> partition(int* arr, int left, int right)
{
    int idx = left + (right - left) / 2;
    int pivot = arr[idx]; // to be improved to median-of-three
    int i = left, j = left, b = right - 1;
    while (j <= b) {
        auto x = arr[j];
        if (x < pivot) {
            swap(arr[i], arr[j]);
            i++;
            j++;
        } else if (x > pivot) {
            swap(arr[j], arr[b]);
            b--;
        } else {
            j++;
        }
    }
    return { i, j };
}
void quickSort(int* arr, int left, int right)
{
    if (left < right)
    {
        pair<int, int> part = partition(arr, left, right);
        quickSort(arr, left, part.first);
        quickSort(arr, part.second, right);
    }
}

输出：

0 1 2 3 4 5 6 7 8 9 11 11 12 13 14 15 16 19 18 19
0 0 0 1 0 1 1 1 1 1 2 3 2 2 2 2 3 3 3 3

0 1 2 3 4 5 6 6 8 8 9 12 11 12 13 14 16 17 18 19
0 0 1 1 1 2 3 3 3 4 4 4 5 6 5 6 7 7 8 8

因此，具有大量重复项的运行现在要快得多。