c++

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

小樊
83
2024-08-28 00:34:13
栏目: 编程语言

在C++中,实现快速排序(Quick Sort)算法时,需要注意以下边界情况:

  1. 空数组或只有一个元素的数组:这种情况下,数组已经是有序的,不需要进行任何操作。可以直接返回。

  2. 数组中所有元素都相同:这种情况下,快速排序仍然适用,不会影响结果。但是为了提高效率,可以考虑使用其他排序算法,如计数排序(Counting Sort)。

  3. 递归调用栈溢出:当数组规模非常大时,递归调用可能导致栈溢出。为了避免这种情况,可以考虑使用尾递归优化(Tail Recursion Optimization)或改用迭代实现。

  4. 最坏情况下的划分:在最坏情况下,每次划分只能将数组分成一个元素和剩余元素。这将导致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
看了该问题的人还看了