要求改写快速排序算法,使得能输出每一趟快排后的结果。c++编写
时间: 2024-10-11 08:04:29 浏览: 3
快速排序是一种经典的分治排序算法,通常它是一个“黑盒”操作,即只关心输入和输出,而不关注内部细节。如果需要在每趟排序后都输出结果,我们可以稍微修改原算法,使其在每个分割阶段都记录中间位置,并打印数组的一部分。
下面是一个简单的C++版本,实现了这个要求:
```cpp
#include <iostream>
using namespace std;
void quickSort(int arr[], int left, int right, int& pivotIndex) {
if (left < right) {
pivotIndex = partition(arr, left, right);
// 输出分割点及其两侧的部分
cout << "Pivot at index " << pivotIndex << ": ";
for (int i = left; i <= pivotIndex; ++i)
cout << arr[i] << " ";
cout << endl;
quickSort(arr, left, pivotIndex - 1, pivotIndex); // 左半部分
quickSort(arr, pivotIndex + 1, right, pivotIndex); // 右半部分
}
}
int 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++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return (i + 1);
}
int main() {
int arr[] = {9, 7, 5, 11, 12, 2, 14, 3};
int size = sizeof(arr) / sizeof(arr[0]);
int pivotIndex;
quickSort(arr, 0, size - 1, pivotIndex);
cout << "Sorted array: ";
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
```
在这个版本中,我们在`quickSort`函数中添加了一个`pivotIndex`变量,用于记录每轮分割的中间位置。然后在每次分割之后,我们都会输出这一信息。注意,这只是一个基本实现,实际应用中可能会有更复杂的日志系统来跟踪整个过程。