八大排序-堆排序（手写堆排序）
闲聊
最近看完一个电视剧，猪脚是胃无限和难忘鸡。比较奇怪的是整个电视剧没有讲爱得死去活来的男女之情反而讲的是男男之间纯纯的基情，不过别说还挺好看。有种感觉就像：天下人负你又如何，我定然站你这边...让我想到了当今社会的一些人，这类人习惯权衡利弊后“站队”，或察言观色后随波逐流不顾真理事实。这部剧表达的三观就像一股清流，人生难得一知己，让我内心颇有触动。很喜欢胃无限说的一句话：管他熙熙攘攘阳关道，我非要一条独木桥走到黑。人生难得一知己，能在大家都诋毁不信任甚至敌视你的时候还义无反顾的支持你，那也真是三生有幸了吧。但愿看到本篇的朋友们都能找到人生中的知己，即使没有这个人，也能坚持一些比较正确的原则。比较感同身受的是，那些见不得人的歪门邪道终究是上不了台面的...
原理
以最大堆为例，利用最大堆结构的特点：每个最大堆的根节点必然是数组中最大的元素，构建一次最大堆即可获取数组中最大的元素。剔除最大元素后，反复构建余下数字为最大堆获取根元素最终保证数组有序。
<font color="#FF0000">以上都是废话，建议直接看图</font>
最大堆定义
- 最大堆图示
image
- 最大堆数组
image
满足父节点大于或等于左右子节点即为最大堆，最大堆二叉树以及对应数组如上图。
堆排序流程
1.一趟堆排序
以数组int n[] = { 6, 5, 2, 7, 3, 9, 8 }为例：
image
步骤
一、构建最大堆：
从最后一个非叶子节点（计算公式为n.length/2-1,可自行验证)开始，从后往前进行调整构建，调整的规则是：若子节点大于父节点，则将子节点中较大的节点元素与父节点交换。
1.调整节点2（数组索引2），对比子节点9和8，将9和2进行交换；
image
2.调整节点5（数组索引1），对比子节点7和3，将7和5进行交换；
image
3.调整节点6（素组索引0），对比子节点7和9，将6和9进行交换；
image
二、取出最大堆数组的第一位根元素与数组末位元素交换：
image
2.循环构建最大堆
根据上述构建最大堆的原理可以得出堆排序的完整过程
- 第1趟堆排序：
image
- 第2趟堆排序：
image
- 第3趟堆排序：
image
- 第4趟堆排序：
image
- 第5趟堆排序：
image
- 第6趟堆排序：
image
编码实践
public class Test {
public static void main(String[] args) {
int n[] = { 6, 5, 2, 7, 3, 9, 8 };
heapsort(n);
System.out.print("堆排序结果：");
for (int m : n) {
System.out.print(m + " ");
}
}
/**
* 堆排序
* @param n 待排序数组
*/
public static void heapsort(int n[]) {
for (int i = n.length - 1; i >= 1; i--) {
buildHeap(n, i);
swap(n, 0, i);
}
}
/**
*
* @param n 待排序数组
* @param end 待排序数组末位下标
*/
public static void buildHeap(int n[], int end) {
int len = end + 1;
for (int i = len / 2 - 1; i >= 0; i--) {
//堆中i节点对应的左右子节点l和r
int l = 2 * i + 1, r = l + 1;
//指向较大数节点的指针
int p = l;
if (r <= len - 1 && n[l] < n[r]) {
p = r;
}
if (n[i] < n[p]) {
swap(n, i, p);
}
}
}
/**
*
* @param n 待排序数组
* @param i 待交换数字数组下标
* @param j 待交换数字数组下标
*/
private static void swap(int n[], int i, int j) {
n[i] ^= n[j];
n[j] ^= n[i];
n[i] ^= n[j];
}
- 结果
堆排序结果：2 3 5 6 7 8 9
编码说明
一、heapsort堆排序方法
for循环（注意循环次数比数组长度小1，原因最低2个数构成最大堆）
i.根据数组长度构建最大堆；
ii.交换数组首位（最大堆根节点）与数组末位；
二、buildHeap构建最大堆
1.声明数组长度len；
2.for循环从最后一个非叶子结点开始往回遍历到根节点;
i.找到当前非叶子结点的左右子节点下标；
ii.声明较大数指针，默认指向左子节点；
iii.对比左右子节点，若右子节点存在且右大于左则指向右子节点；
iv.对比交换较大的子节点和父节点。
结语
本篇以最简单的图文形式讲解八大排序之一的堆排序的核心思想和具体实现，堆排序和快速排序均为相对其他排序出现频率最高的排序算法。最后,如果觉得本篇对你有所启发或帮助，不妨关注走一波~
关注订阅号 获取更多干货～
