如何处理c++快排函数的边界情况 - 问答

在C++中，实现快速排序（Quick Sort）算法时，需要注意以下边界情况：

空数组或只有一个元素的数组：这种情况下，数组已经是有序的，不需要进行任何操作。可以直接返回。
数组中所有元素都相同：这种情况下，快速排序仍然适用，不会影响结果。但是为了提高效率，可以考虑使用其他排序算法，如计数排序（Counting Sort）。
递归调用栈溢出：当数组规模非常大时，递归调用可能导致栈溢出。为了避免这种情况，可以考虑使用尾递归优化（Tail Recursion Optimization）或改用迭代实现。
最坏情况下的划分：在最坏情况下，每次划分只能将数组分成一个元素和剩余元素。这将导致O(n^2)的时间复杂度。为了避免这种情况，可以采用随机选取主元（Pivot）的方法，使得每次划分都能接近平均情况。

下面是一个处理了上述边界情况的C++快速排序实现：

#include<iostream>
#include<vector>
#include<algorithm>
#include <ctime>
#include <cstdlib>

using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    while (low< high) {
        while (low< high && arr[high] >= pivot) {
            high--;
        }
        arr[low] = arr[high];
        while (low< high && arr[low] <= pivot) {
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low >= high) {
        return;
    }

    srand(time(0));
    int pivotIndex = low + rand() % (high - low + 1);
    swap(arr[pivotIndex], arr[low]);

    int pivot = partition(arr, low, high);
    quickSort(arr, low, pivot - 1);
    quickSort(arr, pivot + 1, high);
}

int main() {
    vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    quickSort(arr, 0, arr.size() - 1);

    for (int i : arr) {
        cout << i << " ";
    }
    cout<< endl;

    return 0;
}

这个实现首先检查边界情况，然后随机选取主元进行划分，以避免最坏情况。

0 赞

0 踩