快速排序疑难解答 (C++)

Question

我需要测量系统执行排序算法所需的时间。除了快速排序之外，我已经完成了所有工作。旁注，我不知道如何以毫秒为单位测量时间，所以如果有人知道如何做到这一点，我会洗耳恭听。基本上，为了解决这个问题，我需要使用大量数组。问题是，当使用大约 500-1000 以上的数组时，我的快速排序算法会失败。我不再收到任何堆栈溢出错误，但它继续运行相当长的时间（用于执行函数）。我曾多次看到它运行超过 40 或 50 秒。我不确定如何优化/修复代码。我已经排查问题一段时间了。

我希望每次运行代码时该函数都会运行。我尝试过在分区中搞乱 while 循环，调整递归开始/结束输入。较小的一侧首先优化似乎根本没有运行（也许我做错了）。任何提示将不胜感激，谢谢！

您需要提供所有代码以及输入数组和大小变量，函数才能正常工作。

这是快速排序算法：

//partitioning for quick sort
int partition(int arr[], int start, int end) {
    int pivot = arr[start]; //array is randomly generated, so pivot selection is trivial
    int i = start + 1;
    int j = end;

    while (i < j) { //While I is less than J, increment closer to the pivot until a suitable switch is found.
        while (i <= j && arr[i] < pivot)
            i++;
        while (i <= j && arr[j] > pivot)
            j--;
        if (i < j)
            swap(arr, i, j);    //suitable match found, switch i and j only if theyre not out of scope of their proper placement
        else
            break;
    }
    swap(arr, start, j);    //put pivot in its correct position

    return j;
}

//Recursive Function for quick sort
void quickSort(int arr[], int start, int end) {
    if (start < end) { //as long as the array length is more than 1, continue recursing
        int p = partition(arr, start, end);

        if (p > start)
            quickSort(arr, start, p - 1); // Left side recursion
        if (p < end)
            quickSort(arr, p + 1, end); //right side recursion
    }
}

int main() {
//initialization of arrays, and array qualities
    const int size = 20000;
    int max = 0x80000000;
    int min = 0x7FFFFFFF;
    int *arr = new int [size];
    int *arrC1 = new int[size];
    int *arrC2 = new int[size];
    int *arrC3 = new int[size];
    int *arrC4 = new int [size];
    bool passed = true;
    bool sameArr = true;

//Random generation seeded by the time of day
    srand(static_cast<unsigned>(time(0)));

// Creation and printing of unsorted array  
    for (int i = 0; i < size; i++) {
        arr[i] = rand();
    }


//copying of array, along with ensuring they are the same
    for (int i = 0; i < size - 1; i++) {
        arrC1[i] = arr[i];
        arrC2[i] = arr[i];
        arrC3[i] = arr[i];
        arrC4[i] = arr[i];
    }
    for (int i = 0; i < size - 1; i++) {
        if (arr[i] != arrC1[i] || arrC1[i] != arrC2[i] || arrC2[i] != arrC3[i] || arrC3[i] != arrC4[i])
            sameArr = false;
    }
    cout << "Same Array (1 for true, 0 for false)? " << sameArr << endl;


//Run and test Quick sort algorithm
    passed = true;  //reset bool for further use

    start = getTime();
    quickSort(arrC2, 0, size - 1);
    finish = getTime();

    cout << "QUICK SORT:_______________" << endl;
    cout << "Time Elapsed:          " << chrono::duration_cast<chrono::milliseconds>(finish - start).count() << endl;
    for (int i = 1; i < size - 1; i++) {
        if (arrC2[i - 1] > arrC2[i])
            passed = false;
    }
    cout << "Array ordering: " << passed << endl;




    delete[] arr;
    delete[] arrC1;
    delete[] arrC2;
    delete[] arrC3;
    delete[] arrC4;
    return 0;
}

Answer 1

您面临的问题可能是由于当输入数组已排序或接近排序时，QuickSort 的最坏情况时间复杂度为 O(n^2)。这是因为在这些情况下，您使用的主元选择策略（始终选择第一个元素）会导致分区非常不平衡。

为了提高快速排序的性能，可以使用更好的主元选择策略，例如选择数组的第一个、中间和最后一个元素的中位数。这将导致更平衡的分区和更好的平均情况时间复杂度。

以下是如何修改

partition

函数以使用此枢轴选择策略：

int partition(int arr[], int start, int end) {
    // Choose the median of the first, middle, and last elements as the pivot
    int mid = start + (end - start) / 2;
    int pivotIndex = (arr[start] < arr[mid]) == (arr[mid] < arr[end]) ? mid
                     : (arr[start] < arr[end]) == (arr[end] < arr[mid]) ? end : start;
    int pivot = arr[pivotIndex];

    // Swap the pivot with the first element
    swap(arr, start, pivotIndex);

    // Rest of the function remains the same...
}

至于以毫秒为单位测量时间，您已经使用

chrono::duration_cast<chrono::milliseconds>(finish - start).count()

正确地完成了它。这将为您提供以毫秒为单位的经过时间。