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、結語

這里的堆排序使用的是連續(xù)數組和下標的關系來建立的堆數據結構，如果是使用鏈表數組來建立堆結構應該代碼會有一些區(qū)別（代碼量應該會大一些）。性能分析：堆排序的時間復雜度是O（n*lgn），空間復雜度是O（n）。希望本文對正在學習基礎數據結構算法的同學有所幫助。