排序-4- 堆排序

堆排序

以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。

• 最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
• 创建最大堆（Build_Max_Heap）：将堆所有数据重新排序
• 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

/*
 * 建堆
 * @param arr 看作完全二叉树
 * @param currentParentNode  当前父节点位置
 * @param size 数组长度
 * */
    function heapify(arr,currentParentNode,size){
        if(currentParentNode<size){
            //得到左右子节点的位置
            var left=currentParentNode*2+1;
            var right=left+1;
            var max = currentParentNode;
            if(left<size){
                if (arr[left]>arr[max]) {
                    max=left;
                }
            }
            if(right<size){
                if (arr[right]>arr[max]) {
                    max=right
                }
            }
//          使得当前最大节点是父节点
            if (max!=currentParentNode) {
                var temp=arr[max];
                arr[max]=arr[currentParentNode];
                arr[currentParentNode]=temp;
//              继续比较
                heapify(arr,max,size);
            }
        }
    }
    
    /*完成一次建堆，最大的值在顶部，一般从最后一个数开始建堆，
     让数组的左子树和右子数都有父>子的条件*/
    function maxHeapify(arr,size){
           // 从数组的尾部开始，直到第一个元素(角标为0)
        for (var i=size-1;i>=0;i--) {
            heapify(arr,i,size);
        }
    }
    
    function heapSort(arr){
        //不断建堆，和当前数组的第一个交换即可
            for (var k=0;k<arr.length;k++) {
                maxHeapify(arr,arr.length-k);//每得到一个最大值，数组长度就会少一个
                //由上面可知，当前最大的元素时堆顶元素，也就是第一个元素,和最后一个元素交换，得到排序后的数组
                var temp = arr[0];
                arr[0]=arr[arr.length-1-k]
                arr[arr.length-1-k]=temp;
                console.log(arr.toString())//打印出当前排序的数组
            }
    }