堆排序（堆的建立，维护，和排序）

1、前言

本文使用了Swift语言来实现了堆排序中的三个重要函数：1、维护堆属性；2、建立堆；3、堆排序。

2、代码

1、维护堆属性：

    /// 检查某一位是否是符合大顶堆要求 时间复杂度 O(lgn)
    ///
    /// - Parameters:
    ///   - A: 数组
    ///   - i: 下标
    func max_heapify(A: inout Array<Int>, i: Int) {
        if A.count == 0 {
            return
        }
        let (li, lv) = left(A: A, i: i)
        let (ri, rv) = right(A: A, i: i)
        if lv > A[i] && lv > rv {// lv最大
            exchange(a: &A[li], b: &A[i])
            max_heapify(A: &A, i: li) // 递归调用自己
        } else if rv > lv && rv > A[i] {
            exchange(a: &A[ri], b: &A[i])
            max_heapify(A: &A, i: ri) // 递归调用自己
        } else {
            return
        }
    }

一些辅助函数：

    // 交换两者
    func exchange(a: inout Int, b: inout Int) {
        let c = b
        b = a
        a = c
    }
    
    // 返回数组A中，下标i的左孩子
    func left(A: Array<Int>, i: Int) -> (index: Int, value: Int){
        let index = 2*i+1
        if index > A.count-1 {
            return (index, Int.min)
        }
        return (index, A[index])
    }
    
    // 返回数组A中，下标i的右孩子
    func right(A: Array<Int>, i: Int) -> (index: Int, value: Int) {
        let index = 2*i+2
        if index > A.count-1 {
            return (index, Int.min)
        }
        return (index, A[index])
    }

2、使用max_heapify函数来建立堆:

    /// 将给出的数组转化为大顶堆 时间复杂度 O(n*lgn)
    ///
    /// - Parameter A: 数组
    func build_max_heapify(A: inout Array<Int>) {
        for i in (0..<A.count).reversed() { // 从底向上的开始新建大顶堆
            max_heapify(A: &A, i: i)
        }
    }

3、每一次摘取大顶堆的堆顶来实现堆排序

    /// 堆排序 时间复杂度O(2*n*lgn) 空间复杂度 O(n)
    ///
    /// - Parameter A: 需要排序的数组
    func heapify_sort(A: inout Array<Int>) {
        build_max_heapify(A: &A) // 将A建立为大顶堆 O(n*lgn)
        var sortedArr = [Int]() // 空间复杂度n
        let count = A.count
        // n次操作
        for i in (0..<count).reversed() { // 每次取出大顶堆的顶,i = A.count-1,最后一个
            exchange(a: &A[i], b: &A[0]) // 交换最后一个和第一个，也就是交换了最大的和较小的，最大的数到了A【i】中  O(1)
            sortedArr.append(A[i]) // 将最大的数保存到排序好的数组中 O(1)
            A.removeLast() // 删除最后一个，这里并不会出现i out range的情况 O(1)
            max_heapify(A: &A, i: 0) // 重新将数组排序为大顶堆 O(lgn)
        }
        A = sortedArr
    }

3、结语

这里的堆排序使用的是连续数组和下标的关系来建立的堆数据结构，如果是使用链表数组来建立堆结构应该代码会有一些区别（代码量应该会大一些）。性能分析：堆排序的时间复杂度是O（n*lgn），空间复杂度是O（n）。希望本文对正在学习基础数据结构算法的同学有所帮助。