亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

如何處理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
舟曲县| 彭阳县| 菏泽市| 凤庆县| 宁南县| 连平县| 金川县| 闽侯县| 天台县| 定南县| 武乡县| 霸州市| 云阳县| 环江| 福清市| 陇川县| 宁化县| 嘉义县| 子长县| 德江县| 陆河县| 靖安县| 枣阳市| 富锦市| 仪征市| 灵石县| 浙江省| 苏尼特右旗| 宽甸| 淳化县| 重庆市| 资源县| 乐东| 洪湖市| 治多县| 岳阳县| 连南| 虹口区| 鹤庆县| 通化县| 黑水县|