排序算法之堆排序

[xuexueq]

堆排序（不稳定，相同的两个数字会被交换）（适合大数据量的排序）

• 堆和数组的相互关系

对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、孩子结点的下标：(注意：数组都是 Zero-Based，以零开始)

Parent(i) = floor((i-1)/2)，i 的父节点下标
Left(i) = 2i + 1，i 的左子节点下标
Right(i) = 2(i + 1)，i 的右子节点下标

最大堆调整（MAX‐HEAPIFY）的作用是保持最大堆的性质，是创建最大堆的核心子程序，作用过程如图所示：

但是一次调整后，堆仍然违反堆性质，所以需要递归的测试，使得整个堆都满足堆性质。

步骤:

• 最大堆调整函数
• 创建最大堆数组函数
• 堆排序（一步步将堆缩小）

function heapSort(arr) {
    function swap(arr, i, j) {
        let temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp
    }

    //最大堆调整函数
    function maxHeapify(arr, index, heapSize) {
        let iMax,
             iLeft,
             iRight
             
        //这里可以使用递归。递归调用需要压栈/清栈，和迭代相比，性能上有略微的劣势   
        while(true) {
            iMax = index   // index为当前结点
            iLeft = 2 * iMax + 1
            iRight = 2 * (iMax + 1)
            
            if(iLeft < heapSize && arr[iLeft] > arr[index]) {//index
                iMax = iLeft
            }
            
            if(iRight < heapSize && arr[iRight] > arr[iMax]) {//iMax
                iMax = iRight
            }
            
            if(iMax != index) {
                swap(arr, iMax, index)
                index = iMax
            }else {  //记得终止，不然会无限循环，导致内存溢出
                break
            }
        }
    }
    
    //从最后一个非叶子节点开始，自下而上进行最大堆调整（调用最大堆调整函数）
    function buildMaxHeap(arr) {
        let iParent = Math.floor((arr.length - 1) / 2)
        
        for(let i = iParent; i>=0; i--) {  // i>=0
            maxHeapify(arr, i, arr.length)
        }
    }
    
    //对于调整好的最大堆数组，将堆顶元素与堆底元素交换，然后将堆底最后一位元素砍掉（隔离）,产生的新的堆会一点点缩小，
    //此时新的堆只需要对下标为0的元素进行最大堆调整即可。调整完了之后，重复上述步骤，直到堆数组只剩下一位根元素，就完成了对数组从小到大的排序。
    function sort(arr) {
        buildMaxHeap(arr)
        
        let len = arr.length
        for(let i = len - 1; i>0; i--) {
            swap(arr, 0, i)
            maxHeapify(arr, 0, i) // i
        }
        
        return arr
    }
    
    return sort(arr)
}

算法分析：

最佳情况：T(n) = O(nlogn)
最差情况：T(n) = O(nlogn)
平均情况：T(n) = O(nlogn)

Reference

堆排序 (Heap Sort)