Swift.堆排序

import Foundation

class HeapSortSolution {
    func sort(_ n: [Int]) -> [Int] {
        
        var s = n
        
        //1.初始化堆
        var i = n.count/2 - 1
        while i >= 0 {
            heapAdjust(&s, i, n.count - 1)
            i -= 1
        }
        
        var j = n.count - 1
        var l = 0
        while j > 0 {
            //交换首尾节点
            let temp = s[j]
            s[j] = s[0]
            s[0] = temp

            //再调整
            heapAdjust(&s, 0, n.count - 1 - l )
            j -= 1
            l += 1
        }
        
        return s
    }
    
    func heapAdjust(_ s: inout [Int],_ local: Int,_ len: Int) {
        
        var loc = local
        var child = 2*loc + 1
        while child < len {
            if child + 1 < len && s[child] < s[child+1] {
                child += 1
            }
            
            if s[loc] < s[child] {
                let temp = s[loc]
                s[loc] = s[child]
                s[child] = temp
                loc = child
                child = 2*loc + 1
            }else {
                break
            }
        }
    }
}

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

github地址：https://github.com/cubegao/LeetCode