C++中的快速排序(Quick Sort)是一種高效的排序算法,其基本思想是通過選取一個基準元素,將數組分為兩部分,使得一部分的元素都小于基準元素,另一部分的元素都大于基準元素,然后對這兩部分遞歸地進行快速排序。
以下是一個簡單的C++快速排序實現:
#include<iostream>
#include<vector>
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) {
int pivotIndex = partition(arr, low, high); // 獲取基準元素的索引
quickSort(arr, low, pivotIndex - 1); // 對左側子數組進行快速排序
quickSort(arr, pivotIndex + 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 = 0; i < arr.size(); i++) {
cout<< arr[i] << " ";
}
cout<< endl;
return 0;
}
這個實現中,partition
函數用于將數組劃分為兩部分,quickSort
函數則是遞歸地對這兩部分進行排序。在main
函數中,我們創建了一個包含一些整數的向量,并調用quickSort
函數對其進行排序。最后,我們打印出排序后的結果。