快速排序是一个典型的基于分治思想的算法,其基本思想是: (1)选择基准值pivot 将数组划分成两部分,一部分小于基准值,一部分大于基准值。 (2)对得到的两个子数组再次进行快速排序。 (3)当子数组满足递归出口条件时合并结果。 请使用通用算法 partition 或 stable_partition 编写实现快速排序的程序,测试结果并理解每一步的快排过程。(C++)
时间: 2024-02-23 18:00:16 浏览: 26
以下是使用通用算法 partition 实现快速排序的程序:
```c++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int partition(vector<int>& nums, int left, int right) {
int pivot = nums[left];
int i = left + 1, j = right;
while (i <= j) {
if (nums[i] <= pivot) {
i++;
} else if (nums[j] > pivot) {
j--;
} else {
swap(nums[i], nums[j]);
}
}
swap(nums[left], nums[j]);
return j;
}
void quickSort(vector<int>& nums, int left, int right) {
if (left >= right) return;
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
}
int main() {
vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
quickSort(nums, 0, nums.size() - 1);
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
```
在这个程序中,`partition` 函数使用了双指针的方法,将数组划分成两个部分,左边的部分都小于等于基准值,右边的部分都大于基准值。最终返回基准值的位置。
`quickSort` 函数则是基于分治思想,将数组分成两个部分分别进行快排,直到数组长度为 1 或 0,然后合并结果。
在主函数中,我们首先定义一个测试数组,然后调用 `quickSort` 函数进行排序,最后输出排序结果。
对于测试数组 `{3, 1, 4, 1, 5, 9, 2, 6, 5, 3}`,快排的过程如下:
1. 初始数组:`3, 1, 4, 1, 5, 9, 2, 6, 5, 3`
2. 第一次划分:选择 `pivot` 为 `3`,将数组划分为 `[1, 1, 2]`, `[3]`, `[4, 5, 9, 6, 5]`,交换 `pivot` 和 `2` 的位置,数组变为 `2, 1, 4, 1, 5, 9, 3, 6, 5, 3`。
3. 对左右两个子数组进行快排:
- 左边的子数组 `[2, 1, 4, 1, 5, 3, 5, 3]`,选择 `pivot` 为 `2`,划分为 `[1, 1]`, `[2]`, `[4, 5, 3, 5, 3]`,交换 `pivot` 和 `1` 的位置,数组变为 `1, 1, 2, 4, 5, 3, 5, 3`,然后对左右两个子数组继续进行快排。
- 右边的子数组 `[9, 6]`,选择 `pivot` 为 `9`,划分为 `[]`, `[9]`, `[6]`,不需要进行快排。
4. 最终数组:`1, 1, 2, 3, 3, 4, 5, 5, 6, 9`
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)
![](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)