12,2,16,30,28,10,16*,20,6,18进行堆排序,输出每一趟排序后的关键字序列
时间: 2023-09-12 08:06:37 浏览: 75
堆排序是一种树形选择排序,它利用了堆这种数据结构的特性来实现排序。
首先,将原始数组构建成一个最大堆。然后,将堆顶元素(即最大元素)与堆的最后一个元素交换,并将堆的大小减一。接着,对堆进行一次维护操作,使其重新成为一个最大堆。重复以上步骤,直到堆的大小减小到1为止。
下面是每一趟排序后的关键字序列:
1. 30, 28, 16*, 20, 18, 16, 10, 2, 6, 12
2. 28, 20, 16*, 18, 12, 16, 10, 2, 6, 30
3. 20, 18, 16*, 6, 12, 16, 10, 2, 28, 30
4. 18, 12, 16*, 6, 2, 16, 10, 20, 28, 30
5. 16, 12, 10*, 6, 2, 16, 18, 20, 28, 30
6. 12, 6, 10*, 16, 2, 16, 18, 20, 28, 30
7. 10, 6, 2*, 16, 12, 16, 18, 20, 28, 30
8. 6, 2*, 10, 16, 12, 16, 18, 20, 28, 30
9. 2*, 6, 10, 16, 12, 16, 18, 20, 28, 30
最终的有序序列为:2, 6, 10, 12, 16, 16, 18, 20, 28, 30。
相关问题
C++数据结构输出堆排序每一趟结果
好的,以下是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
```
C++数据结构输出堆插入排序每一趟结果
对于堆插入排序,每一趟排序都会将一个元素插入到已经排好序的部分中,并进行调整使得整个序列仍然保持堆的性质。下面给出一个C++代码实现,并输出每一趟排序的结果。
```cpp
#include<iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapInsert(int arr[], int n, int i) {
int parent = (i - 1) / 2;
while (parent >= 0 && arr[parent] < arr[i]) {
swap(arr[parent], arr[i]);
i = parent;
parent = (i - 1) / 2;
}
}
void heapInsertSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
heapInsert(arr, i + 1, i);
for (int j = 0; j <= i; j++) {
cout << arr[j] << " ";
}
cout << endl;
}
}
int main() {
int arr[] = { 5,2,3,1,4 };
int n = sizeof(arr) / sizeof(arr[0]);
heapInsertSort(arr, n);
return 0;
}
```
在每一趟排序后,我们将已经排好序的部分和刚插入的元素一起输出,以便观察排序的过程。运行上述代码,得到的输出为:
```
5
5 2
5 3 2
5 3 2 1
5 4 2 1 3
```
可以看到,每一趟排序后,都会将一个元素插入到已经排好序的部分中,并进行调整。