在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;
}
這個實現首先檢查邊界情況,然后隨機選取主元進行劃分,以避免最壞情況。