虹口专业网站建设公司,镇江制作网站的,劳务公司网站建设方案,静安青岛网站建设1. 堆排序简介
堆排序（heapsort）是由 J. W. J. Williams 于 1964 年发明的。是一种基于比较的排序算法，和选择排序一样，堆排序将数据序列分为已排序区域和未排序区域两部分。通过从未排列区域中获取最大元素并将其插入已排序区域，迭代这个操作来缩小未排序区域。与选择排…1. 堆排序简介
堆排序（heapsort）是由 J. W. J. Williams 于 1964 年发明的。是一种基于比较的排序算法，和选择排序一样，堆排序将数据序列分为已排序区域和未排序区域两部分。通过从未排列区域中获取最大元素并将其插入已排序区域，迭代这个操作来缩小未排序区域。与选择排序不同的是，堆排序不会对未排序区域进行线性扫描，而是通过维护堆中未排序区域的数据结构以到达高效获取最大元素的目的。堆排序的平均时间复杂度为 O ( n log n ) O{\left(n\log n\right)} O(nlogn)，空间复杂度为 O ( 1 ) O{\left(1\right)} O(1)（原地算法）。
2. 原理
将数组转化为最大堆（Max-Heap），根结点的键值是所有堆结点键值中最大者的二叉树。 Array [ p a r e n t ( i ) ] ≥ Array [ i ] {\text{Array}}{\left[parent{\left(i\right)} \right]}\ge{\text{Array}}{\left[i\right]} Array[parent(i)]≥Array[i] 接着重复取出最大堆中的最大值（即根节点值）插入已排序区域，并维护残余堆的最大堆特性就可完成排序。
3. 步骤
建立最大堆取出最大值（即根节点），并维护残余堆。递归步骤2，完成排序#mermaid-svg-9fmsAbRQ2yyjJj5F {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-9fmsAbRQ2yyjJj5F .error-icon{fill:#552222;}#mermaid-svg-9fmsAbRQ2yyjJj5F .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-9fmsAbRQ2yyjJj5F .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-9fmsAbRQ2yyjJj5F .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-9fmsAbRQ2yyjJj5F .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-9fmsAbRQ2yyjJj5F .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-9fmsAbRQ2yyjJj5F .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-9fmsAbRQ2yyjJj5F .marker{fill:#333333;stroke:#333333;}#mermaid-svg-9fmsAbRQ2yyjJj5F .marker.cross{stroke:#333333;}#mermaid-svg-9fmsAbRQ2yyjJj5F svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-9fmsAbRQ2yyjJj5F .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-9fmsAbRQ2yyjJj5F .cluster-label text{fill:#333;}#mermaid-svg-9fmsAbRQ2yyjJj5F .cluster-label span{color:#333;}#mermaid-svg-9fmsAbRQ2yyjJj5F .label text,#mermaid-svg-9fmsAbRQ2yyjJj5F span{fill:#333;color:#333;}#mermaid-svg-9fmsAbRQ2yyjJj5F .node rect,#mermaid-svg-9fmsAbRQ2yyjJj5F .node circle,#mermaid-svg-9fmsAbRQ2yyjJj5F .node ellipse,#mermaid-svg-9fmsAbRQ2yyjJj5F .node polygon,#mermaid-svg-9fmsAbRQ2yyjJj5F .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-9fmsAbRQ2yyjJj5F .node .label{text-align:center;}#mermaid-svg-9fmsAbRQ2yyjJj5F .node.clickable{cursor:pointer;}#mermaid-svg-9fmsAbRQ2yyjJj5F .arrowheadPath{fill:#333333;}#mermaid-svg-9fmsAbRQ2yyjJj5F .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-9fmsAbRQ2yyjJj5F .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-9fmsAbRQ2yyjJj5F .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-9fmsAbRQ2yyjJj5F .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-9fmsAbRQ2yyjJj5F .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-9fmsAbRQ2yyjJj5F .cluster text{fill:#333;}#mermaid-svg-9fmsAbRQ2yyjJj5F .cluster span{color:#333;}#mermaid-svg-9fmsAbRQ2yyjJj5F div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-9fmsAbRQ2yyjJj5F :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} Yes No 开始 建立最大堆 获取根值? 维护残余堆 结束 3.1 数组索引和堆节点位置的关系
数组如下：
0123456782634438547153626可以看成 #mermaid-svg-EfYpzYb9BTMxkrXu {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-EfYpzYb9BTMxkrXu .error-icon{fill:#552222;}#mermaid-svg-EfYpzYb9BTMxkrXu .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-EfYpzYb9BTMxkrXu .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-EfYpzYb9BTMxkrXu .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-EfYpzYb9BTMxkrXu .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-EfYpzYb9BTMxkrXu .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-EfYpzYb9BTMxkrXu .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-EfYpzYb9BTMxkrXu .marker{fill:#333333;stroke:#333333;}#mermaid-svg-EfYpzYb9BTMxkrXu .marker.cross{stroke:#333333;}#mermaid-svg-EfYpzYb9BTMxkrXu svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-EfYpzYb9BTMxkrXu .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-EfYpzYb9BTMxkrXu .cluster-label text{fill:#333;}#mermaid-svg-EfYpzYb9BTMxkrXu .cluster-label span{color:#333;}#mermaid-svg-EfYpzYb9BTMxkrXu .label text,#mermaid-svg-EfYpzYb9BTMxkrXu span{fill:#333;color:#333;}#mermaid-svg-EfYpzYb9BTMxkrXu .node rect,#mermaid-svg-EfYpzYb9BTMxkrXu .node circle,#mermaid-svg-EfYpzYb9BTMxkrXu .node ellipse,#mermaid-svg-EfYpzYb9BTMxkrXu .node polygon,#mermaid-svg-EfYpzYb9BTMxkrXu .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-EfYpzYb9BTMxkrXu .node .label{text-align:center;}#mermaid-svg-EfYpzYb9BTMxkrXu .node.clickable{cursor:pointer;}#mermaid-svg-EfYpzYb9BTMxkrXu .arrowheadPath{fill:#333333;}#mermaid-svg-EfYpzYb9BTMxkrXu .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-EfYpzYb9BTMxkrXu .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-EfYpzYb9BTMxkrXu .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-EfYpzYb9BTMxkrXu .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-EfYpzYb9BTMxkrXu .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-EfYpzYb9BTMxkrXu .cluster text{fill:#333;}#mermaid-svg-EfYpzYb9BTMxkrXu .cluster span{color:#333;}#mermaid-svg-EfYpzYb9BTMxkrXu div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-EfYpzYb9BTMxkrXu :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} [0]=26 [1]=3 [2]=44 [3]=38 [4]=5 [5]=47 [6]=15 [7]=36 [8]=26 由此上可以看出：
数组 [ i ] {\left[i\right]} [i]的左子节点的位置为 2 × i + 1 2\times i+1 2×i+1。数组 [ i ] {\left[i\right]} [i]的右子节点的位置为 2 × i + 2 2\times i+2 2×i+2。数组 [ i ] {\left[i\right]} [i]的父节点的位置为 i i i为偶数则父节点位置为 i − 2 2 \frac{i-2}{2} 2i−2 i i i为基数则父节点位置为 i − 1 2 \frac{i-1}{2} 2i−1可以简化为数组 [ i ] {\left[i\right]} [i]的父节点位置为 ⌊ i − 1 2 ⌋ \lfloor \frac{i-1}{2}\rfloor ⌊2i−1⌋ 3.2 建立最大堆
从数组后面向前扫描并调整堆满足最大堆的特性： #mermaid-svg-fTIzgHvd0hfSrhR2 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-fTIzgHvd0hfSrhR2 .error-icon{fill:#552222;}#mermaid-svg-fTIzgHvd0hfSrhR2 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-fTIzgHvd0hfSrhR2 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-fTIzgHvd0hfSrhR2 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-fTIzgHvd0hfSrhR2 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-fTIzgHvd0hfSrhR2 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-fTIzgHvd0hfSrhR2 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-fTIzgHvd0hfSrhR2 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-fTIzgHvd0hfSrhR2 .marker.cross{stroke:#333333;}#mermaid-svg-fTIzgHvd0hfSrhR2 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-fTIzgHvd0hfSrhR2 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-fTIzgHvd0hfSrhR2 .cluster-label text{fill:#333;}#mermaid-svg-fTIzgHvd0hfSrhR2 .cluster-label span{color:#333;}#mermaid-svg-fTIzgHvd0hfSrhR2 .label text,#mermaid-svg-fTIzgHvd0hfSrhR2 span{fill:#333;color:#333;}#mermaid-svg-fTIzgHvd0hfSrhR2 .node rect,#mermaid-svg-fTIzgHvd0hfSrhR2 .node circle,#mermaid-svg-fTIzgHvd0hfSrhR2 .node ellipse,#mermaid-svg-fTIzgHvd0hfSrhR2 .node polygon,#mermaid-svg-fTIzgHvd0hfSrhR2 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-fTIzgHvd0hfSrhR2 .node .label{text-align:center;}#mermaid-svg-fTIzgHvd0hfSrhR2 .node.clickable{cursor:pointer;}#mermaid-svg-fTIzgHvd0hfSrhR2 .arrowheadPath{fill:#333333;}#mermaid-svg-fTIzgHvd0hfSrhR2 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-fTIzgHvd0hfSrhR2 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-fTIzgHvd0hfSrhR2 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-fTIzgHvd0hfSrhR2 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-fTIzgHvd0hfSrhR2 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-fTIzgHvd0hfSrhR2 .cluster text{fill:#333;}#mermaid-svg-fTIzgHvd0hfSrhR2 .cluster span{color:#333;}#mermaid-svg-fTIzgHvd0hfSrhR2 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-fTIzgHvd0hfSrhR2 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}#mermaid-svg-fTIzgHvd0hfSrhR2 .focus*{stroke:#f66!important;stroke-width:3px!important;}#mermaid-svg-fTIzgHvd0hfSrhR2 .focus span{stroke:#f66!important;stroke-width:3px!important;} [0]=26 [1]=3 [2]=44 [3]=38 [4]=5 [5]=47 [6]=15 [7]=36 [8]=26 数组中[7]=36 和 [8]=26 都满足小于父节点 [3]=38；继续向前扫描得 [6]=15 也满足小于父节点 [2]=44；继续： #mermaid-svg-nYt4abyz0KPeedGa {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-nYt4abyz0KPeedGa .error-icon{fill:#552222;}#mermaid-svg-nYt4abyz0KPeedGa .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-nYt4abyz0KPeedGa .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-nYt4abyz0KPeedGa .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-nYt4abyz0KPeedGa .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-nYt4abyz0KPeedGa .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-nYt4abyz0KPeedGa .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-nYt4abyz0KPeedGa .marker{fill:#333333;stroke:#333333;}#mermaid-svg-nYt4abyz0KPeedGa .marker.cross{stroke:#333333;}#mermaid-svg-nYt4abyz0KPeedGa svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-nYt4abyz0KPeedGa .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-nYt4abyz0KPeedGa .cluster-label text{fill:#333;}#mermaid-svg-nYt4abyz0KPeedGa .cluster-label span{color:#333;}#mermaid-svg-nYt4abyz0KPeedGa .label text,#mermaid-svg-nYt4abyz0KPeedGa span{fill:#333;color:#333;}#mermaid-svg-nYt4abyz0KPeedGa .node rect,#mermaid-svg-nYt4abyz0KPeedGa .node circle,#mermaid-svg-nYt4abyz0KPeedGa .node ellipse,#mermaid-svg-nYt4abyz0KPeedGa .node polygon,#mermaid-svg-nYt4abyz0KPeedGa .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-nYt4abyz0KPeedGa .node .label{text-align:center;}#mermaid-svg-nYt4abyz0KPeedGa .node.clickable{cursor:pointer;}#mermaid-svg-nYt4abyz0KPeedGa .arrowheadPath{fill:#333333;}#mermaid-svg-nYt4abyz0KPeedGa .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-nYt4abyz0KPeedGa .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-nYt4abyz0KPeedGa .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-nYt4abyz0KPeedGa .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-nYt4abyz0KPeedGa .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-nYt4abyz0KPeedGa .cluster text{fill:#333;}#mermaid-svg-nYt4abyz0KPeedGa .cluster span{color:#333;}#mermaid-svg-nYt4abyz0KPeedGa div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-nYt4abyz0KPeedGa :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}#mermaid-svg-nYt4abyz0KPeedGa .focus*{stroke:#f66!important;stroke-width:3px!important;fill:#f77!important;color:#fff!important;}#mermaid-svg-nYt4abyz0KPeedGa .focus span{stroke:#f66!important;stroke-width:3px!important;fill:#f77!important;color:#fff!important;}
