排序算法-选择排序-堆排序

堆排序是一种树型选择排序方法。在排序过程中，将 L [ 1... n ] L[1 ... n] L[1...n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序中选择关键字最大（或最小）的元素。

堆是一棵完全二叉树，此处的堆排序主要利用了完全二叉树的顺序存储结构。

大根堆：任意的父节点都要大于等于其孩子结点。大根堆的根结点必然是树(堆)中最大的元素.
小根堆：任意的父节点都要小于等于其孩子结点。小根堆的根结点必然是树(堆)中最小的元素.

完全二叉树的定义可以看此处。在此处的完全二叉树的顺序存储是从下标1开始的，这样就和完全二叉树从1开始编号对应上了。对于下标为 i i i的结点，其左孩子为 2 i 2i 2i，右孩子为 2 i + 1 2i+1 2i+1（如果该结点存在左右孩子的话），其父节点为 ⌊ i / 2 ⌋ lfloor i/2rfloor ⌊i/2⌋,所在层次为 ⌊ l o g 2 n ⌋ + 1 lfloor log_{2}nrfloor + 1 ⌊log2​n⌋+1。

另外在完全二叉树的顺序存储中，树有n个结点，如果结点 i i i有左孩子，则有 2 i < = n 2i<=n 2i<=n，有右孩子则满足 ( 2 i + 1 ) < = n (2i+1)<=n (2i+1)<=n。完全二叉树中的分支结点满足 i < = ⌊ n / 2 ⌋ i<=lfloor n/2rfloor i<=⌊n/2⌋。

堆排序的过程中，每次选取大(小)根堆中的根结点将其交换到最终位置即可完成一趟排序。比如要进行升序排序，则可以利用大根堆来完成，每次将数组第一个元素即大根堆的根结点交换到数组未排序的序列 末尾即可，现在大根堆被破坏，然后重新调整堆，使其满足大根堆的要求，然后再交换即可。堆排序的关键就在建堆和调整堆。

思路：将所有的非叶子结点都检查一遍，是否满足大根堆的要求，如果不满足则进行调整。

n个结点的完全二叉树，最后一个结点是第 ⌊ n / 2 ⌋ lfloor n/2rfloor ⌊n/2⌋个结点的孩子。对第 ⌊ n / 2 ⌋ lfloor n/2rfloor ⌊n/2⌋个结点为根的子树筛选（对于大根堆：若根结点的关键字小于左右孩子中关键字较大者，则交换），使该子树成为堆。之后向前依次对各节点 ( ⌊ n / 2 ⌋ − 1 (lfloor n/2rfloor-1 (⌊n/2⌋−1~ 1 ) 1) 1)为根的子树进行筛选，判断结点值与左右孩子值较大者的大小，若根小则交换，交换后可能会破坏下一级的堆，于是采用上述方法构造下一级的堆，直到该结点为根的子树构成堆为止。反复利用上述调整堆的方法，直到根结点为止。

建立堆的代码：

public static void BuildMaxHeap(int[] nums, int len){
        for(int i=len/2;i>0;--i){  // 从len/2到1反复调整堆
            AdjustDown(nums, i, len);
        }
    }

    public static void AdjustDown(int[] nums, int k, int len){
        //将元素k向下进行调整
        nums[0] = nums[k];  // 将要比较的根结点暂存在nums[0]处
        for(int i=2*k;i<=len;i=k*2){
            if(i=nums[i]) break;          //筛选结束
            else{
                nums[k] = nums[i];       //将nums[i]调整到双亲结点上
                k=i;                     //修改k值，以便继续向下筛选
            }
        }
        nums[k] = nums[0]; //被筛选结点的值放入最终位置
    }

堆排序的过程中，每一趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换）。并将待排序元素再次调整为大根堆（小元素不断下坠。）

完整代码

public class HeapSort {
    public static void main(String[] args) {
        int[] nums = {-1,32,67,8,54,31,89,23,18}; // 下标0不存储排序元素。
        heapsort(nums,nums.length-1);
        for(int i=1;i1;--i){ //len个数一共需要n-1趟交换过程
            int temp = nums[i];
            nums[i] = nums[1];
            nums[1] = temp;
            AdjustDown(nums,1,i-1); //交换之后破坏了堆，所以自顶向下调整
        }
    }

    public static void BuildMaxHeap(int[] nums, int len){
        for(int i=len/2;i>0;--i){  // 从len/2到1反复调整堆
            AdjustDown(nums, i, len);
        }
    }

    public static void AdjustDown(int[] nums, int k, int len){
        //将元素k向下进行调整
        nums[0] = nums[k];  // 将要比较的根结点暂存在nums[0]处
        for(int i=2*k;i<=len;i=k*2){
            if(i=nums[i]) break;          //筛选结束
            else{
                nums[k] = nums[i];       //将nums[i]调整到双亲结点上
                k=i;                     //修改k值，以便继续向下筛选
            }
        }
        nums[k] = nums[0]; //被筛选结点的值放入最终位置
    }
}

时间复杂度：
首先分析 AdjustDown() 的时间复杂度，显然，一个结点每向下调整一层，最多对比关键字2次。假设该结点在第i层，堆高为h，那么该结点最多向下调整h-i次，最多对比关键字 2 ( h − i ) 2(h-i) 2(h−i)次。
n个结点的完全二叉树的高度为 h = ⌊ l o g 2 n ⌋ + 1 h=lfloor log_{2}n rfloor+1 h=⌊log2​n⌋+1.

所以建堆的过程，关键字的对比次数不超过 4 n 4n 4n，建堆的时间复杂度为 O ( n ) O(n) O(n)。
每经过一趟排序，需要将堆顶元素交换到待排序序列的末尾，交换之后从堆顶向下调整堆，根结点最多向下调整 h − 1 h-1 h−1层，而每向下调整一层，最多对比关键字两次，因此每一趟排序时间复杂度不会超过 O ( h ) = O ( l o g 2 n ) O(h)=O(log_{2}n) O(h)=O(log2​n)，总共需要n-1趟，所以时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。

因此堆排序的时间复杂度为： O ( n ) + O ( n l o g n ) = O ( n l o g n ) O(n) + O(nlogn) = O(nlogn) O(n)+O(nlogn)=O(nlogn)

空间复杂度为：O(1)

稳定性：不稳定。在进行筛选时，有可能将后面相同的关键字的元素调整到前边，所以堆排序算法是一种不稳定的算法。