c++快速排序具体实现
时间: 2023-11-11 19:57:45 浏览: 36
快速排序是一种常用的排序算法,其具体实现如下:
```
// 快速排序
void quickSort(int arr[], int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right); // 将数组划分为两个子数组
quickSort(arr, left, pivot - 1); // 对左侧子数组进行快速排序
quickSort(arr, pivot + 1, right); // 对右侧子数组进行快速排序
}
}
// 划分函数
int partition(int arr[], int left, int right) {
int pivot = arr[right]; // 选取最右边的元素作为基准元素
int i = left - 1; // 定义一个指针,指向小于基准元素的区域的最后一个元素
for (int j = left; j < right; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]); // 将小于基准元素的值交换到小于区域的末尾
}
}
swap(arr[i + 1], arr[right]); // 将基准元素放置到正确的位置上
return i + 1; // 返回基准元素的索引位置
}
```
以上是快速排序算法的具体实现。其实现思想是通过选取一个基准元素将数组划分为两个子数组,然后递归地对子数组进行排序。