二叉堆排序

二叉堆的内容详见上篇http://www.cnblogs.com/deltadeblog/p/8576488.html

可以利用二叉堆对数组排序，主要包含两步：将原始数组重新组织使之成为二叉堆；数组的第一个元素为最大或最小，取出后对数组使用sink()函数保持堆有序，依次进行。

堆的构造

将一个包含N个元素的数组构造成二叉堆。方法1是使用swim()函数从左到右遍历数组的每一个元素，

该方法的复杂度为O(NlogN)。

另一个方法是使用sink()函数从右至左遍历数组元素，由于叶子结点下没有其他节点，所以sink()函数可以从分支节点开始遍历，不要遍历每个数组元素。sink(i) ，i=N/2; i>=1; i--

实现代码如下：

for (int i=N/2; i>=1; i--) sink(a, N, i);

算法复杂度：少于2N次比较及N次交换。

排序

将数组构造为堆，则数组的第一个元素即是最大（或最小），将该元素与数组最后一个元素交换。

对余下的元素（0 - N-2）使用sink()函数继续进行堆构造并与最后一个元素交换。

整个算法的代码如下：

import java.util.Arrays;

public class StackSort {

    private static boolean less(int[] a, int i, int j) {
        return a[i-1]<a[j-1];
    }

    private static void exch(int[] a, int i, int j) {
        int temp = a[i-1];
        a[i-1] = a[j-1];
        a[j-1] = temp;
    }

    public static void sink(int[] a, int N, int i) {

        while (2*i <= N) {

            int j = 2*i;
            while(j<N && less(a, j, j+1)) j++;
            if (!less(a, i, j)) break;
            exch(a, i, j);

            i = j;
        }
    }

    public static void sort(int[] a) {

        int N = a.length;
        // 使用sink()对数组a堆排序
        // 使之成为二叉堆
        for (int i=N/2; i>=1; i--) sink(a, N, i);
        // 对数组a排序
        for (int i=N; i>1; i--) {
            exch(a, 1, i);
            sink(a, i-1, 1);
        }
    }

    public static void main(String[] args) {

        int[] a = {8,3,7,10,9,12,6};
        sort(a);
        System.out.println(Arrays.toString(a));
    }
}

算法复杂度：