heapsort 堆排序

1.基本描述

? 堆排序 heap sort 指利用堆这种数据结构所设计的一种排序算法。

? 要求完全二叉树

? 这边我只写最大堆

? 堆排序归分在选择排序。

? 稳定性 不稳定

? 时间复杂度
$$
O(nlog_2n)
$$
? 空间复杂度
$$
O(1)
$$

2. 最大堆进行升序排序思想：

1. 初始化堆 ，将数列 [0,n-1] 构造成最大堆

2. 交换数据， 将array[0]和array[n-1]交换， 然后将 array[0…n-2] 重新调整为最大堆，以此类推

3. 这里有一点需要注意，无论是初始化堆，还是交换数据，都调用maxHeapDown，他的参数是 array[] , int start ,int end. 这里 三个参数一个都不能少，start 我觉得这里不好，应该形容为node节点。end可以理解，在交换数据时，需要调整的堆大小是不断变小。 start 这个参数比较微妙。我的理解是调整这个节点在其子节点中的位置，并在原来的位置替换合理的节点(注 不是他最后的位置的节点)。而由于在交换数据时，本身堆除了跟节点，就是符合最大堆特性。就像初始化堆一样，需要从底往上初始化。(这边的参数也是参考 如果天空不死)

   由于已经符合，所以直接调整节点 array[0] 即可。

   所以初始化堆也好，交换数据也好，本质上就是在筛选调整节点位置。这只是我的理解。,,,,堆排序初始化需要从下往上才能初始化最大堆。而交换数据相当于初始化堆的最后一步再现。

3. 代码剖析

? heapSortAsc

    private static void heapSortAsc(int[] array) {
        int i;
        int n=array.length;
        for (i=n/2-1;i>=0;i--) //初始化堆
            maxheapDown(array,i,n-1); // 注意参数，遍历所有非叶节点

        for (i=n-1;i>0;i--){  //交换数据
            int tmp=array[0];
            array[0]=array[i];
            array[i]=tmp;
            maxheapDown(array,0,i-1); // 只有根节点不符合最大堆的要求
        }
    }

? maxheapDown

private static void  maxheapDown(int[] array,int start,int end){    //start 理解为 node 节点更好。 或者干脆改过来吧
        int c=start;                                                    //调整某个节点在适当分支
        int left=2*c+1;                                                 //这样0，i-1 参数更加容易理解
        int tmp=array[c];
        for (;left<=end;c=left,left=2*left+1){
            if (left<end&&array[left]<array[left+1])   //left<end  必须放在前面
            {
                left++; //选择大的往上面替换。
            }
            if(tmp>=array[left])
                break;
            else {
                array[c]=array[left];
                array[left]=tmp; // 疑问二，tmp一直不变
            }
        }
    }

# heapsort

原文：https://www.cnblogs.com/EsMussSeinHui/p/11156235.html