堆排序

堆排序

堆排序是时间复杂度为O(N*logN)，空间复杂度为O(1)的算法，该算法是不稳定的。
首先二叉堆是满足如下条件的完全二叉树：

1.父节点的值大(小)于等于左右子节点，称为大(小)顶堆;
2.每个节点都满足1的条件;

如下：

堆化后.png

有了这样的堆，如果用于排序，取跟节点的值就行了，然后再把移除取出值后的二叉树再进行一次堆化即可，然后就会发现最大(小)的值又在根节点了。这样可以减少选择排序里的重复比较。

1.考虑一下如何堆化一个数组

a.首先考虑如何把一个除根节点外已经堆化的二叉树的根节点放到合适的位置。

如图，如何为79找到合适的位置:

调整根节点到合适的堆位置.png

堆化一个节点，为它找到合适位置的的方法如下(小顶堆):

/**
*table是待堆化的数组，i是需要堆化的那个根节点,这里是输入0，n是数组的长度-1
*
*
**/
public static void sift(int[] table,int i ,int n){
        int tem = table[i] ;
        //左子节点的位置
        int left = i * 2 + 1;
        //如果存在左子树，那么循环继续
        while(left <= n){
            if(left + 1 <= n && table[left+1] < table[left]){ //如果右子节点存在并且右子节点小于左子节点，比较的值变成了右子节点
                left ++; //use right to compare;
            }
            //如果当前的值大于较小的那个子节点，交换
            if(tem > table[left]){
                table[i] = table[left];
                table[left] = tem;
                i = left;
            }else{
            //如果当前的值大于或者等于当前的较小的值，说明到了合适的位置，终止
                break;
            }
            //下一个左子树的位置是当前位置*2 + 1;
            left = i * 2 + 1;
        }
    }

b.a中已经堆化了一个根节点不满足最小堆的二叉树了，下面就是如何生成一个最小堆了：

首先，叶子节点没有左右子节点，所以是满足1条件的，所以叶子节点的父节点就可以看成是a中的那个根节点，所以第一个堆化的节点应该是从下往上第一个有叶子节点的节点：i = n / 2 -1;
而一旦堆化了一个父节点，那么父节点的父节点又满足了a条件，可以继续循环往下了。

如图,26,27可以看成满足已经堆化，那么第一个需要堆化的就是16,位置是5/2 -1 = 1

未堆化的二叉树.png

所以堆化一个数组的代码如下：

    public static void generateHeap(int[] table){
        int n = table.length;
        //i==0时，即使到了根节点
        for(int i = n / 2 - 1 ; i >= 0 ; i--){
            sift(table,i,n - 1);
        }
        print(table);
    }

2.堆化后的排序

一旦数组堆化后，排序就容易了，直接取出table[0]的值，即是被选择出来的最小值，然后把它放到数组的尾部，然后把原来尾部的那个数放到原来table[0]的位置
堆化后：

堆化后.png

取出根节点值(最小的值)到末尾，同时把末尾值放到根节点，如下

排序.png

再为根节点35找到合适的位置，即是1a的堆化根节点。

public static void heapSort(int[] table){
        generateHeap(table);
        int tem;
        for(int i = table.length - 1 ; i >= 0 ; i--){
            tem = table[i];
            table[i] = table[0];
            table[0] = tem;
            //这里后一个值i-1是因为后面的值是排序后的值，不应该再进行堆化。
            sift(table,0,i-1);
        }

3.完整代码：

//里面出现的英语。。破eclipse无法打中文我会乱说咩。。
public class HeapSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] table = new int[]{81,49,38,65,548,548,1587,97,76,9,84,13};
        heapSort(table);
        print(table);
    }
    
    //change a num from high to low
    public static void sift(int[] table,int i ,int n){
        int tem = table[i] ;
        int left = i * 2 + 1;
        while(left <= n){
            if(left + 1 <= n && table[left+1] < table[left]){ //if right is smaller ,use right to compare
                left ++; //use right to compare;
            }
            if(tem > table[left]){
                table[i] = table[left];
                table[left] = tem;
                i = left;
            }else{
                break;
            }
            
            left = i * 2 + 1;
        }
    }
    
    //generage a heap
    
    public static void generateHeap(int[] table){
        int n = table.length;
        for(int i = n / 2 - 1 ; i >= 0 ; i--){
            sift(table,i,n - 1);
        }
        print(table);
    }
    
    public static void heapSort(int[] table){
        generateHeap(table);
        int tem;
        for(int i = table.length - 1 ; i >= 0 ; i--){
            tem = table[i];
            table[i] = table[0];
            table[0] = tem;
            sift(table,0,i-1);
        }
    }
    
    public static void print(int[] table){
        for(int i : table){
            System.out.print(i + " ");
        }
        System.out.println("");
    }

}