选择堆排序.md

堆排序是选择排序的一种变种，大顶堆是节点大于或者等于左右节点的完全二叉树，小顶堆是节点小于或者等于左右节点的完全二叉树。升序排序用大顶堆，降序用小顶堆。

堆排序图解

此时的二叉树对应的图为

一个二叉树对应的父节点可以通过公式(lenght/2 - 1) ~ 0,我们一共有6个元素，对应的父节点索引就是2~0也就是12 8 3,便利节点是从下到上，从右到左的原则。

第一次构建大顶堆

1. 便利节点12，对应的左节点是6，没有右节点，因为12比6大，所以不需要进行互换操作

   

2. 便利节点8，左侧节点是45，右侧节点是1，最大节点是45，45比8大，需要交换位置。

   

   

3. 便利节点3，左侧节点45，右侧节点12。最大节点45，45比3大，所以45和3交换。

   

   

4. 查询节点12，只有左侧节点6，小于12，则不交换位置

   

5. 查询节点3，左侧节点8，右侧节点1，最大节点8，则8大于3交换位置

   

   

6. 查询节点12，左侧节点6，不需要交换

   

7. 到此第一次大顶堆排序完成

   

8. 我们将收尾进行互换

   

   

对剩余的五个元素进行大顶堆排序

我们通过上面进行大顶堆排序之后

第二次大顶堆排序完成

将首尾进行互换

将剩余的四个元素进行大顶堆排序

进行大顶堆排序完毕

将首尾进行位置的互换

将剩下的元素进行大顶堆排序

大顶堆排序之后

将首尾互换

将剩余的两个元素进行大顶堆排序

大顶堆排序完毕之后

首尾互换

剩余一个元素不需要再次排序，则排序完毕。

示例代码

class Solution {
    func heapSort(_ numbers:inout [Int], _ lenght:Int = 0) {
        let _lenght = lenght > 0 ? lenght : numbers.count
        guard _lenght > 1 else {
            return
        }
        let count = _lenght / 2 - 1
        var index = 0
        while count >= index {
            for i in (index ... count).reversed() {
                let leftIndex = 2 * i + 1
                let leftN = numbers[leftIndex]
                let nodeN = numbers[i]
                var swapIndex = i
                if leftN > nodeN {
                    swapIndex = leftIndex
                }
                let rightIndex = 2 * i + 2
                if _lenght > rightIndex {
                    let rightN = numbers[rightIndex]
                    if rightN > leftN {
                        swapIndex = rightIndex
                    }
                }
                if swapIndex != i {
                    self.swap(&numbers, i, right: swapIndex)
                }
            }
            index += 1
        }
        swap(&numbers, 0, right: (_lenght - 1))
        heapSort(&numbers, _lenght - 1)
    }
    func swap(_ numbers:inout [Int], _ left:Int, right:Int) {
        guard numbers.count > left, numbers.count > right else {
            return
        }
        let temp = numbers[left]
        numbers[left] = numbers[right]
        numbers[right] = temp
    }
}