堆排序算法——C
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了堆排序算法——C,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2383字,纯文字阅读大概需要4分钟。
内容图文
![堆排序算法——C](/upload/InfoBanner/zyjiaocheng/592/cf80b10dbbd94a1bafcabe7181f7d96a.jpg)
原始数据:array[]={49,38,65,97,76,13,27,49,10}
1.原始堆排序
2.创建大顶堆
3.开始排序(从小到大),交换根节点和最后一个结点。![堆排序算法——C - 文章图片](/upload/getfiles/0001/2021/4/29/20210429045340702.jpg)
4.重新创建大顶堆,进行下一结点的排序。循环即可。![堆排序算法——C - 文章图片](/upload/getfiles/0001/2021/4/29/20210429045341343.jpg)
5.五个函数
交换函数:void swap(int array[],int x,int y)
初始化大顶堆函数:void BuildHeap(int array[],int size)
生成大顶堆函数:void Down(int array[],int i,int n)
排序函数:void heapSort(int array[],int size)
主函数:int main()
#include <stdio.h>
void display(int array[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
void swap(int array[], int x, int y) {
int key = array[x];
array[x] = array[y];
array[y] = key;
}
// 从大到小排序
// void Down(int array[], int i, int n) {
// int child = 2 * i + 1;
// int key = array[i];
// while (child < n) {
// if (child + 1 < n && array[child] > array[child + 1]) {
// child++;
// }
// if (key > array[child]) {
// swap(array, i, child);
// i = child;
// } else {
// break;
// }
// child = child * 2 + 1;
// }
// }
// 从小到大排序
void Down(int array[], int i, int n) { // 最后结果就是大顶堆
int parent = i; // 父节点下标
int child = 2 * i + 1; // 子节点下标
while (child < n) {
if (child + 1 < n && array[child] < array[child + 1]) { // 判断子节点那个大,大的与父节点比较
child++;
}
if (array[parent] < array[child]) { // 判断父节点是否小于子节点
swap(array, parent, child); // 交换父节点和子节点
parent = child; // 子节点下标 赋给 父节点下标
}
child = child * 2 + 1; // 换行,比较下面的父节点和子节点
}
}
void BuildHeap(int array[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆,必须从下往上比较
Down(array, i, size); // 否则有的不符合大顶堆定义
}
}
void HeapSort(int array[], int size) {
printf("初始化数组:");
BuildHeap(array, size); // 初始化堆
display(array, size); // 查看初始化结果
for (int i = size - 1; i > 0; i--) {
swap(array, 0, i); // 交换顶点和第 i 个数据
// 因为只有array[0]改变,其它都符合大顶堆的定义,所以可以从上往下重新建立
Down(array, 0, i); // 重新建立大顶堆
printf("排序的数组:");
display(array, size);
}
}
int main() {
int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};
int size = sizeof(array) / sizeof(int);
// 打印数据
printf("%d \n", size);
printf("排序前数组:");
display(array, size);
HeapSort(array, size);
return 0;
}
内容总结
以上是互联网集市为您收集整理的堆排序算法——C全部内容,希望文章能够帮你解决堆排序算法——C所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。