堆排序(二)
组{20,30,90,40,70,110,60,10,100,50,80}也就变成了{110,100,90,40,80,20,60,10,30,50,70}。
第2部分 交换数据
在将数组转换成最大堆之后，接着要进行交换数据，从而使数组成为一个真正的有序数组。
交换数据部分相对比较简单，下面仅仅给出将最大值放在数组末尾的示意图。
上面是当n=10时，交换数据的示意图。
当n=10时，首先交换a[0]和a[10]，使得a[10]是a[0...10]之间的最大值；然后，调整a[0...9]使它称为最大堆。交换之后：a[10]是有序的！
当n=9时， 首先交换a[0]和a[9]，使得a[9]是a[0...9]之间的最大值；然后，调整a[0...8]使它称为最大堆。交换之后：a[9...10]是有序的！
...
依此类推，直到a[0...10]是有序的。
堆排序的时间复杂度和稳定性
堆排序时间复杂度
堆排序的时间复杂度是O(N*lgN)。
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？
堆排序是采用的二叉堆进行排序的，二叉堆就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。最多是多少呢？由于二叉堆是完全二叉树，因此，它的深度最多也不会超过lg(2N)。因此，遍历一趟的时间复杂度是O(N)，而遍历次数介于lg(N+1)和lg(2N)之间；因此得出它的时间复杂度是O(N*lgN)。
堆排序稳定性
堆排序是不稳定的算法，它不满足稳定算法的定义。它在交换数据的时候，是比较父结点和子节点之间的数据，所以，即便是存在两个数值相等的兄弟节点，它们的相对顺序在排序也可能发生变化。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！
堆排序实现
堆排序C实现
实现代码(heap_sort.c)
1 /**
2 * 堆排序：C 语言
3 *
4 * @author skywang
5 * @date 2014/03/12
6 */
7
8 #include
9
10 // 数组长度
11 #define LENGTH(array) ( (sizeof(array)) / (sizeof(array[0])) )
12 #define swap(a,b) (a^=b,b^=a,a^=b)
13
14 /*
15 * (最大)堆的向下调整算法
16 *
17 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
18 * 其中，N为数组下标索引值，如数组中第1个数对应的N为0。
19 *
20 * 参数说明：
21 * a -- 待排序的数组
22 * start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
23 * end -- 截至范围(一般为数组中最后一个元素的索引)
24 */
25 void maxheap_down(int a[], int start, int end)
26 {
27 int c = start; // 当前(current)节点的位置
28 int l = 2*c + 1; // 左(left)孩子的位置
29 int tmp = a[c]; // 当前(current)节点的大小
30 for (; l <= end; c=l,l=2*l+1)
31 {
32 // "l"是左孩子，"l+1"是右孩子
33 if ( l < end && a[l] < a[l+1])
34 l++; // 左右两孩子中选择较大者，即m_heap[l+1]
35 if (tmp >= a[l])
36 break; // 调整结束
37 else // 交换值
38 {
39 a[c] = a[l];
40 a[l]= tmp;
41 }
42 }
43 }
44
45 /*
46 * 堆排序(从小到大)
47 *
48 * 参数说明：
49 * a -- 待排序的数组
50 * n -- 数组的长度
51 */
52 void heap_sort_asc(int a[], int n)
53 {
54 int i;
55
56 // 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。
57 for (i = n / 2 - 1; i >= 0; i--)
58 maxheap_down(a, i, n-1);
59
60 // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
61 for (i = n - 1; i > 0; i--)
62 {
63 // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
64 swap(a[0], a[i]);
65 // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
66 // 即，保证a[i-1]是a[0...i-1]中的最大值。
67 maxheap_down(a, 0, i-1);
68 }
69 }
70
71 /*
72 * (最小)堆的向下调整算法
73 *
74 * 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
75 * 其中，N为数组下标索引值，如数组中第1个数对应的N为0。
76 *
77 * 参数说明：
78 * a -- 待排序的数组
79 * start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
80 * end -- 截至范围(一般为数组中最后一个元素的索引)
81 */
82 void minheap_down(int a[], int start, int end)
83 {
84 int c = start; // 当前(current)节点的位置
85 int l = 2*c + 1; // 左(left)孩子的位置
86 int tmp = a[c]; // 当前(current)节点的大小
87 for (; l <= end; c=l,l=2*l+1)
88 {
89 // "l"是左孩子，"