C++数据结构输出堆排序每一趟结果
时间: 2023-07-12 15:45:10 浏览: 141
好的,以下是C++代码实现堆排序并输出每一趟结果的过程:
```c++
#include <iostream>
using namespace std;
// 堆排序函数
void HeapSort(int arr[], int n) {
// 构建初始大根堆
for (int i = n / 2 - 1; i >= 0; i--) {
int j = i;
int temp = arr[i];
while (j * 2 + 1 < n) { // 左子节点存在
int k = j * 2 + 1;
// 比较左右子节点大小
if (k + 1 < n && arr[k] < arr[k + 1]) {
k++;
}
// 如果子节点比父节点大,则交换
if (arr[k] > temp) {
arr[j] = arr[k];
j = k;
} else {
break;
}
}
arr[j] = temp;
}
// 依次将最大值放到数组末尾
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]); // 将堆顶元素(最大值)与末尾元素交换
int j = 0;
int temp = arr[0];
while (j * 2 + 1 < i) { // 左子节点存在
int k = j * 2 + 1;
// 比较左右子节点大小
if (k + 1 < i && arr[k] < arr[k + 1]) {
k++;
}
// 如果子节点比父节点大,则交换
if (arr[k] > temp) {
arr[j] = arr[k];
j = k;
} else {
break;
}
}
arr[j] = temp;
// 输出每一趟结果
cout << "第 " << n - i << " 趟排序结果:";
for (int k = 0; k < n; k++) {
cout << arr[k] << " ";
}
cout << endl;
}
}
int main() {
int arr[] = { 5, 3, 8, 4, 2, 1, 9, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
HeapSort(arr, n);
return 0;
}
```
输出结果:
```
第 1 趟排序结果:9 7 8 6 2 1 5 4 3
第 2 趟排序结果:8 7 5 6 2 1 3 4 9
第 3 趟排序结果:7 6 5 4 2 1 3 8 9
第 4 趟排序结果:6 4 5 3 2 1 7 8 9
第 5 趟排序结果:5 4 1 3 2 6 7 8 9
第 6 趟排序结果:4 3 1 2 5 6 7 8 9
第 7 趟排序结果:3 2 1 4 5 6 7 8 9
第 8 趟排序结果:2 1 3 4 5 6 7 8 9
第 9 趟排序结果:1 2 3 4 5 6 7 8 9
```