堆排序算法（HeapSort）

本文主要是介绍堆排序算法（HeapSort），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.堆（heap）

（1）堆的概念
若n个关键字序列 $L [1... n]$ 满足下面某一条性质，则称为堆（heap）：
1）大根堆： $L (i) >= L (2 i)$ 且 $L (i) >= L (2 i + 1)$ $(1 <= i <= n /2)$
2）小根堆： $L (i) <= L (2 i)$ 且 $L (i) <= L (2 i + 1)$ $(1 <= i <= n /2)$
说明：可理解为顺序存储的完全二叉树，其每个结点的值大于其左右孩子结点的值

（2）堆的插入
先将新元素放到表尾，与父结点对比，若新元素比父结点更大（小）则将二者互换，若元素互换破坏了上一层级的堆性质，则采用相同的方法继续上调，直到无法上调为止

（3）堆的删除
用表尾的元素代替被删除的元素，若破坏了堆的性质，则与孩子结点中更大（小）的结点互换，若元素互换破坏了下一层级的堆性质，则采用相同的方法继续下调，直到无法下调为止

2.堆排序算法（HeapSort）

（1）堆排序算法思想
每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换），并将待排序元素再次调整为大（小）根堆

（2）适用范围
顺序表

2.建立大（小）根堆

把所有非终端结点都检查一遍，是否满足大（小）根堆的要求，如果不满足，则将当前结点与更大（小）的孩子互换，若元素互换破坏了下一层级的堆性质，则采用相同的方法继续向下调整

3.堆排序算法性能分析

性能	性能指标
时间复杂度	$O(n\log_{2}n)$
空间复杂度	$O (1)$
稳定性	不稳定

4.堆排序算法代码实现（Java）

public void heapSort(int[] arr, int len){buildMaxHeap(arr, len);for(int i = len ; i > 1 ; i--){int temp = arr[1];arr[1] = arr[i];arr[i] = temp;adjustHead(arr, 1, i-1);}
}public void buildMaxHeap(int[] arr, int len){for(int i = (len - 1) / 2 ; i >= 0 ; i--){adjustHead(arr, i , len);}
}public void adjustHead(int[] arr, int k, int len){arr[0] = arr[k];for(int j = 2 * k ; j <= len ; j *= 2){if(j < len && arr[j] < arr[j+1]){j++;}if(arr[0] > arr[j]){break;}else{arr[k] = arr[j];k = j;}}arr[k] = arr[0];
}