OC 堆排序

今天去参加一个公司的面试，其中有道题是请说出快速排序和堆排序的区别。妈蛋，瞬间有种这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];
}

其实完全搞明白了也不是很难理解，在我们使用递归的时候，一定要弄清楚临界条件。

好了，堆排序就介绍到这里，方便自己以后来理解，归纳和总结也是一种能力。在面试的过程中，能清楚表达自己的意思很重要。