说白了,也就是大堆,或者小堆,通过删掉堆顶点,然后存入数组,来实现排序:
第一阶段:构建堆最多用2N次比较
第二阶段:第i次deleteMax最多用到2【logi】次比较,
总数最多2NlogN-O(N)次比较
代码:
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4 template <typename Comparable>
5 void heapsort(vector<Comparable> & a)
6 {
7 for(int i = a.size()/2; i>= 0 ;i--)
8 percDown(a,i,a.size());
9 for(int j=a.size()-1; j>0 ; j--)
10 {
11 swap(a[0],a[j]);
12 percDown(a,0,j);
13 }
14 }
15 inline int leftChild(int i )
16 {
17 return 2*i;
18 }
19 template <typename Comparable>
20 void percDown(vector<Comparable> & a,int i,int n)
21 {
22 int child;
23 Comparable tmp;
24
25 for(tmp = a[i] ; leftChild(i)<n ; i=child)
26 {
27 child = leftChild(i);
28 if(child != n-1 && a[child] < a[child+1])
29 child++;
30 if(tmp<a[child])
31 a[i]=a[child];
32 else
33 break;
34 }
35 a[i]=tmp;
36 }
37 int main()
38 {
39 vector<int> ivec;
40 ivec.push_back(1);
41 ivec.push_back(9);
42 ivec.push_back(2);
43 ivec.push_back(10);
44 ivec.push_back(3);
45 ivec.push_back(11);
46 ivec.push_back(4);
47 ivec.push_back(12);
48 ivec.push_back(5);
49 ivec.push_back(13);
50 ivec.push_back(6);
51 ivec.push_back(14);
52 ivec.push_back(7);
53 ivec.push_back(15);
54 ivec.push_back(8);
55 ivec.push_back(16);
56 heapsort(ivec);
57 for(int i =0;i<ivec.size();i++)
58 cout<<ivec[i]<<endl;
59 return 0;
60 }
结果如下: