C++数据结构与算法快速排序
时间: 2023-07-12 15:40:10 浏览: 86
快速排序是一种常见的排序算法,其基本思想是通过划分将待排序序列分成左右两个子序列,左子序列的元素均小于右子序列的元素,然后对左右子序列分别进行递归排序,直到整个序列有序为止。以下是C++实现快速排序的代码:
```c++
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
if (left < j) {
quickSort(arr, left, j);
}
if (i < right) {
quickSort(arr, i, right);
}
}
```
其中,参数arr为待排序的数组,left和right分别表示数组的左右边界。pivot是基准值,可以选择数组中的任意一个元素。在排序过程中,将左右两个指针分别从数组两端向中间移动,当左指针指向的元素大于等于基准值,右指针指向的元素小于等于基准值时,交换两个元素的位置。重复这个过程直到左指针大于右指针,然后对左右两个子序列分别递归排序。