C++实现快速排序
时间: 2023-06-28 22:05:29 浏览: 54
快速排序是一种常见的排序算法,它的核心思想是分治法。具体实现步骤如下:
1. 选择一个基准元素(通常是第一个或最后一个元素)。
2. 将数组分成两个子数组,小于基准元素的放在左边,大于基准元素的放在右边。
3. 对左右子数组分别递归地进行快速排序。
4. 合并左右子数组,得到排好序的数组。
下面是 C++ 实现代码:
```
#include <iostream>
using namespace std;
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);
}
}
int main() {
int arr[] = {5, 2, 6, 8, 3, 1, 7, 9, 4};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
在上面的实现中,我们选择中间的元素作为基准元素,用 i 和 j 分别指向数组的左右两端,然后进行分区操作。在分区操作中,我们首先移动 i 指针,找到第一个大于等于基准元素的元素,然后移动 j 指针,找到第一个小于等于基准元素的元素,然后交换这两个元素。重复这个过程,直到 i > j。最后,递归地对左右子数组进行快速排序,直到排序完成。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)