每次选择子数组的第一个元素作为pivot 在根据pivot划分完的左子数组元素的顺序与原数组中的顺序一致。右子数组同理。 比如:数组为5,3,6,8,2,4,1,9,10,7,选择5为pivot,划分得到的左子数组3,2,4,1,右子数组6,8,9,10,7。输出在这个序列上进行快速排序算法需要的比较次数。给出c++程序
时间: 2023-06-16 17:08:03 浏览: 30
以下是使用快速排序算法进行排序,并输出比较次数的C++程序:
```c++
#include <iostream>
using namespace std;
// 交换两个元素
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
// 以arr[l]作为pivot,对arr[l...r]进行划分
// 返回划分后pivot的位置
int partition(int arr[], int l, int r, int& cmp_count) {
int pivot = arr[l];
int i = l, j = r;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
cmp_count++; // 比较次数+1
}
if (i < j) {
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < pivot) {
i++;
cmp_count++; // 比较次数+1
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
return i;
}
// 对arr[l...r]进行快速排序
void quicksort(int arr[], int l, int r, int& cmp_count) {
if (l < r) {
int pivot_pos = partition(arr, l, r, cmp_count);
quicksort(arr, l, pivot_pos - 1, cmp_count);
quicksort(arr, pivot_pos + 1, r, cmp_count);
}
}
int main() {
int arr[] = {5, 3, 6, 8, 2, 4, 1, 9, 10, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int cmp_count = 0;
quicksort(arr, 0, n - 1, cmp_count);
cout << "比较次数:" << cmp_count << endl;
cout << "排序后的数组:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
输出结果为:
```
比较次数:34
排序后的数组:1 2 3 4 5 6 7 8 9 10
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)