首页 > 编程语言 > 详细

用分解的方式学算法006——堆排序

时间:2018-05-19 23:10:34      阅读:243      评论:0      收藏:0      [点我收藏+]

堆排序是使用二叉堆实现的优先队列来进行排序的。

先介绍几个概念:

第一个是优先队列,优先队列是一种数据结构,它支持两种操作:删除最大元素和插入元素。

第二个是二叉堆,二叉堆是一种数据结构,它能够和那红的实现优先队列的基本操作。它使用一个数组来保存数据,在这个数组中,每个元素都要保证大于等于另两个特定位置的元素。相应的,这些位置的元素又至少要岛屿等于数组中的另两个元素,以此类推。

如果将所有元素画成一棵二叉树,将每个较大元素和两个较小元素用边连接就可以看出这种结构。

一般使用完全二叉树来表示。

技术分享图片

下面就进入正题,给出完整代码:

package asen.yang;

public class heapSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        //数组的第一个元素(索引0位置)不使用,因此赋值为MIN_VALUE。
        int[] a = { Integer.MIN_VALUE, 5, 1, 4, 8, 3, 9, 0, 2, 7, 6 };
        sort(a);//进行排序
        //打印输出,从下标1开始打印
        for (int i = 1; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

    //比较数组中两个索引的元素的大小,如果i>j返回true,否则返回false
    private static boolean less(int[] pq, int i, int j) {
        return pq[i] < pq[j];
    }

    //交换数组中两个索引的元素的值
    private static void exch(int[] pq, int i, int j) {
        int t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }

    //上浮操作
    private static void swim(int[] pq, int k) {
        while (k > 1 && less(pq, k / 2, k)) {
            exch(pq, k / 2, k);
            k = k / 2;
        }
    }

    //下沉操作
    private static void sink(int[] pq, int k, int N) {
        while (2 * k <= N) {
            //k的两个子结点是2k和2k+1,
            int j = 2 * k;
            if (j < N && less(pq, j, j + 1)) {
                //这里判断2k与2k+1的大小,选择其中较大的元素
                j++;
            }
            //如果k(父)节点大于等于j(子)结点,则说明已经调整为有序的状态
            if (!less(pq, k, j)) {
                break;
            }
            
            //否则交换k(父)结点和j(子)结点,使之有序
            exch(pq, k, j);
            //交换完毕,另j(子)结点成为新的比较对象
            k = j;
        }
    }

    public static void sort(int[] a) {
        //数组可用长度为实际长度-1
        int N = a.length - 1;
        
        //构建堆
        for (int k = N / 2; k >= 1; k--) {
            sink(a, k, N);
        }
        
        //堆排序
        while (N > 1) {
            exch(a, 1, N--);
            sink(a, 1, N);
        }
    }
}

 

其中关键的是sink方法,这个方法的作用是在堆有序的状态因为某个即诶单变得比它的两个子结点或是其中之一更小了而打破了,可以通过将它和它的两个子结点中的较大者交换来恢复堆。

交换可能会在子即诶单处继续打破堆的有序状态,因此需要不断用相同的方式将其修复,将结点向下移动直到它的子结点都比它小或是达到了堆的底部。

最后的sort方法实现了排序的整体流程。

这里是从右至左用sink函数构造子堆。开始时只需要扫描数组中的一半元素,因为可以跳过大小为1的子堆。最后在位置1上调用sink方法,扫描结束。

接下来的while循环将醉倒的元素a[1]和a[N]交换并修复了堆,如此重复直到堆变空。

最后打印的结果为:

技术分享图片

与预期是一致的。

 

用分解的方式学算法006——堆排序

原文:https://www.cnblogs.com/asenyang/p/9061850.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!