堆排序

堆排序是通过构建堆来对元素进行排序的。主要分为两个步骤:堆的构建下沉排序。

第一步堆的构建:就是将无序的元素构建成堆,这一步完成之后,元素就成为堆有序的元素。这一步骤可以通过上浮或下沉来完成。因此,当我们完成堆的构建之后,最大的元素就在二叉树的根节点上。此时,就该进行第二步了。

第二步就是下沉排序:此时,我们已经得到了一个堆有序的元素集合,我们要做的就是通过把最大的元素也就是根节点上的元素与最后一个元素交换位置,交换之后“堆有序”的状态被打破,我们需要再次通过下沉排序来将根节点上的元素下沉到合适的位置,但与第一次构建堆时不同的是,这次下沉的范围应该把最后一个位置排除掉,因为那里放着最大的元素,那个就是它最终的位置。不断重复这个过程,下沉排序的范围也在一直缩小,最终只剩下了根节点自己,堆排序也就完成了。

堆(二叉堆):二叉堆是一组能够用堆有序的二叉树排序的元素,并在数组中按照层级存储(不适用数组第一个位置)

为什么不适用第一个位置:为了方便表示结点的父结点和子结点。只要不适用第一个结点也就是下标为0的位置,那么任何一个元素,比如i的父结点位置就是i/2向下取整,子结点位置就是2i和2i+1

堆有序:当一颗二叉树的每个结点都大于等于他的两个子结点时,它被称为堆有序。 上浮和下沉:两种达到堆有序的方法。结点不断地和父结点交换位置到达堆有序叫做上浮,不断的跟子结点交换位置达到堆有序叫做下沉。

查看堆排序动画演示请回复:堆排序动画

public class Heap {
    public static int temp;
    public static void sort(int[] array){
        int N = array.length;
        int[] newarray = new int[N+1];
        System.arraycopy(array, 0, newarray, 1, N);
        sort(newarray,true);
        System.arraycopy(newarray, 1, array, 0, N);
    }
    public static void sort(int[] array,boolean flag){
        int N = array.length-1;
        //堆的构建
        for (int i=N/2;i>=1;i--){
            sink(array,i,N);
        }
        //下沉排序
        while (N>1){
            temp = array[1];
            array[1]=array[N];
            array[N]=temp;
            sink(array,1,--N);
        }
    }
    //小的元素下沉
    private static void sink(int[] array, int k, int N) {
        while (2*k<=N){
            int j = 2*k;
            if (j<N&&array[j]<array[j+1])j++;
            if (array[k]>=array[j])break;
            temp = array[k];
            array[k] = array[j];
            array[j] = temp;
            k=j;
        }
    }
}

本文分享自微信公众号 - Vegout(t10244201),作者:naget

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 初级排序算法

    今天分享给您的是三种初级排序算法,但绝对也是经典排序算法。平时,当我们遇到需要排序的问题时,也许第一反应就是xxx.Sort()。太多的库函数为我们实现了排序的...

    naget
  • 希尔排序

    如果上一篇初级排序算法中的插入排序你已经熟悉,那么今天的这个希尔排序对你来说就要简单一些。希尔排序,就是使用不同增量进行一遍一遍的插入排序的排序算法。首先,增量...

    naget
  • 归并排序

    归并排序的一切都是基于归并这一操作,具体来说就是把两个有序的小数组归并成一个有序的大数组。首先从这两个数组中各按顺序取出一个元素,将小的元素先放入大数组,大的后...

    naget
  • 堆排序(HeapSort)之java实现

    堆是一种重要的数据结构,为一棵完全二叉树, 底层如果用数组存储数据的话,假设某个元素为序号为i(Java数组从0开始,i为0到n-1), 如果它有左子树,那么...

    MickyInvQ
  • 看动画学算法之:排序-选择排序

    选择排序就是从数组中选择出来最大或者最小的元素,然后将其和队首或者队尾的元素进行交互。

    程序那些事
  • 初探numpy——广播和数组操作函数

    若数组a,b形状相同,即a.shape==b.shape,那么a+b,a*b的结果就是对应数位的运算

    LRainner
  • Clojure 学习入门(19)—— 数组

    user=> (into-array [1 2 3]) #<Integer[] [Ljava.lang.Integer;@4b0ea9ba> user=> (s...

    阳光岛主
  • php学习笔记之 array+array 和 array_merge

    <?php

    solate
  • python--几种快速排序的实现以及运行时间比较

    快速排序的基本思想:首先选定一个数组中的一个初始值,将数组中比该值小的放在左边,比该值大的放在右边,然后分别对左边的数组进行如上的操作,对右边的数组进行如上的操...

    绝命生
  • 《剑指offer》第12天:旋转数组的最小数字

    把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。例如数组 {3,4,5,1,2} 为...

    程序员小浩

扫码关注云+社区

领取腾讯云代金券