- 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 下午 板凳
☺☝☝☝