首页 > 代码库 > 堆排序（heapsort）
堆排序（heapsort）
堆数据结构是一种数组对象，它可以被视为一棵完全二叉树。时间复杂度为：O(n*logn)，空间复杂度：O(1);
平均时间复杂度和最坏时间复杂度都为：O(n*logn)，但堆排序是不稳定排序。
堆排序思路：
1.建立小堆：把堆看成一个完全二叉树，然后从这棵树的最大非叶子节点开始，比较它与它的左儿子与
右儿子的大小，若大于它的儿子，则与最小的交换，交换位置后然后继续与它现在位置的儿子比较；若小于它的儿子
，则不用交换，直接跳到下一个非叶子节点，重复以上步骤。
2.输出排序的结果：将堆顶元素输出，然后再将堆的最后一个节点赋值给堆顶元素，删除最后一个堆元
素。然后将堆顶元素与它的儿子比较，若大于它的儿子，则与最小的交换，交换位置后继续与它现在位置的儿子比较；
若小于它的儿子则不用交换，继续输出堆顶元素，重复以上步骤。
建立小堆排序的示例代码：
#include <stdio.h>void BuildHeap(int array[], int n) //建立一个小堆{ int mark; //mark作为标记变量 int i, j, k; for(i = n/2; i>=1; i--) //从最大的非叶子节点开始 { j = 2*i; while(j<=n) //开始比较它与儿子节点的大小，若大则交换位置并继续比较 { if(j+1<=n) { if(array[j]>= array[j/2] && array[j+1]>=array[j/2]) break; k = array[j] > array[j+1] ? j+1 : j; mark = array[j/2]; array[j/2] = array[k]; array[k] = mark; j = 2*k; } else { if(array[j]>=array[j/2]) break; else { mark = array[j/2]; array[j/2] = array[j]; array[j] = mark; j = 2*j+1; //这里有个小技巧，因为它已经是最后一个非叶子节点，加1是为了防止它再进入循环 } } } }}void HeapSort(int array[], int n){ int i, j, k, m = n; int mark; BuildHeap(array, n); for(j = 1; j<=m; j++) //输出堆排序的结果 { i = 1; printf("%d ", array[i]); array[i] = array[n--]; while(2*i<=n) //重新将堆排序好，和上面有点类似 { if(2*1+1<=n) { if(array[2*i+1]>=array[i] && array[2*i]>=array[i]) break; else { k = array[2*i] > array[2*i+1] ? 2*i+1 : 2*i; mark = array[i]; array[i] = array[k]; array[k] = mark; i = k; } } else { if(array[2*i]>=array[i]) break; else { mark = array[i]; array[i] = array[2*i]; array[2*i] = mark; i = 2*i; } } } }}int main(){ int n; int array[100]; printf("请输入要排序的数组大小："); scanf("%d", &n); printf("请输入数组中的各个数："); for(int i = 1; i<=n; i++) scanf("%d", &array[i]); HeapSort(array, n); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。