堆排序详解

堆排序是利用堆这种数据结构的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质；子节点的键值或索引总是小于（或者大于）它的父节点。堆排序是利用堆的概念来排序的选择排序。 堆可以分为：

1. 大定堆：每个节点的值都大于或等于其子节点的值，在堆排序中用于升序排序。
            2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序中用于降序排序。

1.算法步骤

• 将未排序的数组构建成一个堆，根据（升序、降序）选择大顶堆或小顶堆。
• 把堆首（最大值）和堆尾互换。
• 把堆的尺度缩小1，调整堆大小
• 重复步骤2，直到堆的尺寸为1

2.算法演示流程

3.算法代码

    var len; //多个函数都要使用这个数据长度，所以声明在全局

    function buildMaxHeap(arr){
        len = arr.length;
        for(var i = 0; i < Math.floor(len / 2); i--){
            heapifyChange(arr);
        }
    }

    function heapifyChange(arr, i){
        var left  = 2 * i + 1;
        var right = 2 * i + 2;
        var largest = i;

        if(left < len && arr[left] > arr[largest]){
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);

            // 修改之前的节点
            heapifyChange(arr, largest);
        }
    }

    // 交换方法
    function swap(arr, i, j){
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = arr[i];
    }

// 堆排序
    function HeapSort(arr){
        // 构建大顶堆；
        buildMaxHeap(arr);

        for(var i = arr.length - 1; i > 0; i--){
            swap(arr, 0, i);
            len--;

            // 堆排序
            heapifyChange(arr, 0);
        }
        return arr;
    }