本文主要是介绍堆排序（Heap_sort），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
涉及到大根堆的知识点；
最小父节点为length/2-1
父节点的子节点为son = dad*2+1 或 dad*2+2
大根堆即所有父节点大于所有子节点
主要函数：
void Heap_Sort(int *a,int length)
{int i;//从最小的父亲节开始改变，使每一个父亲节点大于儿子节点，从而构成大根堆for(int i = length/2-1;i >=0 ;--i){Heap(a,i,length);}//排序完成后最开始的节点一定是最大的，因为是大根堆swap(a[0],a[length-1]);for(int i = length-1;i > 1;--i){Heap(a,0,i);//因为大根堆父亲节点大于所有子节点，所以排序一次即可swap(a[0],a[i-1]);}
}先将无序数组转换为大根堆
然后将首节点与最后节点交换，因为大根堆的头节点最大，这时候最末尾元素就是最大的了
然后在用heap一次即可找打剩余最大的数字持续交换直到剩下最后一个元素即可
次要函数：
//使每个父亲节点大于儿子节点
void Heap(int *a,int dad,int length)
{int son = dad*2+1;while(son < length){if(son+1<length && a[son] < a[son+1])//保证儿子节点是两个儿子中最大的{++son;}if(a[dad] < a[son]){swap(a[dad],a[son]);}dad = son;son = dad*2+1;}
}该函数只能使一个头节点的元素最大，需要从最小的父节点进行循环，因为如果从下往上的话最大的数传播不上去；在主函数后续只需要排序一次是因为：只有头节点不满足大根堆，相当于第一次的最后一步，也就是排序最后一个头节点，因此只需要排序一次即可构成大根堆；
c++代码如下：
#include <bits/stdc++.h>using namespace std;void swap(int &a,int &b)
{int t = a;a = b;b = t;
}//使每个父亲节点大于儿子节点
void Heap(int *a,int dad,int length)
{int son = dad*2+1;while(son < length){if(son+1<length && a[son] < a[son+1])//保证儿子节点是两个儿子中最大的{++son;}if(a[dad] < a[son]){swap(a[dad],a[son]);}dad = son;son = dad*2+1;}
}void Heap_Sort(int *a,int length)
{int i;//从最小的父亲节开始改变，使每一个父亲节点大于儿子节点，从而构成大根堆for(int i = length/2-1;i >=0 ;--i){Heap(a,i,length);}//排序完成后最开始的节点一定是最大的，因为是大根堆swap(a[0],a[length-1]);for(int i = length-1;i > 1;--i){Heap(a,0,i);//因为大根堆父亲节点大于所有子节点，所以排序一次即可swap(a[0],a[i-1]);}
}void print_arr(int *arr,int size)
{for(int i = 0;i < size;++i){cout << arr[i];if(i != size-1){cout << " ";}}
}int main()
{int n;cin >> n;int arr[n];for(int i = 0;i < n;++i){cin >> arr[i];}Heap_Sort(arr,n);print_arr(arr,n);cout << endl;
}这篇关于堆排序（Heap_sort）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
