QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 1475|回复: 0
打印 上一主题 下一主题

十大经典排序算法之堆排序(Java语言)

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59
  • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女,毕业于内蒙古科技大学,担任文职专业,毕业专业英语。

    群组2018美赛大象算法课程

    群组2018美赛护航培训课程

    群组2019年 数学中国站长建

    群组2019年数据分析师课程

    群组2018年大象老师国赛优

    跳转到指定楼层
    1#
    发表于 2020-4-23 15:00 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    * w3 S  d" D, z! p5 D+ f( [
    十大经典排序算法之堆排序(Java语言)# {% {, v8 I1 f6 z1 X, I- b
    文章目录. @7 y+ f; n1 P& W* F  s

    9 }4 l  g1 W% {# Y) q- F什么是堆
    ! A  Z9 i; z0 J0 z! X  T如何进行堆排序呢
    ) K) a+ Y5 [; R# F4 F# K用数组构建一个堆
    + p/ a0 j) }, p8 ~, k2 c上代码
    7 U0 k: y, S6 ^什么是堆/ t0 ]7 }- ?8 l( O, h$ g
    2 t' \! j# {8 h5 x5 h' g6 l- O& Y$ N1 O
    在了解什么是堆之前一定要先了解什么是完全二叉树
    : ]0 F+ U1 q! I; n6 n* {看一下百度百科的介绍
    % c+ R  R, b# [  f' _4 ^! F$ _: j0 b9 v& @7 s5 Y5 y3 h' U
    若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。2 p5 C0 x0 e/ ^* N9 _4 @
    百度百科拗口版性质介绍,能看懂上面的就行,下面的大概看下0 z, r7 K7 r6 |5 t9 X
    - u( J, D" z: x9 W5 z
    完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
    ; s- M+ I& n; A0 T* _- a$ a(1)所有的叶结点都出现在第k层或k-l层(层次最大的两层)
    ! B- K% E+ M2 w2 V0 y1 Z7 W(2)对任一结点,如果其右子树的最大层次为L,则其左子树的最大层次为L或L+l。& o' Q( K+ x( y, C5 b1 ~
    一棵二叉树至多只有最下面的两层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,则此二叉树成为完全二叉树,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。
    " q* e% q9 v3 D9 M% L那么在了解到什么是完全二叉树之后,我们再来看什么是堆
    ( w& N& @& w. a) d5 g1 U2 N% t堆有以下两个性质( \2 p% `0 v: d/ m; F$ f( e
    + O; q5 T4 L+ B, R
    1 堆中某个节点的值总是不大于或不小于其父节点的值;
    % ~, F% c9 {; r& M: V2 堆总是一棵完全二叉树。" n5 |' O) r0 A$ n* a3 h0 x( n
    其中堆顶就对应二叉树的根
    5 K$ B9 _( {% [- n( [+ l$ z
    * X/ u; L* T# M: h8 \堆又分为大顶堆和小顶堆,根据堆的第一个性质来进行区分
    9 f' u0 ~' l) {% v( |. m0 s7 z- t/ q  p% G% u& @
    当堆中某个节点的值总是大于它的子节点的时候这个堆为大顶堆,反之为小顶堆
    4 N+ z; a& Y5 _" l! l$ B- o. N如何进行堆排序呢# Q, h; p( Y8 q/ m* n/ c: R

    4 l, C! p  ~' ~$ t, W2 ~堆排序,其实就是每次构造出一个大顶堆或者小顶堆,然后取出堆顶的值,再将剩下的值重新构造成大顶堆或者小顶堆,最终到堆里的值全部取出来,取出来的数就是排好序的
    ! p2 V) |% `* ]  X
    " L5 \. t; @% ?5 k用数组构建一个堆  ^9 A, c4 R2 U6 \
    . [% x# j2 R6 _/ g( A4 C2 J
    因为堆是一颗完全二叉树,所以我们可以用数组来对其进行存储  b/ E3 M/ c, K, W
    对于用数组存储的二叉树,我们可以用如下方法来定义:% D( S+ [# Z2 _) N) a% u
    假设当前节点的下标为 n
    # A' h4 c- Z) D# _5 }- G& s
      l. ?2 f2 H2 l3 q1、那么他的左子节点的下标 2*n + 1, I" a0 l/ }: O0 z$ G' y
    2、那么他的右子节点的下标 2*n + 2
    ; r* q! i% B+ g% b+ f# M5 ^/ L; K3、他左边的节点是 n-1,如果当前节点是第 h 层的最左节点,那么第h-1层的最右节点的下标就是 n-1  j: I5 i' M0 P! i' x; |7 s8 M
    4、根据1、2可以推出来n节点的父节点是 (n-1)/2,不管当前节点是父节点的左子节点还是右子节点,都用 (n-1)/2就行了,因为整型数字相除小数点后面的会被截断
    0 e8 A, R2 M. P- _- i/ p那么有了上面四条性质,我们就可以开始动手了
    8 Q6 E3 K# J3 P( B7 O
    % @+ s, F. M/ J1、假设我们要构建的堆是大顶堆,那么根据大顶堆的性质,任意节点都比它的左右子节点要大,所以我们肯定有个heapify方法,该方法调整指定节点和其子节点的位置,并且继续调整被调整的子节点和孙子节点的关系,直到没有调整或者到数的最底层
    4 }8 v% r7 c; ~" f2、然后我们要有构造大顶堆的方法,构造大顶堆就是从最后一个节点的父节点开始调整,接设最后一个节点的父节点是n,那么我们就将n,n-1,n-2 ··· ··· 0,这些节点逐次,从大到小调用heapify方法,这些节点都调整完成后,大顶堆就构造完成了7 [7 e" _$ A0 D
    3、接下来就开始将堆顶和堆尾互换,并砍断堆尾的操作了,由于互换之前,这是一个符合条件的大顶堆,但是换完只有只有一个堆顶这里不满足了,那么我们重新调整一下堆顶的三个元素就可以,还是调用heapify方法,这个方法会自上而下的重新调整堆,使其成为一个大顶堆3 f/ Q2 X( |7 S; b7 V# o1 C& E) Q

    % c% l* P- U/ R$ d9 m. K堆排序的性质* N, a. e, e# {  Z

    / Q& d+ B- o( a中文名称        英文名称        平均时间复杂度        最坏时间复杂度        最好时间复杂度        空间复杂度        稳定性" T0 F  q& x  N' L5 t" m; T" g% A2 M  V
    堆排序        Heap        n*logn        n*logn        n*logn        1        不稳定
    & _6 k5 ?8 h' S, p4 C/ @, w上代码
    2 D# n7 A2 @0 |. t! N9 ?4 W+ A0 x5 y! e1 }2 j
    /**+ {4 M2 [* ?& t. |
    * 交换第n和m个元素* [% N: N; I- P3 ?/ p& p# S2 u% I
    */4 {( X' M) O, e2 S( w: f. l
    private static void swap(int arr[], int n, int m){3 ]% H- S* B- }# ~/ d& q
        int temp = arr[n];
    ; m7 @! p" E! l+ ~6 \    arr[n] = arr[m];+ A  t8 U5 R, h0 j$ v
        arr[m] = temp;+ b6 \7 V7 P7 |7 R
    }
    ' |! d+ D! @" h% B0 K2 y# o1 P, M2 G( o+ ]# \6 u' F( _
    /**7 |% B# ^% A5 R2 G" @
    * 调整指定节点和其子节点
    + C: M. R: |% y& O3 [ * @param tree 整棵树
    + J, W0 W, }( } * @param n 数组长度,树的元素个数
    $ |  K$ S# i7 ], _0 `! X * @param i 要调整的节点的下标
    , R7 z7 f7 X4 V6 g2 z */
    / x* r6 y0 M; B5 o# p+ Zprivate static void heapIfy(int tree[], int n, int i){4 a$ }6 }: e; y6 Y
        if(i >= n){
    ; u* \" Q/ i! q; C7 v        return;! x  h; d: d, i! {
        }
    # K7 T8 ~! n/ p& w& k) q    int c1 = 2 * i + 1;//左子节点的下标6 Y' w% c3 `. `. l6 P- O
        int c2 = 2 * i + 2;//右子节点的下标
    % h' b9 C7 c) J' b" u) g9 A    int max = i;//假设父节点是最大的
    - d; V/ g3 \. M: D+ K7 K6 l' _) a    //找出最大值的下下标& `" s: A! x9 C$ P- K2 o/ [
        if(c1 < n && tree[c1] > tree[max]){* G& @6 f0 c* ~0 O! J  [. G
            max = c1;4 e5 H5 ?/ ?! p* V7 U# F, l2 F
        }" S1 O3 s; V9 M+ c: r$ c
        if(c2 < n && tree[c2] > tree[max]){. Q* M- I4 Z5 E: x
            max = c2;: Y, }' x( b7 k' z& d* ~
        }
    ! E& l* }: `- _9 p: S    if(max != i){//如果最大值不是父节点,需要做换位置操作
    0 T  L7 Q  w# d" X8 ^# O2 O        swap(tree, max, i);
    2 }( K0 y* u$ P9 c) u% O4 {2 J        //此时,i节点被换成最大值了,符合大顶堆的性质2 J; k( Q7 |$ F4 d
            //但是换到下面的节点不能保证比他的两个子节点都要大
    6 C4 u4 `* T/ S  p        //所以被换位置的节点继续调整
    . y& }( R7 M$ N+ a& [$ Z$ f3 Z: f        heapIfy(tree, n, max);; [1 _8 M8 C& h- P$ t% C" S
        }
    ) G. Y4 l. E" a" h}1 i1 }% m( l1 E7 s
    2 e7 ?/ F( P+ r: w) r. m
    /**
    . r! K0 N9 \8 L% C * 完整构建大顶堆' z* r' g; i  ^$ ?* v2 z
    * @param arr 用于构建堆的数组
    5 k9 ]; I. C" q5 Q; y* V * @param n 堆的最后一个节点的下标3 a$ P! Z8 D  M, `) t
    */5 z$ _( M4 D% R, g3 B( ]
    private static void buildHeap(int arr[],int n){
    4 o2 v/ k% ]: {, n& F    int lastNode = n - 1;. {) t# }1 k6 ]6 L% v
        int parent = (lastNode - 1) / 2;* D7 E/ M. b0 _* C) \5 w
        for (int i = parent; i >= 0; i--){
    % q+ B- R& `! c  ]7 R% T# j  D        heapIfy(arr, n, i);
    , a+ b3 q8 J; F5 q8 @) [. n% \9 B    }5 |7 s* I' B, u9 z6 Y' T' }4 L
    }
    ! Y5 k3 f0 S. R- x7 C0 R/ ]" b* A9 l7 p7 C( x
    /**
    # z# v2 |7 L; \( q7 x  f7 m+ ?5 U6 y * 堆排序
    $ j2 [& j; d! [" M& ~; M9 ^ * @param arr 待排数组
    , e5 V9 }+ i( \8 j */
    3 ]4 O6 [$ n/ H4 V2 D  L9 upublic static void sort(int arr[]){' M1 F8 N  N, _  J7 @
        buildHeap(arr, arr.length);//先构造大顶堆
    + v9 g" ~* Z& A# T7 S( Y    //每次构建堆后将根节点和最后一个节点进行交换2 v7 G0 M+ ~  p4 L
        //然后砍断最后一个节点
    2 r: C: ~3 b# D; K/ O8 r9 }) A- j    //所以从最后一个节点向前循环& n" l! ^4 H5 h' k& g; M. a
        for (int i = arr.length - 1; i > 0; i--){
    ( {6 D1 L8 p. _# [        swap(arr, 0, i);8 k8 w+ }+ d7 z$ d2 j5 T
            heapIfy(arr, i, 0);# t2 X- e& Z6 E% B+ R
        }# N1 a5 Q0 r/ Q9 g' \
    }' a, p4 _" {" p# e' P$ i/ H! o
    ————————————————
    ' K3 {& l) u* B9 d- Q- h版权声明:本文为CSDN博主「qq_34912889」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    $ p# s* w: w( j  W# {原文链接:https://blog.csdn.net/qq_34912889/article/details/105690644
    * A7 m3 Y, I9 |5 k7 Z. V9 o) v' S- K9 {1 J) M: ^# b2 s

    : t4 r0 B- i- g/ K" i! P# O
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-6-9 23:06 , Processed in 0.347761 second(s), 51 queries .

    回顶部