经典排序之堆排序详解

栏目: 编程工具 · 发布时间: 5年前

内容简介:首先我们来看看什么叫做堆排序?若在输出堆顶的最小值之后,使得剩余的n-1个元素的序列重新又构成一个堆,则得到n个元素中的次小值,如此反复,便能得到一个有序序列,称这个过程为堆排序。再来看看总结一下基本思想:

堆排序

一、概述

首先我们来看看什么叫做堆排序?

若在输出堆顶的最小值之后,使得剩余的n-1个元素的序列重新又构成一个堆,则得到n个元素中的次小值,如此反复,便能得到一个有序序列,称这个过程为堆排序。

再来看看总结一下基本思想:

  1. 将无序序列建成一个堆
  2. 输出堆顶的最小(大)值
  3. 使剩余的n-1个元素又调整成一个堆,则可得到n个元素的次小值
  4. 重复执行,得到一个有序序列

通过上面的规律发现两个问题,而堆 排序 需要解决这两个问题:1.如何建堆? 2.如何调整?

二、如何建堆

1.什么是堆?

n个元素的序列{k1,k2,…,kn},当且仅当满足下列关系时,成为堆:

经典排序之堆排序详解

如果将序列看成一个完全二叉树,非终端结点的值均小于或大于左右子结点的值。

利用树的结构特征来描述堆,所以树只是作为堆的描述工具,堆实际是存放在线形空间中的。

经典排序之堆排序详解

解释: 从上面可以知道,当父节点大于左右孩子节点 或者父节点小于节点的时候,可以称为堆,前者称为大顶堆,后者称为小顶堆。

2.建堆

经典排序之堆排序详解

从第n/2 向下取整 个元素起,至第一个元素止,进行反复筛选,如果我们要建立大顶堆,先比较左右孩子的大小,将比较大的孩子和父节点进行比较。

经典排序之堆排序详解

因为数组的元素一共是7个元素,我们应该从第3个元素,首先我们应该比较第3个元素的左右孩子的大小,然后再进行调整。

经典排序之堆排序详解

代码如下:

Copy

// 建立大顶堆
publicvoidbuildHeap(int[] arr){
for (int i = arr.length /2 -1; i >=0; i--) {
           //从第一个非叶子结点从下至上,从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }
}
/**
     * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
     *
     *@param arr
     *@param i
     *@param length
     */
   publicstaticvoidadjustHeap(int[] arr,int i,int length) {
       int temp = arr[i];//先取出当前元素i
       for (int k = i *2 +1; k < length; k = k *2 +1) {//从i结点的左子结点开始,也就是2i+1处开始
           if (k +1 < length && arr[k] < arr[k +1]) {//如果左子结点小于右子结点,k指向右子结点
                k++;
            }
           if (arr[k] > temp) {//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                arr[i] = arr[k];
                i = k;
            }else {
               break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

   /**
     * 交换元素
     *
     *@param arr
     *@param a
     *@param b
     */
   publicstaticvoidswap(int[] arr,int a,int b) {
       int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

三、如何调整

当我们将数组进行建立大顶堆或者小顶堆的时候,我们就会发现堆顶元素必然是该排序数组的最大或者是最小的那个数据。如何在输出堆顶元素后调整,使之成为新堆?

  1. 输出堆顶元素后,以堆中最后一个元素替代之
  2. 将根结点与左、右子树根结点比较,并与小者交换
  3. 重复直至叶子结点,得到新的堆

解释:

这时候我们将堆顶元素和最后一个元素进行交换,那么我们调整前n-1个元素成堆,反复操作即可

四、算法分析

时间效率:O(nlog2n)  O(nlog2n)

空间效率:O(1) O(1)

稳 定 性:不稳定

适用于n 较大的情况

五、完整代码

Copy

publicclassHeapSort {
   publicstaticvoidmain(String[] args) {
       int[] arr = {9,8,7,6,5,4,3,2,1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

   publicstaticvoidsort(int[] arr) {
       //1.构建大顶堆
       for (int i = arr.length /2 -1; i >=0; i--) {
           //从第一个非叶子结点从下至上,从右至左调整结构
            adjustHeap(arr, i, arr.length);
        }


       //2.调整堆结构+交换堆顶元素与末尾元素
       for (int j = arr.length -1; j >0; j--) {
            swap(arr,0, j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0, j);//重新对堆进行调整
        }

    }

   /**
     * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
     *
     *@param arr
     *@param i
     *@param length
     */
   publicstaticvoidadjustHeap(int[] arr,int i,int length) {
       int temp = arr[i];//先取出当前元素i
       for (int k = i *2 +1; k < length; k = k *2 +1) {//从i结点的左子结点开始,也就是2i+1处开始
           if (k +1 < length && arr[k] < arr[k +1]) {//如果左子结点小于右子结点,k指向右子结点
                k++;
            }
           if (arr[k] > temp) {//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                arr[i] = arr[k];
                i = k;
            }else {
               break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

   /**
     * 交换元素
     *
     *@param arr
     *@param a
     *@param b
     */
   publicstaticvoidswap(int[] arr,int a,int b) {
       int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

Linux公社的RSS地址https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址: https://www.linuxidc.com/Linux/2018-12/155785.htm


以上所述就是小编给大家介绍的《经典排序之堆排序详解》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

如何变得有思想

如何变得有思想

阮一峰 / 人民邮电出版社 / 2014-12-2 / 49.00元

本书为阮一峰博客选集,囊括了作者对各种问题的思考,围绕的主题是试图理解这个世界。本书内容非常广泛,涉及观点、文学、历史、科技、影视等方面。作者在书中对具有深刻意义的文字进行摘录,并且在思索后提出自己独特的观点。书后附有阮一峰诗集。 本书适合喜欢独立思考、热爱读书的读者,对于广大读者具有一定的启发作用。一起来看看 《如何变得有思想》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具