- A+
之前写了十大经典排序算法的桶排序，现在，我们再来看看堆排序以及其Java代码的实现...
原理
既然是堆排序，肯定是涉及到数据结果中的堆，堆排序是利用堆来实现排序；其排序既用到完全二叉树的特性，又用到了堆父节点大于子节点的特性。
先将所有数据当成一颗完全二叉树，然后使得所有的父节点都大于子节点（满足堆的特性），然后将完全二叉树最后一个叶子节点与根节点交换（此时最后一个节点属于有序的，我们暂称其存在于有序区，而其他节点存在无序区），此时数据不再满足堆的特性，因此再继续调整，让所有父节点大于子节点，再替换最后一个叶子节点与根节点（此时有序区存在两个节点），依此循环，直至所有节点都加入有序区，则排序完成。
示意图
发现自己上面表达得有点太啰嗦了，却又不知道怎么去更改，暂且自认为已经表达了意思吧。
我们再来看看其示意图（画图太麻烦，只好百度之，注：下图来自网络）
堆排序
java代码
堆排序算法java实现代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 |
public class BucketSort implements IArraySort { <span class="hljs-comment"> //声明全局变量，用于记录数组array的长度；</span> <span class="hljs-keyword"> static</span> <span class="hljs-keyword">int</span> len; <span class="hljs-comment">/** * 堆排序算法 * * @param array * @return */</span> <span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">int</span>[] HeapSort(<span class="hljs-keyword">int</span>[] <span class="hljs-built_in">array</span>) { len = <span class="hljs-built_in">array</span>.length; <span class="hljs-keyword">if</span> (len < <span class="hljs-number">1</span>) <span class="hljs-keyword">return</span> <span class="hljs-built_in">array</span>; <span class="hljs-comment">//1.构建一个最大堆</span> buildMaxHeap(<span class="hljs-built_in">array</span>); <span class="hljs-comment">//2.循环将堆首位（最大值）与末位交换，然后在重新调整最大堆</span> <span class="hljs-keyword">while</span> (len > <span class="hljs-number">0</span>) { swap(<span class="hljs-built_in">array</span>, <span class="hljs-number">0</span>, len - <span class="hljs-number">1</span>); len--; adjustHeap(<span class="hljs-built_in">array</span>, <span class="hljs-number">0</span>); } <span class="hljs-keyword">return</span> <span class="hljs-built_in">array</span>; } <span class="hljs-comment">/** * 建立最大堆 * * @param array */</span> <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">buildMaxHeap</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] <span class="hljs-built_in">array</span>)</span> </span>{ <span class="hljs-comment">//从最后一个非叶子节点开始向上构造最大堆</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = (len/<span class="hljs-number">2</span> - <span class="hljs-number">1</span>); i >= <span class="hljs-number">0</span>; i--) { adjustHeap(<span class="hljs-built_in">array</span>, i); } } <span class="hljs-comment">/** * 调整使之成为最大堆 * * @param array * @param i */</span> <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">adjustHeap</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] <span class="hljs-built_in">array</span>, <span class="hljs-keyword">int</span> i)</span> </span>{ <span class="hljs-keyword">int</span> maxIndex = i; <span class="hljs-comment">//如果有左子树，且左子树大于父节点，则将最大指针指向左子树</span> <span class="hljs-keyword">if</span> (i * <span class="hljs-number">2</span> < len && <span class="hljs-built_in">array</span>[i * <span class="hljs-number">2</span>] > <span class="hljs-built_in">array</span>[maxIndex]) maxIndex = i * <span class="hljs-number">2</span>; <span class="hljs-comment">//如果有右子树，且右子树大于父节点，则将最大指针指向右子树</span> <span class="hljs-keyword">if</span> (i * <span class="hljs-number">2</span> + <span class="hljs-number">1</span> < len && <span class="hljs-built_in">array</span>[i * <span class="hljs-number">2</span> + <span class="hljs-number">1</span>] > <span class="hljs-built_in">array</span>[maxIndex]) maxIndex = i * <span class="hljs-number">2</span> + <span class="hljs-number">1</span>; <span class="hljs-comment">//如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。</span> <span class="hljs-keyword">if</span> (maxIndex != i) { swap(<span class="hljs-built_in">array</span>, maxIndex, i); adjustHeap(<span class="hljs-built_in">array</span>, maxIndex); } } <span class="hljs-comment">/** * 交换数组内两个元素 * @param array * @param i * @param j */</span> <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">swap</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] <span class="hljs-built_in">array</span>, <span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> j)</span> </span>{ <span class="hljs-keyword">int</span> temp = <span class="hljs-built_in">array</span>[i]; <span class="hljs-built_in">array</span>[i] = <span class="hljs-built_in">array</span>[j]; <span class="hljs-built_in">array</span>[j] = temp; } } |
复杂度
由上面可以看出，堆排序时间复杂度为T(n) = O(nlogn)
原文博客：IT老五（【十大经典排序算法】堆排序及其JAVA代码实现）
IT老五（it-lao5）：关注公众号，一起源创，一起学习！
我的微信公众号
微信扫一扫关注公众号，不定时更新
2019-08-23 11:01 下午 沙发
2019-08-23 10:16 下午 板凳
☺☝☝☝