📄 heapsort.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>Heap 排序法 - 改良的选择排序</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: Heap 排序法 - 改良的选择排序</a></h1>
<h2>说明</h2>
选择排序法的概念简单，每次从未排序部份选一最小值，插入已排序部份的后端，其时间主要花费于在整个未排序部份寻找最小值，如果能让搜寻最小值的方式加
快，选择排序法的速率也就可以加快，Heap排序法让搜寻的路径由树根至最后一个树叶，而不是整个未排序部份，因而称之为改良的选择排序法。<br>
<h2>解法</h2>
Heap排序法使用Heap
Tree（堆积树），树是一种资料结构，而堆积树是一个二元树，也就是每一个父节点最多只有两个子节点（关于树的详细定义还请见资料结构书籍），堆积树的
父节点若小于子节点，则称之为最小堆积（Min Heap），父节点若大于子节点，则称之为最大堆积（Max
Heap），而同一层的子节点则无需理会其大小关系，例如下面就是一个堆积树： <br>
<div style="text-align: center;"><img style="width: 284px; height: 152px;" alt="Heap 排序" title="Heap 排序" src="images/heapSort-1.jpg"></div>
<br>
可以使用一维阵列来储存堆积树的所有元素与其顺序，为了计算方便，使用的起始索引是1而不是0，索引1是树根位置，如果左子节点储存在阵列中的索引为s，则其父节点的索引为s/2，而右子节点为s+1，就如上图所示，将上图的堆积树转换为一维阵列之后如下所示： <br>
<div style="text-align: center;"><img style="width: 286px; height: 55px;" alt="Heap 排序" title="Heap 排序" src="images/heapSort-2.jpg"></div>
<br>
首先必须知道如何建立堆积树，加至堆积树的元素会先放置在最后一个树叶节点位置，然后检查父节点是否小于子节点（最小堆积），将小的元素不断与父节点交换，直到满足堆积树的条件为止，例如在上图的堆积加入一个元素12，则堆积树的调整方式如下所示：<br>
<div style="text-align: center;"><img style="width: 574px; height: 154px;" alt="Heap 排序" title="Heap 排序" src="images/heapSort-3.jpg"></div>
<br>
建立好堆积树之后，树根一定是所有元素的最小值，您的目的就是：<br>
<ol>
<li>将最小值取出</li>
<li>然后调整树为堆积树</li>
</ol>
<br>
不断重复以上的步骤，就可以达到排序的效果，最小值的取出方式是将树根与最后一个树叶节点交换，然后切下树叶节点，重新调整树为堆积树，如下所示： <br>
<div style="text-align: center;"><img style="width: 591px; height: 199px;" alt="Heap 排序" title="Heap 排序" src="images/heapSort-4.jpg"></div>
<br>
调整完毕后，树根节点又是最小值了，于是我们可以重覆这个步骤，再取出最小值，并调整树为堆积树，如下所示：<br>
<div style="text-align: center;"><img style="width: 564px; height: 197px;" alt="Heap 排序" title="Heap 排序" src="images/heapSort-5.jpg"></div>
<br>
如此重覆步骤之后，由于使用一维阵列来储存堆积树，每一次将树叶与树根交换的动作就是将最小值放至后端的阵列，所以最后阵列就是变为已排序的状态。
<br>
<br>
其实堆积在调整的过程中，就是一个选择的行为，每次将最小值选至树根，而选择的路径并不是所有的元素，而是由树根至树叶的路径，因而可以加快选择的过程，
所以Heap排序法才会被称之为改良的选择排序法。 <br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br>#include <time.h> <br>#define MAX 10 <br>#define SWAP(x,y) {int t; t = x; x = y; y = t;} <br><br>void createheap(int[]); <br>void heapsort(int[]); <br><br>int main(void) { <br> int number[MAX+1] = {-1}; <br> int i, num; <br><br> srand(time(NULL)); <br><br> printf("排序前："); <br> for(i = 1; i <= MAX; i++) { <br> number[i] = rand() % 100; <br> printf("%d ", number[i]); <br> } <br><br> printf("\n建立堆积树："); <br> createheap(number); <br> for(i = 1; i <= MAX; i++) <br> printf("%d ", number[i]); <br> printf("\n"); <br><br> heapsort(number); <br><br> printf("\n"); <br><br> return 0; <br>} <br><br>void createheap(int number[]) { <br> int i, s, p; <br> int heap[MAX+1] = {-1}; <br><br> for(i = 1; i <= MAX; i++) { <br> heap[i] = number[i]; <br> s = i; <br> p = i / 2; <br> while(s >= 2 && heap[p] > heap[s]) { <br> SWAP(heap[p], heap[s]); <br> s = p; <br> p = s / 2; <br> } <br> } <br><br> for(i = 1; i <= MAX; i++) <br> number[i] = heap[i]; <br> <br>} <br><br>void heapsort(int number[]) { <br> int i, m, p, s; <br><br> m = MAX; <br> while(m > 1) { <br> SWAP(number[1], number[m]); <br> m--; <br><br> p = 1; <br> s = 2 * p; <br><br> while(s <= m) { <br> if(s < m && number[s+1] < number[s]) <br> s++; <br> if(number[p] <= number[s]) <br> break; <br> SWAP(number[p], number[s]); <br> p = s; <br> s = 2 * p; <br> } <br><br> printf("\n排序中："); <br> for(i = MAX; i > 0; i--) <br> printf("%d ", number[i]); <br> } <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class HeapSort {<br> public static void sort(int[] number) {<br> int[] tmp = new int[number.length + 1];<br> <br> // 配合说明，使用一个有遍移的暂存阵列<br> for(int i = 1; i < tmp.length; i++) {<br> tmp[i] = number[i-1]; <br> }<br> <br> createHeap(tmp);<br> <br> int m = number.length; <br> while(m > 1) { <br> swap(tmp, 1, m); <br> m--; <br><br> int p = 1; <br> int s = 2 * p; <br><br> while(s <= m) { <br> if(s < m && tmp[s+1] < tmp[s]) <br> s++; <br> if(tmp[p] <= tmp[s]) <br> break; <br> swap(tmp, p, s); <br> p = s; <br> s = 2 * p; <br> } <br> } <br> <br> // 这边将排序好的暂存阵列设定回原阵列<br> for(int i = 0; i < number.length; i++) {<br> number[i] = tmp[i+1]; <br> }<br> }<br> <br> private static void createHeap(int[] tmp) { <br> int[] heap = new int[tmp.length];<br> <br> for(int i = 0; i < heap.length; i++)<br> heap[i] = -1;<br><br> for(int i = 1; i < heap.length; i++) { <br> heap[i] = tmp[i]; <br> int s = i; <br> int p = i / 2; <br> while(s >= 2 && heap[p] > heap[s]) { <br> swap(heap, p, s); <br> s = p; <br> p = s / 2; <br> } <br> } <br><br> for(int i = 1; i < tmp.length; i++) <br> tmp[i] = heap[i]; <br> <br> } <br> <br> private static void swap(int[] number, int i, int j) {<br> int t; <br> t = number[i]; <br> number[i] = number[j]; <br> number[j] = t;<br> }<br>} </pre>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -