经典排序算法：堆排序（Heap Sort）详解编程语言

什么是堆

首先堆是一个完全二叉树，但同时他具有这样的要求：每一个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；每一个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

如下图是一个大顶堆

在此要补充一个二叉树的性质：二叉树的某个节点下标为i，则它的左孩子的下标一定为2i，右孩子下标一定为2i+1。

案列分析

假如现在我们要对这个序列，{50,10,90,30,70,40,80,60,20}进行堆排序，我们现在要做的：
1. 首先我们要把这个无序序列变成一个堆，构成堆之后，由堆的定义我们知道，堆的根节点一定是整个树当中值最大的。
2. 变成堆后，根节点和树的最后一个结点交换位置，然后弹出该节点，剩下的结点再重新构造成一个新堆。

上述两步关键代码

//具体构建堆的逻辑代码 
void heapAdjust(SqList *L, int s, int m){ 
    int temp, j; 
    temp = L->r[s]; 
    for(j=2*s;j<=m;j*=2){ 
 
        if(j<m && L->r[j] < L->r[j+1]){ 
            ++j; 
        } 
 
        if(temp >= L->r[j]){ 
            break; 
        } 
 
        L->r[s] = L->r[j]; 
        s=j; 
    } 
    L->r[s] = temp; 
} 
 
//排序  
void heapSort(SqList *L){ 
    int i; 
    //先把序列转换为堆  
    for(i = L->length/2; i>0; i--){ 
        heapAdjust(L, i, L->length); 
    } 
    //没交换一次，就转换一次为堆  
    for(i = L->length;i>1;i--){ 
        swap(L, 1, i); 
        heapAdjust(L, 1, i-1); 
    }  
}

说一说heapAdjust这个方法的关键逻辑

1. 首先根据传入的下标，获得一个结点，开始对这个结点操作；
2. 然后根据这个结点，获取到它的左右孩子结点（上面提到的二叉树定义：左孩子为2i， 右孩子为2i+1）；
3. 左右孩子比较，得出值大者跟其父节点交换位置。

初始无序序列树图：

例如，当i=length/2=4时，获取到的结点为30,然后再获取30的左右孩子分别为60,20。由于60大于30，因此30和60交换位置。

最后转换为堆之后的示意图：

完整代码

public class HeapSort { 
 
    /** 
     * 从小到大排列，就是维护一个大根堆 
     * 从大到小排列，就是维护一个小根堆 
     */ 
    public void sort(int[] array){ 
        int size = array.length - 1; 
        //首先构造根堆(即把最大的或者最小的放在根节点)为什么i为size/2，因为构造堆从底向上 
        for(int i = size / 2; i > 0; i--){ 
            heapAdjust(array, i, size); 
        } 
        for(int i = size; i > 0; i--){ 
            swap(array, 1, i); 
            heapAdjust(array, 1, i-1); 
        } 
    } 
 
    public  void heapAdjust(int[] array, int root, int end){ 
        int temp = array[root]; 
        for(int i = root * 2; i <= end; i*=2){ 
            if(i < end && array[i] < array[i+1]){ 
               i++; 
            } 
            if(temp >= array[i]){ 
                break; 
            } 
            array[root] = array[i]; 
            root = i; 
        } 
        array[root] = temp; 
    } 
 
    public void swap(int[] array, int i, int j){ 
        int temp = array[i]; 
        array[i] = array[j]; 
        array[j] = temp; 
    } 
 
    public static void main(String args[]){ 
        int array[] = new int[]{0,50,10,90,30,70,40,80,60,20}; 
        new HeapSort().sort(array); 
 
        for(int i = 1; i < array.length; i++){ 
            System.out.print(array[i] + " "); 
        } 
    } 
}

结果：

时间复杂度

建堆的时间复杂度：O(n)
排序的时间复杂度：
for循环肯定是n的，关键是看heapAdjust，一开始传1，n进去，我们看heapAdjust里的时间复杂度是多少
完全二叉树的性质：

有n个节点的完全二叉树，深度为 log n(向上取整) + 1

因此传1，n进去，假设n为9，那么此时会查找的节点下标为1,2,4,8，也就是走完了整个树n个节点的深度（二分查找）
所以heapAdjust的时间复杂度为：O(logn)
所以假如维护k的堆，heapAdjust的时间复杂度为：O(logk)