快速排序是一种常用的排序算法,其基本思想是通过递归地将数组分成两个子数组,然后对这两个子数组分别进行排序。具体步骤如下:
C++实现快速排序的代码示例如下:
void quickSort(vector<int>& arr, int low, int high) {
if (low < high) {
int i = low, j = high, pivot = arr[low];
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
while (i < j && arr[i] < pivot) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivot;
quickSort(arr, low, i - 1);
quickSort(arr, i + 1, high);
}
}
// 使用方法
vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
quickSort(arr, 0, arr.size() - 1);
上述代码中,我们首先选择数组的第一个元素作为基准值,然后根据基准值将数组分成两部分。接着递归地对左右子数组进行排序,最终得到一个有序的数组。