请用【c+】帮我写一段快排代码,并帮我讲解下实现逻辑
时间: 2024-10-19 07:10:25 浏览: 32
当然可以。以下是使用 C++ 编写的快速排序(Quicksort)算法的简单示例:
```cpp
#include <iostream>
// 选择枢轴元素并分割数组
void partition(int arr[], int low, int high) {
int pivot = arr[high]; // 最后一个元素作为枢轴
int i = (low - 1); // 小于枢轴的元素索引
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) { // 如果当前元素小于枢轴
i++; // 移动指针到右侧
std::swap(arr[i], arr[j]); // 交换元素位置
}
}
std::swap(arr[i + 1], arr[high]); // 将枢轴放在正确的位置
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
// 找到分区点
int pi = partition(arr, low, high);
// 对左右两侧分别递归调用 quickSort
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// 主函数用于测试
int main() {
int data[] = {9, 7, 5, 11, 12, 2, 14, 3, 10};
int n = sizeof(data) / sizeof(data[0]);
quickSort(data, 0, n - 1);
std::cout << "Sorted array: \n";
for (int i = 0; i < n; i++)
std::cout << data[i] << " ";
return 0;
}
```
**实现逻辑解释**:
1. **partition 函数**:它选取数组的最后一个元素作为枢轴(pivot)。然后从左到右遍历数组,如果遇到比枢轴小的元素,就将其与i位置的元素交换,并将i加一。最后,把枢轴放到正确的位置(即所有小于它的元素都在其左边,大于等于它的元素在其右边)。
2. **quickSort 函数**:这个是主函数,接收三个参数:待排序数组、低界和高界。如果低界小于高界,说明还有未排序的部分,于是找到当前部分的分区点(pi),然后对左侧(low 到 pi - 1)和右侧(pi + 1 到 high)分别递归调用 quickSort。
3. **main 函数**:这里创建了一个示例数组,调用 quickSort 进行排序,并打印出排序后的结果。
阅读全文