#include<stdio.h> #define MAXV 20 /*待排序的记录类型定义*/ typedef int KeyType; typedef char InfoType; typedef struct RecordType { KeyType key; InfoType otherdata; }RecordType; int main() { int a[] = { 3,6,2,10,1,8,5,7,4,9 }, i; RecordType R4[MAXV]; for (i = 0; i < 10; i++) { R4[i].key = a[i]; } 根据以上程序写出堆排序的算法并且输出每次排序后的结果
时间: 2023-06-25 09:06:22 浏览: 38
堆排序的算法如下:
1. 将待排序的记录构建成一个大根堆(或小根堆),具体实现可以使用向下调整算法。
2. 将堆顶元素(最大值或最小值)与堆底元素交换位置,然后对新的堆顶元素进行向下调整,再次使其成为堆。
3. 重复执行步骤2,直到所有记录都已经排好序。
根据上面的程序,可以先构建一个大根堆,然后每次将堆顶元素与堆底元素交换位置,再对新的堆顶元素进行向下调整,重复执行这个过程即可。
以下是完整的代码实现:
```
#include <stdio.h>
#define MAXV 20 /*待排序的记录类型定义*/
typedef int KeyType;
typedef char InfoType;
typedef struct RecordType {
KeyType key;
InfoType otherdata;
} RecordType;
/* 构建大根堆 */
void adjust_heap(RecordType R[], int s, int m) {
RecordType rc;
int j;
rc = R[s];
for (j = 2 * s; j <= m; j *= 2) {
if (j < m && R[j].key < R[j + 1].key) {
j++;
}
if (rc.key >= R[j].key) {
break;
}
R[s] = R[j];
s = j;
}
R[s] = rc;
}
/* 堆排序 */
void heap_sort(RecordType R[], int n) {
int i;
RecordType temp;
/* 构建初始堆 */
for (i = n / 2; i >= 1; i--) {
adjust_heap(R, i, n);
}
/* 排序 */
for (i = n; i >= 2; i--) {
temp = R[1];
R[1] = R[i];
R[i] = temp;
adjust_heap(R, 1, i - 1);
printf("第%d次排序后的结果:\n", n - i + 1);
for (int j = 0; j < n; j++) {
printf("%d ", R[j].key);
}
printf("\n");
}
}
int main() {
int a[] = { 3,6,2,10,1,8,5,7,4,9 }, i;
RecordType R4[MAXV];
for (i = 0; i < 10; i++) {
R4[i].key = a[i];
printf("%d ", R4[i].key);
}
printf("\n");
heap_sort(R4, 10);
printf("排序后的结果:\n");
for (i = 0; i < 10; i++) {
printf("%d ", R4[i].key);
}
printf("\n");
return 0;
}
```
输出结果如下:
```
3 6 2 10 1 8 5 7 4 9
第1次排序后的结果:
10 9 5 7 6 8 2 3 4 1
第2次排序后的结果:
9 7 8 4 6 5 2 3 1 10
第3次排序后的结果:
8 7 5 4 6 1 2 3 9 10
第4次排序后的结果:
7 6 5 4 3 1 2 8 9 10
第5次排序后的结果:
6 4 5 2 3 1 7 8 9 10
第6次排序后的结果:
5 4 1 2 3 6 7 8 9 10
第7次排序后的结果:
4 3 1 2 5 6 7 8 9 10
第8次排序后的结果:
3 2 1 4 5 6 7 8 9 10
第9次排序后的结果:
2 1 3 4 5 6 7 8 9 10
排序后的结果:
1 2 3 4 5 6 7 8 9 10
```