排序算法——堆排序

堆定义：堆是基于完全二叉树的一种数据结构，并且满足条件：每个根节点的数据都比他的叶子节点的数据要大（大顶堆）或小（小顶堆）；

堆排序：基于堆这种数据结构进行排序的方法叫做堆排序；

排序方法及步骤：

我们用数组结构来实现堆，假设有一个堆使用长度为length的数组array实现，由数学及数据结构知识可知，堆中最后一个非叶子节点对应的数组下标为length/2-1；假设堆中有一个非叶子节点i，i的左右子节点对应在数组中的下标分别为i*2+1、i*2+2；

知道这些基本的完全二叉树属性，我们接下来就可以实现堆排序算法了。

1、首先对给与的数据进行初始化构建堆，即使这些数据符合堆的定义；

2、交换堆顶（最大或最小的节点）和堆尾元素；

3、调整除去最后一个节点的其他节点，使之满足堆的性质；

4、返回步骤2继续操作，直至堆节点只有一个；

下面是算法实现，以大顶堆为例：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 void print_log(int *a, int length);
 5 
 6 int adjust_heap(int *arr, int index, int length)
 7 {
 8     int currentValue = arr[index];
 9     for (int i = index*2+1; i < length; i = i*2+1)
10     {
11         if (i+1 < length && arr[i] < arr[i+1])
12         {
13             i++;
14         }
15         
16         if (arr[i] > currentValue)
17         {
18             arr[index] = arr[i];
19             index = i;
20         }
21         else
22         {
23             break;
24         }
25     }
26     
27     arr[index] = currentValue;
28     
29     return 0;
30 }
31 
32 int init_heap(int *arr, int length)
33 {
34     for (int i = length/2-1; i >= 0; --i)
35     {
36         adjust_heap(arr, i, length);
37     }
38     return 0;
39 }
40 
41 int swap(int *arr, int index1, int index2)
42 {
43     int temp = arr[index1];
44     arr[index1] = arr[index2];
45     arr[index2] = temp;
46 }
47 
48 int heap_sort(int *arr, int length)
49 {
50     init_heap(arr, length);
51     
52     print_log(arr, length);
53     
54     for (int i = length-1; i >= 0; --i)
55     {
56         swap(arr, 0, i);
57         adjust_heap(arr, 0, i);
58     }
59     return 0;
60 }
61 
62 void print_log(int *a, int length)
63 {
64     for (int i = 0; i < length; ++i)
65     {
66         cout << a[i] << " , ";
67     }
68     
69     cout << endl;
70 }
71 
72 int main() {
73     int a[10] = {9, 10, 8, 6, 4, 5, 2, 3, 1, 7};
74     
75     int length = sizeof(a)/sizeof(*a);
76     heap_sort(a, length);
77     
78     print_log(a, length);
79 
80     return 0;
81 }

算法重新调整了一下：

  1 #include <iostream>
  2 using namespace std;
  3 
  4 int adjust_heap_recursive(int *arr, int index, int length);
  5 void print_log(int *a, int length);
  6 int swap(int *arr, int index1, int index2);
  7 
  8 /*****
  9 ** summary : create heap.
 10 ** parameter@arr : array to sort.
 11 ** parameter@length : the length of array.
 12 *****/
 13 int init_heap(int *arr, int length)
 14 {
 15     for (int i = 0; i < length/2-1; ++i)
 16     {
 17         adjust_heap_recursive(arr, i, length);
 18     }
 19     return 0;
 20 }
 21 
 22 /*****
 23 ** summary : adjust correct value to index .
 24 ** parameter@arr : array to opera .
 25 ** parameter@index : position .
 26 ** parameter@length : the length of array .
 27 *****/
 28 int adjust_heap_recursive(int *arr, int index, int length)
 29 {
 30     if (2*index+1 == length-1)  // have left child node.
 31     {
 32         if (adjust_heap_recursive(arr, 2*index+1, length)  > arr[index])
 33         {
 34             swap(arr, index, 2*index+1);
 35         }
 36     }
 37     else if (2*index+2 < length)  // have both left and right nodes.
 38     {
 39         if (adjust_heap_recursive(arr, 2*index+1, length) < adjust_heap_recursive(arr, 2*index+2, length))
 40         {
 41             if (adjust_heap_recursive(arr, 2*index+2, length) > arr[index])
 42             {
 43                 swap(arr, index, 2*index+2);
 44             }
 45         }
 46         else
 47         {
 48             if (adjust_heap_recursive(arr, 2*index+1, length) > arr[index])
 49             {
 50                 swap(arr, index, 2*index+1);
 51             }
 52         }
 53     }
 54 
 55     return arr[index];
 56 }
 57 
 58 /*****
 59 ** summary : exchange value between index1 and index2
 60 *****/
 61 int swap(int *arr, int index1, int index2)
 62 {
 63     int temp = arr[index1];
 64     arr[index1] = arr[index2];
 65     arr[index2] = temp;
 66 
 67     return 0;
 68 }
 69 
 70 /*****
 71 ** summary : heap sort.
 72 ** parameter@arr : array to sort.
 73 ** parameter@length : the length of array.
 74 *****/
 75 int sort_heap(int *arr, int length)
 76 {
 77     for (int i = length-1; i >= 0; --i)
 78     {
 79         swap(arr, 0, i);
 80         adjust_heap_recursive(arr, 0, i);
 81     }
 82 
 83     return 0;
 84 }
 85 
 86 /*****
 87 ** summary : heap sort.
 88 *****/
 89 int sort(int *arr, int length)
 90 {
 91     init_heap(arr, length);
 92 
 93     print_log(arr, length);
 94 
 95     sort_heap(arr, length);
 96 
 97     return 0;
 98 }
 99 
100 /*****
101 ** summary : print logs.
102 ** parameter@a : array.
103 ** parameter@length : the length of array.
104 *****/
105 void print_log(int *a, int length)
106 {
107     for (int i = 0; i < length; ++i)
108     {
109         cout << a[i];
110         if (i != length-1)
111         {
112             cout << " ,";
113         }
114     }
115 
116     cout << endl;
117 }
118 
119 int main() {
120     int a[19] = {9, 10, 8, 6, 4, 5, 2, 3, 1, 7, 11, 13, 12, 15, 14, 100, 201, 300, 821};
121 
122     int length = sizeof(a)/sizeof(*a);
123     sort(a, length);
124 
125     print_log(a, length);
126 
127     return 0;
128 }