基础算法(堆排序)

算法

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

算法步骤

  1. 先将初始文件Array[1..n]建成一个大根堆，此堆为初始的无序区。

  2. 再将关键字最大的记录Array[1]（即堆顶）和无序区的最后一个记录Array[n]交换，由此得到新的无序区Array[1..n-1]和有序区Array[n]，然后再把无序区建成一个大根堆，然后再次将Array[1..n-1]中关键字最大的记录Array[1]和该区间的最后一个记录Array[n-1]交换.

下面是算法的Swift实现:

/// 将Array中的index位置堆化
///
/// - Parameters:
///   - array: 数组
///   - index: 位置
///   - end: 数组的最后位置
func maxHeapify(array: inout [Int], index:Int, end:Int){
    var parentIndex = index
    var endIndex = end
    
    while true {
        var leftChildIndex = parentIndex * 2 + 1
        var rightChildIndex = leftChildIndex + 1
        
        var childIndex = leftChildIndex
        if childIndex > endIndex {
            break
        }
        if childIndex + 1 <= endIndex && array[leftChildIndex] < array[rightChildIndex] {
            childIndex += 1
        }
        if array[parentIndex] < array[childIndex]{
            swap(&array[childIndex], &array[parentIndex])
            parentIndex = childIndex
        }else{
            break
        }
    }
}
/// 创建大根堆
func creatMaxHeap(array: inout [Int]){
    for i in (0...(array.count - 1) / 2).reversed(){
        maxHeapify(array: &array, index: i, end: array.count - 1)
    }
}
/// 堆排序
func heapSort(array: inout [Int]){
    creatMaxHeap(array: &array)
    for i in (0...array.count - 1).reversed(){
        if i != 0{
            swap(&array[0], &array[i])
        }
        maxHeapify(array: &array, index: 0, end: i - 1)
    }
}