数组-堆排序

采用堆排序方式对数组进行排序

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

摘一个示例做个说明.
示例 1：
输入: [0,5,9,3,12,7]
输出: [0,3,5,7,9,12]

在堆的数据结构中,堆中最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点).

堆的操作:

1. 最大堆调整(Max Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
2. 创建最大堆(Build Max Heap) :将堆中的所有数据重新排序
3. 堆排序(HeapSort):移除位在第一个数据的根结点,并做最大堆调整的递归运算.
4. 算法演示 堆排序演示.gif

算法分析:

1. 时间复杂度
   堆排序总的平均时间复杂度为O(n logn).
2. 算法稳定性
   堆排序是一种不稳定排序算法.

代码实现-Swift版本:

func heapSort(nums: inout [Int]){
    // 数据生成堆
    for i in (0 ..< nums.count / 2 ).reversed(){
        // 生成堆过程,满足每个父结点大于子结点值,从最底层父结点开始找
        heapify(array: &nums, parent: i, length: nums.count)
    }
    // 堆数据排序
    for j in (1 ..< nums.count).reversed() {
        // 交换第一个数据和第J个,这样保证最后一个是最大值,然后继续堆生成再交换,直到结束
        nums.swapAt(0, j)
        heapify(array: &nums, parent: 0, length: j)
    }
}

func heapify(array:inout [Int], parent:Int,length:Int) {
    var parentIndex = parent
    let temp = array[parentIndex]
    var child = 2*parentIndex+1//2n+1:左孩子,2n+2:右孩子,默认左结点值最大
    //生成堆
    while child<length {
        //如果有右结点且左结点值小于右结点值则最大值为右结点
        if child+1<length && array[child]<array[child+1]{
            child += 1
        }
        if temp>array[child]{//父节点大于左右孩子节点
            break
        }
        // 父结点值等于最大值
        array[parentIndex] = array[child]
        parentIndex = child
        // 子结点的左结点
        child = 2*child+1
    }
    array[parentIndex] = temp
}

测试用例:

var nums = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

参考:

• 堆排序百科
• 一像素

考察要点:

• 数组
• 排序