堆排序(Heap Sort),java版.

堆排序(Heap Sort),java版.

发表于：2008年12月28日 | 分类：算法 | 标签： sort | views(2,392)

版权信息: 可以任意转载, 转载时请务必以超链接形式标明文章原文出处, 即下面的声明.

 

原文出处：http://blog.chenlb.com/2008/12/heap-sort-for-java.html

堆排序是高效的排序方法。没有最坏情况（即与平均情况一样），空间占用又小，综合效率比快速排序还好。

堆排序原理：1、从数据集中构建大顶堆（或小顶堆）。2、堆顶与最后一个数据交换，然后维护堆顶使它还是大顶堆（或小顶堆）。3、重复2的过程，直到剩下一个数据。
时间复杂度：平均O(nlog₂n)，最坏情况O(nlog₂n)。

示例代码：

package com.chenlb.sort;

import java.util.Arrays;

/**
 * 堆排序.
 *
 * @author chenlb 2008-12-28 下午03:52:53
 */
public class HeapSort {

    private static int parentIdx(int childIdx) {
        return (childIdx - 1) / 2;  //索引从0开始, 注意childIdx=0时返回0
    }

    private static int leftChildIdx(int parentIdx) {
        return parentIdx*2 + 1;
    }

    /**
     * 构建大顶堆.
     * @author chenlb 2008-12-28 下午03:52:23
     */
    private static void buildMaxHeap(int[] datas) {
        int lastIdx = datas.length -1;
        for(int i=parentIdx(lastIdx); i>=0; i--) {
            int k = i;
            /*boolean isHeap = false;*/
            while(/*!isHeap && */leftChildIdx(k) <= lastIdx) {
                int j = leftChildIdx(k);
                if(j < lastIdx) {    //有两个孩子
                    if(datas[j] <= datas[j+1]) { //j+1 比较大, 选择大的
                        j++;
                    }
                }

                if(datas[k] > datas[j]) {    //父的比较大
                    /*isHeap = true;*/
                    break;
                } else {
                    SortUtil.swap(datas, k, j);
                    k = j;
                }
            }
        }
    }

    /**
     * 堆顶改变, 要维护大顶堆.
     * @author chenlb 2008-12-28 下午03:53:04
     */
    private static void maintainMaxHeap(int[] datas, int lastIdx) {
        int k = 0;
        while(k <= parentIdx(lastIdx)) {
            int j = leftChildIdx(k);
            if(j < lastIdx) {    //有两个孩子
                if(datas[j] <= datas[j+1]) { //j+1 比较大, 选择大的
                    j++;
                }
            }
            if(datas[k] < datas[j]) {    //父结点比较小
                SortUtil.swap(datas, k, j);
                k = j;
            } else {
                break;
            }
        }
    }

    public static int[] sort(int[] datas) {
        buildMaxHeap(datas);
        int lastIdx = datas.length - 1;
        while(lastIdx > 0) {
            SortUtil.swap(datas, 0, lastIdx);
            lastIdx--;
            if(lastIdx > 0) {
                maintainMaxHeap(datas, lastIdx);
            }
        }
        return datas;
    }

    public static void main(String[] args) {
        int[] datas = {5,1,3,4,9,2,7,6,5};//{2, 9, 3, 7, 8, 6, 4, 5, 0, 1};

        /*buildMaxHeap(datas);
        System.out.println(Arrays.toString(datas));*/

        sort(datas);
        System.out.println(Arrays.toString(datas));

        datas = SortUtil.randomDates(10);
        sort(datas);
        System.out.println(Arrays.toString(datas));

    }

}

运行结果：

[1, 2, 3, 4, 5, 5, 6, 7, 9]
[18, 185, 239, 304, 407, 489, 546, 688, 744, 821]

待排序数据：5, 1, 3, 4, 9, 2, 7, 6, 5
构建大顶堆的过程：
5, 1, 3, 4, 9, 2, 7, 6, 5
5, 1, 3, 6, 9, 2, 7, 4, 5
5, 1, 7, 6, 9, 2, 3, 4, 5
5, 9, 7, 6, 1, 2, 3, 4, 5
9, 5, 7, 6, 1, 2, 3, 4, 5 -> 9, 6, 7, 5, 1, 2, 3, 4, 5

排序过程：
9, 6, 7, 5, 1, 2, 3, 4, 5
7, 6, 5, 5, 1, 2, 3, 4, 9
6, 5, 5, 4, 1, 2, 3, 7, 9
5, 5, 3, 4, 1, 2, 6, 7, 9
5, 4, 3, 2, 1, 5, 6, 7, 9
4, 2, 3, 1, 5, 5, 6, 7, 9
3, 2, 1, 4, 5, 5, 6, 7, 9
2, 1, 3, 4, 5, 5, 6, 7, 9
1, 2, 3, 4, 5, 5, 6, 7, 9

红色为交换。