c++ 快速排序 一个函数
时间: 2024-05-09 12:11:43 浏览: 9
C++中的快速排序是一种常用的排序算法,它基于分治的思想。下面是一个实现快速排序的函数:
```cpp
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high); // 将数组划分为两部分,并返回枢轴的位置
quickSort(arr, low, pivot - 1); // 对枢轴左边的子数组进行快速排序
quickSort(arr, pivot + 1, high); // 对枢轴右边的子数组进行快速排序
}
}
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为枢轴
int i = low - 1; // i指向小于枢轴的元素的位置
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]); // 将小于枢轴的元素交换到左侧
}
}
swap(arr[i + 1], arr[high]); // 将枢轴放置到正确的位置
return i + 1; // 返回枢轴的位置
}
```
这个函数接受一个整型数组 `arr`,以及数组的起始索引 `low` 和结束索引 `high`。它首先选择一个枢轴元素,然后将数组划分为两部分,使得左侧的元素都小于枢轴,右侧的元素都大于枢轴。然后递归地对左右两部分进行快速排序,直到排序完成。