堆排序有两个重要的步骤：初始化堆和依次交换（树根和最后一个），然而这两步都涉及堆的调整。以大根堆为例 |
|
i |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
a[i] |
0 |
16 |
20 |
3 |
11 |
17 |
8 |
4 |
9 |
32 |
65 |
23 |
<br>从a[1]开始可以保证，结点a[n]的父结点为a[n/2]，子结点为a[2*n]和a[2*n+1];<br><br>初始化的堆如下： |
要从最后一个非叶子结点开始调整：即从17开始，在17，65，23中选择最大的并交换 |
排序时，每次都是树根a[1]与最后一个叶子结点20交换，之后调整a[1] |
65已经排好，接下来a[1]要与17交换，并调整a[1]
<br><br><br><br><br><br><br><br><br><br>#include <iostream>#include <iomanip>using
namespace std;void
adjust(int* a,int
n,int size) /<span style="color: rgb(0, 0, 0);">/n--要调整的元素下标，size--最后一个元素下标</span>{ int
last=size/2; while(n<=last) //调整到最后一个非叶子结点<br>{ int
max=a[n],maxn=n; if(<span style="color: rgb(255, 0, 0);">2*n<=size</span> && a[2*n]>max) { max=a[2*n]; maxn=2*n; //left child } if(<span style="color: rgb(255, 0, 0);">2*n+1<=size</span> && a[2*n+1]>max) //<span style="color: rgb(0, 0, 0);">不能超过size</span> { max=a[2*n+1]; maxn=2*n+1; } if(maxn^n) // { max=a[n]; a[n]=a[maxn]; a[maxn]=max; n=maxn; //next loop } else break; }}void
buildheap(int* a,int
size){ int
i=size/2; //from the last not leaf while(i>0) { adjust(a,i,size); i--; }}void
sort(int* a,int
size){ int
temp; int
n=size; while(n>1) { temp=a[1]; a[1]=a[n]; a[n]=temp; adjust(a,1,n-1); n--; }}int
main(int
argc, char* argv[]){ int
a[16]={0,16,20,3,11,17,8,4,9,32,65,23}; int
size=11; //number of the last buildheap(a,size); for(int
i=1;i<=size;i++) cout<<setw(4)<<a[i]; cout<<endl; sort(a,size); for(i=1;i<=size;i++) cout<<setw(4)<<a[i]; cout<<endl; return
0;} |
堆排序还是比较好理解的，要自己动手画出排序过程，再亲自写下，就会掌握的，祝大家好运！
原文：http://www.cnblogs.com/mm220284/p/3601316.html