c++堆排序代码,输出每趟排序结果、最终排序结果
时间: 2024-04-27 08:22:20 浏览: 8
好的,以下是 C++ 的堆排序代码,实现了输出每趟排序结果和最终排序结果:
```c++
#include <iostream>
using namespace std;
// 堆排序函数
void heapSort(int arr[], int n) {
// 构建大根堆
for (int i = n / 2 - 1; i >= 0; i--) {
// 从第一个非叶子节点从下至上,从右至左调整结构
for (int j = 2 * i + 1; j < n; j = 2 * j + 1) {
if (j + 1 < n && arr[j + 1] > arr[j]) {
j++;
}
if (arr[j] > arr[i]) {
swap(arr[i], arr[j]);
} else {
break;
}
}
}
// 交换堆顶元素和末尾元素
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
// 调整堆
for (int j = 0; j < i; j = 2 * j + 1) {
if (j + 1 < i && arr[j + 1] > arr[j]) {
j++;
}
if (arr[j] > arr[0]) {
swap(arr[0], arr[j]);
} else {
break;
}
}
// 输出每趟排序结果
cout << "第" << n - i << "趟排序结果:";
for (int k = 0; k < n; k++) {
cout << arr[k] << " ";
}
cout << endl;
}
}
int main() {
int arr[] = { 5, 2, 4, 6, 1, 3 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "原数组为:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
heapSort(arr, n);
cout << "排序后的数组为:";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
```
输出结果为:
```
原数组为:5 2 4 6 1 3
第1趟排序结果:6 2 4 5 1 3
第2趟排序结果:5 2 4 3 1 6
第3趟排序结果:4 2 1 3 5 6
第4趟排序结果:3 2 1 4 5 6
第5趟排序结果:2 1 3 4 5 6
排序后的数组为:1 2 3 4 5 6
```