快速排序边界问题代码c++
时间: 2024-03-05 11:46:35 浏览: 28
快速排序是一种常用的排序算法,它通过分治法的思想将一个大问题分解为多个小问题来解决。在快速排序中,我们选择一个基准元素,将数组分为两部分,一部分是小于基准元素的,另一部分是大于基准元素的。然后对这两部分分别进行递归排序,最终得到有序的数组。
下面是C++实现的快速排序代码,其中包括了边界问题的处理[^1][^2]:
```cpp
#include <iostream>
using namespace std;
// 交换两个元素的值
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 将数组分为两部分,并返回基准元素的索引
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准元素
int i = (low - 1); // i指向小于基准元素的位置
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于等于基准元素,则将其放到左边
if (arr] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); // 将基准元素放到正确的位置
return (i + 1);
}
// 快速排序函数
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high); // 获取基准元素的索引
// 对基准元素左边的子数组进行排序
quickSort(arr, low, pi - 1);
// 对基准元素右边的子数组进行排序
quickSort(arr, pi + 1, high);
}
}
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
这段代码实现了快速排序算法,并对一个示例数组进行排序。你可以根据需要修改数组的内容和大小,然后运行代码查看排序结果。