堆排序顺序存储（升序）
一： 完全二叉树的概念：前h-1层为满二叉树，最后一层连续缺失右结点！
二：首先堆是一棵全完二叉树：
a:构建一个堆分为两步：⑴创建一棵完全二叉树 ⑵调整为一个堆
（标注：大根堆为升序，小根堆为降序）
b:算法描述：①创建一棵完全二叉树
②while(有双亲){
A:调整为大根堆；
B:交换根和叶子结点；
C:砍掉叶子结点；
}
c:时间复杂度为 O(nlogn) ,空间复杂度为 O(1), 是不稳定排序！
代码实现：
|
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
67
68
69
70
|
/*堆排序思想:[完全二叉树的定义:前 h-1 层为满二叉树一最后一层连续缺失右结点(即右子女)]，(大根堆升序排序，小根堆降序排列) 首先堆是一个完全二叉树 ，根据数组下标就可建成了一棵完全二叉树 其次:while(有双亲){ A: 调整为一个大根堆 【Adjust()函数实现】 B: 交换最后一个叶子结点和根结点 【Swap()函数实现】 C: 砍掉最后一个叶子结点 【即元素个数 n--】 } */ #include <iostream> #define N 100 using namespace std; int b[N]={0}; //存储数据的数组 int n=0; //记录数据的总个数【0单元不要,实际元素个数为(n-1)个】 void Swap(int *x,int *y){ int t; t=*x; *x=*y; *y=t; } void Adjust(){ int p; //记录双亲结点 int tag=1; //记录是否已经调整为大根堆(标志性的变量) while(tag){ //判断是否已经调整好为大根堆 p=(n-1)/2; //最后一个双亲结点的下标 tag=0; //凡是交换后，tag=1,标志着还没有调整为大根堆，否则继续调整 while(p>0){ //确保有双亲结点 if(b[p]<b[2*p]){ //若根结点大于左子女结点，就交换 Swap(&b[p],&b[2*p]); tag=1; } if(2*p+1<n && b[p]<b[2*p+1]){ //若存在右子女，并且根结点大于右子女结点，就交换 Swap(&b[p],&b[2*p+1]); tag=1; } p--; //直到最后一个双亲结点调整完 } } } void HeapSort(){ while(n>2){ //保证有双亲结点 Adjust(); //调整大根堆函数 Swap(&b[1],&b[n-1]); //将最后一个叶子结点和根结点交换 n--; //裁剪最后的叶子结点 } } int main(void){ int i,m; cout<<"请输入数据的总数【0单元不要,实际元素个数为(n-1)个】:"<<endl; cin>>n; m=n; cout<<"请输入各个数据【0单元不要,实际元素个数为(n-1)个】:"<<endl; b[0]=0; for(i=1;i<n;i++){ cin>>b[i]; } HeapSort(); //堆排序 cout<<"大根堆升序排列为:"<<endl; for(i=1;i<m;i++){ cout<<b[i]<<" "; } cout<<endl; return 0; } |
感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！
原文链接：http://blog.csdn.net/super_yc/article/details/52964080
