《数据结构与算法分析：C语言描述》复习——第六章“排序”—

2014.06.17 03:29

简介：

　　堆排序，是从这本教材上看，最好的排序算法。它是稳定排序，时间复杂度稳定保持在O(n * log(n))，空间复杂度为O(1)。原理非常简单，实现也比较简单。但是，应用却不如快速排序和归并排序那么广。原因咱们下面说说。

描述：

　　如果你要把数组排成升序，你可以依次把最小的元素放前面，或把最大的元素往后放。我们在第五章学习了堆，知道可以用数组来表示一个堆。那么我们就通过建堆算法，把这个数组变成一个大顶堆，堆顶元素最大。每次从这个堆拿出堆顶放在数组的后面，放了n - 1次以后，整个数组就排好序了。

　　那堆排序有什么不如快速排序的呢？应该是输在常系数上了，从代码里可以看到堆排序在随机访问元素的时候，下标的变化很大。如果你还考虑了内存里数据寻址的耗时，那么快速排序、归并排序要访问的内存总是离得更近（人家用的是++和--），这样就不会像堆排序那样到处寻址了。不过，这个理由也没有很大的说服力。因为你自己手写一个快速排序和堆排序进行比较，很有可能堆排序会胜出。而目前最优秀的排序算法sort君，其内涵是非常丰富的，绝不是简单的快速排序。纠结于这些算法到底谁最好，不如取长补短。在找工作时，堆排序确实有个实实在在的好处，当你写不出快排的时候，堆排序就容易多了。因为——不论快速排序还是快速选择，都是既不好分析又容易写错的算法。如果sort不让用，还是堆排序吧；万一堆排序也忘了，就归并了吧；如果归并也忘了，你就回家等通知吧。

实现：

 1 // My implementation for selection sort.
 2 #include <iostream>
 3 #include <vector>
 4 using namespace std;
 5 
 6 static inline int leftChild(int n)
 7 {
 8     return n * 2 + 1;
 9 }
10 
11 static inline int rightChild(int n)
12 {
13     return n * 2 + 2;
14 }
15 
16 static inline void swap(int &x, int &y)
17 {
18     int tmp;
19     
20     tmp = x;
21     x = y;
22     y = tmp;
23 }
24 
25 static inline int max(const int &x, const int &y)
26 {
27     return x > y ? x : y;
28 }
29 
30 static void percolateDown(vector<int> &v, int i, int n)
31 {
32     if (n <= 1 || i < 0 || i >= n) {
33         return;
34     }
35     int max_val;
36 
37     while (leftChild(i) < n) {
38         if (leftChild(i) == n - 1) {
39             max_val = v[leftChild(i)];
40         } else {
41             max_val = max(v[leftChild(i)], v[rightChild(i)]);
42         }
43         if (v[i] < max_val) {
44             if (max_val == v[leftChild(i)]) {
45                 swap(v[i], v[leftChild(i)]);
46                 i = leftChild(i);
47             } else {
48                 swap(v[i], v[rightChild(i)]);
49                 i = rightChild(i);
50             }
51         } else {
52             break;
53         }
54     }
55 }
56 
57 void heapSort(vector<int> &v)
58 {
59     int n;
60     int i;
61     
62     n = (int)v.size();
63     for (i = (n - 1) / 2; i >= 0; --i) {
64         percolateDown(v, i, n);
65     }
66     
67     int val;
68     for (i = 0; i < n - 1; ++i) {
69         val = v[0];
70         v[0] = v[n - 1 - i];
71         percolateDown(v, 0, n - 1 - i);
72         v[n - 1 - i] = val;
73     }
74 }
75 
76 int main()
77 {
78     vector<int> v;
79     int n, i;
80     
81     while (cin >> n && n > 0) {
82         v.resize(n);
83         for (i = 0; i < n; ++i) {
84             cin >> v[i];
85         }
86         heapSort(v);
87         for (i = 0; i < n; ++i) {
88             cout << v[i] << ' ';
89         }
90         cout << endl;
91     }
92     
93     return 0;
94 }

《数据结构与算法分析：C语言描述》复习——第六章“排序”——堆排序

推荐阅读