堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
1. 算法步骤
1、创建一个堆 H[0……n-1]；
2、把堆首（最大值）和堆尾互换；
3、把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
4、重复步骤 2，直到堆的尺寸为 1。
2. 动图演示
3. 时间复杂度
堆排序的平均时间复杂度为 Ο(nlogn)。
4. 算法实现
堆排序C语言
#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b)
{
int temp = *b;
*b = *a;
*a = temp;
}
void max_heapify(int arr[], int start, int end)
{
//建立父节点指标和子节点指标
int dad = start;
int son = dad * 2 + 1;
while (son <= end) //若子节点指标在范围内才做比较
{
if (son + 1 <= end && arr[son] < arr[son + 1])
//先比较两个子节点大小，选择最大的
son++;
if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
return;
else //否则交换父子内容再继续子节点和孙节点比较
{
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len)
{
int i;
//初始化，i从最後一个父节点开始调整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
for (i = len - 1; i > 0; i--)
{
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
堆排序C++
#include <iostream>
#include <algorithm>
using namespace std;
void max_heapify(int arr[], int start, int end)
{
//建立父节点指标和子节点指标
int dad = start;
int son = dad * 2 + 1;
while (son <= end) //若子节点指标在范围内才做比较
{
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
son++;
if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
return;
else //否则交换父子内容再继续子节点和孙节点比较
{
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len)
{
//初始化，i从最後一个父节点开始调整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
for (int i = len - 1; i > 0; i--)
{
swap(arr[0], arr[i]);
max_heapify(arr, 0, i - 1);
}
}
void main()
{
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
for (int i = 0; i < len; i++)
cout << arr[i] << ' ';
cout << endl;
system("pause");
}
堆排序PHP
function hsort(array &$arr, $len){
$idx = $len - 1;
//创建堆操作，并使得堆有序
for($k=floor($len/2); $k>=0; $k--){
sink($arr, $k, $idx);
}
//排序操作
while($idx>0){
//获取最大值操作
list($arr[0], $arr[$idx]) = [$arr[$idx], $arr[0]];
$idx--;
//堆调整下沉
sink($arr, 0, $idx);
}
}
//堆调整下沉，小数字下沉
function sink(array &$arr, $low, $high){
//从$low开始找子节点
while($low*2+1<=$high){
//获取low的直接左子节点
$j = $low*2+1;
//判断$low位置节点子节点中的较大子节点
if($j<$high && $arr[$j]<$arr[$j+1]){
$j++;
}
if($arr[$low]>$arr[$j]){
break;
}
//交换low节点和子节点的值
list($arr[$low], $arr[$j]) = [$arr[$j], $arr[$low]];
//继续排查下沉后子节点是否需要进行下沉操作
$low = $j;
}
}
$a = [4,3,6,7,5,1,9,0,2];
hsort($a, count($a));
print_r($a);
堆排序JAVA
/**
* 选择排序-堆排序
* @param array 待排序数组
* @return 已排序数组
*/
public static int[] heapSort(int[] array) {
//这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length); //调整堆
}
// 上述逻辑，建堆结束
// 下面，开始排序逻辑
for (int j = array.length - 1; j > 0; j--) {
// 元素交换,作用是去掉大顶堆
// 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(array, 0, j);
// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
// 而这里，实质上是自上而下，自左向右进行调整的
adjustHeap(array, 0, j);
}
return array;
}
/**
* 整个堆排序最关键的地方
* @param array 待组堆
* @param i 起始结点
* @param length 堆的长度
*/
public static void adjustHeap(int[] array, int i, int length) {
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
// 让k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子树,并且右子树大于左子树
k++;
}
//如果发现结点(左右子结点)大于根结点，则进行值的交换
if (array[k] > temp) {
swap(array, i, k);
// 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
i = k;
} else { //不用交换，直接终止循环
break;
}
}
}
/**
* 交换元素
* @param arr
* @param a 元素的下标
* @param b 元素的下标
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
堆排序JavaScript
var len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr) { // 建立大顶堆
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { // 堆调整
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
堆排序C#语言
/// <summary>
/// 堆排序
/// </summary>
/// <param name="arr">待排序数组</param>
static void HeapSort(int[] arr)
{
int vCount = arr.Length;
int[] tempKey = new int[vCount + 1];
// 元素索引从1开始
for (int i = 0; i < vCount; i++)
{
tempKey[i + 1] = arr[i];
}
// 初始数据建堆（从含最后一个结点的子树开始构建，依次向前，形成整个二叉堆）
for (int i = vCount / 2; i >= 1; i--)
{
Restore(tempKey, i, vCount);
}
// 不断输出堆顶元素、重构堆，进行排序
for (int i = vCount; i > 1; i--)
{
int temp = tempKey[i];
tempKey[i] = tempKey[1];
tempKey[1] = temp;
Restore(tempKey, 1, i - 1);
}
//排序结果
for (int i = 0; i < vCount; i++)
{
arr[i] = tempKey[i + 1];
}
}
/// <summary>
/// 二叉堆的重构（针对于已构建好的二叉堆首尾互换之后的重构）
/// </summary>
/// <param name="arr"></param>
/// <param name="rootNode">根结点j</param>
/// <param name="nodeCount">结点数</param>
static void Restore(int[] arr, int rootNode, int nodeCount)
{
while (rootNode <= nodeCount / 2) // 保证根结点有子树
{
//找出左右儿子的最大值
int m = (2 * rootNode + 1 <= nodeCount && arr[2 * rootNode + 1] > arr[2 * rootNode]) ? 2 * rootNode + 1 : 2 * rootNode;
if (arr[m] > arr[rootNode])
{
int temp = arr[m];
arr[m] = arr[rootNode];
arr[rootNode] = temp;
rootNode = m;
}
else
{
break;
}
}
}
堆排序Python
def big_endian(arr,start,end): root=start child=root*2+1 #左孩子 while child<=end: #孩子比最后一个节点还大，也就意味着最后一个叶子节点了，就得跳出去一次循环，已经调整完毕 if child+1<=end and arr[child]<arr[child+1]: #为了始终让其跟子元素的较大值比较，如果右边大就左换右，左边大的话就默认 child+=1 if arr[root]<arr[child]: #父节点小于子节点直接交换位置，同时坐标也得换，这样下次循环可以准确判断：是否为最底层， #是不是调整完毕 arr[root],arr[child]=arr[child],arr[root] root=child child=root*2+1 else: break def heap_sort(arr): #无序区大根堆排序 first=len(arr)//2 - 1 for start in range(first,-1,-1): #从下到上，从左到右对每个节点进行调整，循环得到非叶子节点 big_endian(arr,start,len(arr)-1) #去调整所有的节点 for end in range(len(arr)-1,0,-1): arr[0],arr[end]=arr[end],arr[0] #顶部尾部互换位置 big_endian(arr,0,end-1) #重新调整子节点的顺序，从顶开始调整 return arr def main(): l=[3,1,4,9,6,7,5,8,2,10] print(heap_sort(l)) if __name__=="__main__": main()
堆排序Go语言
func heapSort(arr []int) []int {
arrLen := len(arr)
buildMaxHeap(arr, arrLen)
for i := arrLen - 1; i >= 0; i-- {
swap(arr, 0, i)
arrLen -= 1
heapify(arr, 0, arrLen)
}
return arr
}
func buildMaxHeap(arr []int, arrLen int) {
for i := arrLen / 2; i >= 0; i-- {
heapify(arr, i, arrLen)
}
}
func heapify(arr []int, i, arrLen int) {
left := 2*i + 1
right := 2*i + 2
largest := i
if left < arrLen && arr[left] > arr[largest] {
largest = left
}
if right < arrLen && arr[right] > arr[largest] {
largest = right
}
if largest != i {
swap(arr, i, largest)
heapify(arr, largest, arrLen)
}
}
func swap(arr []int, i, j int) {
arr[i], arr[j] = arr[j], arr[i]
}