堆排序算法

     所谓堆，是满足如下条件的一个序列：n个元素，任意第i个元素具备同时不比2i和2i+1个元素小或者大。把堆看成一个完全二叉树，那么这棵树所有左右子节点都要具备同时不比父节点小或者大。

    从堆得定义可以看出序列的第一个元素，也就是堆顶元素一定是整个序列里最大或者最小的元素。堆排序就是利用了堆的这一特性来实现的。

    堆排序可以简单文字描述如下：1.把一个无序序列调整成一个堆；2.输出堆顶元素，然后把剩下的序列调整成堆。3.如果堆还有元素，继续做操作2。

    怎么把一个无序序列调整成一个堆呢？父节点和子节点根据条件不停调整可以得到一个堆，这个过程称之为筛选。把这个序列看成一个完全二叉树，最后一个非叶子节点是第n/2求整个元素，筛选只需要从这一个元素开始递减一直到第一个元素即可。

    接着说说取走堆顶元素后，怎么调整这个堆：从堆顶拿走一个最大或者最小值后，把堆得最后一个元素放到堆顶，这时堆顶的两个子节点仍然是堆，这时我们沿着堆顶开始向下筛选，很快就能得到一个新堆了。

    堆排序java实现代码：

public class HeapSort extends BaseSort
{

    @Override
    protected void sortAlg(int[] ls)
    {
        buildHeap(ls, ls.length - 1);
        hsort(ls, ls.length - 1);
    }

    private void hsort(int[] ls, int end)
    {
        swap(ls, 0, end);
        for(int i = end-1; i > 0; i--)
        {
            maxHeapifyk(ls, 0, i);
            swap(ls, 0, i);
        }
    }

    private void buildHeap(int[] ls, int end)
    {
        for(int i = ((end - 1) >> 1); i >= 0; i--)
        {
            maxHeapifyk(ls, i, end);
        }
    }

    /**
     * Ki>=K2i Ki>=K2i+1
     * 
     * @param ls
     * @param i
     */
    private void maxHeapifyk(int a[], int i, int end)
    {

        int maxIndex = i;
        int finish = (end - 1) >> 1;
        for(int j = i; j <= finish;)
        {
            int left = (j << 1) + 1;
            int right = left + 1;
            if(left <= end && a[left] > a[j])
                maxIndex = left;
            if(right <= end && a[right] > a[maxIndex])
                maxIndex = right;
            if(maxIndex != j)
            {
                swap(a, maxIndex, j);
                j = maxIndex;
            }
            else
            {
                break;
            }
        }
    }

    堆排序的时间复杂度稳定在O(nlogn)