【007】Swift经典排序算法-堆排序

小序：什么是堆？

      先了解一下什么是堆，堆是计算机科学中的一种特别的树状数据结构,堆总是一棵完全二叉树,它总是满足下列性质:

性质1：堆中某个节点的值总是不大于或不小于其父节点的值;

性质2：堆总是一棵完全二叉树。

      堆的特征就是:给定堆中任意节点P和C,若P是C的母节点,那么P的值会小于等于(或大于等于) C 的值”。将根节点最大的堆叫做最大堆、大顶堆或大根堆，根节点最小的堆叫做最小堆、小顶堆或小根堆，如下图：。常见的堆有二叉堆、斐波那契堆等。

同时，我们对以上堆的这种逻辑结构映射到数组中就是下面这个样子：

我们用简单的公式定义一下大顶堆和小顶堆：

大顶堆：a[I] >= a[2i+1] && a[I] >= a[2i+2]

小顶堆：a[I] <= a[2i+1] && a[I] <= a[2i+2]

---

堆排序的思路？

首先我们先将数组序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。

---

堆排序

基于上面对堆的了解，相信你对堆排序会有了更好的认识。堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

堆排序的平均时间复杂度为 Ο(nlogn)。

1. 算法步骤

创建一个堆 H[0……n-1]；

把堆首（最大值）和堆尾互换；

把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

重复步骤 2，直到堆的尺寸为 1。

2. 动图演示

GIF1 GIF2【接着GIF1】 GIF3【接着GIF2】

3. 代码实现

/// 堆排序法

    /// [微信公众号：疯狂1024]

    /// - Parameter array:传入参数的数组

    /// - Returns: 返回排序后的数组

    publicfuncheapSort(_array: [Int]) -> [Int] {

        guard!array.isEmptyelse{return[] }        // 非空判断，避免崩溃

        varpreArray:Array = array                // 对 arr 进行拷贝，不改变参数内容

        buildMaxHeap(&preArray)                        // 建立大顶堆（堆化处理）

        foriin(0..<preArray.count).reversed() {

            preArray.swapAt(i,0)                      // 找到最大堆顶后将堆顶的数值和第i个进行互换

            heapify(&preArray, nodeIndex:0, len: i)  // 堆化处理(互换堆顶数值后结构发生变化，需要再次堆顶化处理)

        }

        returnpreArray

    }

    ///建立大顶堆

    /// - Parameter array: 传入参数的数组，注意是传址不是传值

    privatefuncbuildMaxHeap(_array:inout[Int]) {

        letminNodeIndex =Int(floor(Double(array.count/2))-1)  // 寻找“最小的”节点位置,即中间平分后带子叶的节点

        forindexin(0...minNodeIndex).reversed() {            // 循环所有节点

            heapify(&array, nodeIndex: index, len: array.count)

        }

    }

    /// （大顶）堆化调整

    /// - Parameters:

    ///  - array: 传入参数的数组，注意是传址不是传值

    ///  - nodeIndext: 节点位置

    ///  - len: 想要要堆化的数组长度

    privatefuncheapify(_array:inout[Int], nodeIndex:Int, len:Int) {

        letleft =2*nodeIndex+1

        letright =2*nodeIndex+2

        varlargest = nodeIndex

        // 寻找最大数值位置

        ifleft<len&&array[left]>array[largest] {

            largest = left

        }

        ifright<len&&array[right]>array[largest] {

            largest = right

        }

        iflargest!=nodeIndex {

            array.swapAt(nodeIndex, largest)      // 互换数值，把最大数值放到节点位置

            heapify(&array, nodeIndex: largest, len: len)    // 互换后数据结构发生变化，继续进行堆化处理

        }

    }