今天去参加一个公司的面试，其中有道题是请说出快速排序和堆排序的区别。妈蛋，瞬间有种这7年程序员白当的感觉，我竟然不知道什么是堆排序。而快速排序也是前两天准备面试的时候临时看了看，毫不夸张的说，这两个算法，在我把每个算法研究了很长时间后，现在叫我来写，我也不保证能完全正确。咱得承认差距，认清现实。算法这东西只有多刷题，写多了自然就会了。
首先我们从字面意思上解释下什么是堆排序，为什么叫堆排序呢，因为整个排序过程中使用的数据结构 堆 而得来。
而我连什么是堆都不知道，没办法，只有去翻大学的教材，我的大学教材是严蔚敏编的《数据结构 C语言版》。开始我没有找到堆这种数据结构的定义，没办法只有百度百科。在我刚刚写这篇文章的时候，我不服气，又回去翻书，发现堆的定义在教材的排序算法-堆排序中。我都不知道自己上大学的时候在干嘛~所以告诫还在读大学的盆友，认认真真的学习，我就是鲜活的例子啊。
堆的定义如下：首先我们可以用一维数组表示堆，堆可以看做是一颗完全二叉树。（完全二叉树的意思是除去最后一层的节点后，其余全是满二叉树）这颗完全二叉树还具备这样的特点才能叫堆。
完全二叉树中所有非终端结点的值均不大于（或者不小于）其左右孩子结点的值。
堆排序的过程
假设我们要将数组升序排序
首先我们将拿到的数组理解成一颗完全二叉树，在这颗完全二叉树上原地进行建大堆（什么是大堆，大堆就是最大的值在根结点的堆，为什么这里要建大堆，我们稍后会解释）。
大堆怎么建的问题
我们可以用递归的思想，从下往上依次建。
/*
*@param array 待排序的数组
*@param start 结点序号（从0开始），待排序的父结点。
*@param end 完全二叉树的最后一个尾结点序号，用来判断临
*界情况
*/
+(void)createMaxHeapWithArray:(NSMutableArray<NSNumber*> *)array start:(int)start end:(int)end {
int dad = start;
int son = dad * 2 + 1;
while (son <= end) {
//比较两个儿子的大小
if (son + 1 <= end &&
[array[son] intValue] < [array[son+1] intValue]) {
son ++;
}
if ([array[dad] intValue] > [array[son] intValue]) {
return;
} else {
[array exchangeObjectAtIndex:dad withObjectAtIndex:son];
//因为交互打乱了原来的顺利，这里继续对打乱的顺序进行再一次排序，所以dad = son ,son = dad * 2 + 1,直到满足return的条件或者找到了尾结点
dad = son;
son = dad * 2 + 1;
}
}
}
排序过程
刚刚我们实现了一个函数给定一个数组，开始值和数组对应的完全二叉树的结尾值，我们可以建堆。
接下来我们看看算法的实现
+ (void)heapSortWithArray:(NSMutableArray<NSNumber*> *)array {
int len =(int) array.count;
//这里是关键，从最后一个非叶子结点开始,这里就是递归的思想。
for (int i = len / 2 - 1; i >= 0; i-- ){
[self createMaxHeapWithArray:array start:i end:len-1];
}
//交换堆的根结点和尾结点的值，然后对交换后的除去尾结点的最大值的完全二叉树建大堆，一直交换，直到只剩下跟结点。
for (int i = len - 1; i > 0 ; i -- ) {
[array exchangeObjectAtIndex:0 withObjectAtIndex:i];
[self createMaxHeapWithArray:array start:0 end:i-1];
}
[self printArray:array];
}
其实完全搞明白了也不是很难理解，在我们使用递归的时候，一定要弄清楚临界条件。
好了，堆排序就介绍到这里，方便自己以后来理解，归纳和总结也是一种能力。在面试的过程中，能清楚表达自己的意思很重要。
