C语言堆排序算法实现

jack1007

堆排序思想：
首先把数组看成是一个无序的堆结构，然后首先把数组构建成大根堆，及所有父节点不小于他的两个子节点。
构建的大根堆的特点是顶点值一定不小于所有子节点的值。
然后把大根堆的顶点，也就是数组第一个元素值和堆的尾节点值交换。
这样最大值就一定最后面。尾节点之前的堆结构就失去大根堆特性了，然后需要重新构建大根堆（除了尾节点以外，因为尾节点已经有顺序了，为最大值）
然后再次交换顶点和倒数第二个堆节点的值，然后再重构大根堆（除堆结尾已经交换过的值）。
重复上面步骤，直到只有最顶层的堆节点，这时候整个堆结构为一个递增的数组序列（虽然堆已经不是大根堆了）。
整个算法的核心就是构建大根堆（heap_ex函数实现），其中要注意堆节点和数组键，堆节点从1开始，数组键从0开始。
整个堆排序代码如下：

1. #include <stdio.h>
   
2. 
   
3. void swap(int *a, int *b);
   
4. void print_arr(int *arr, int arr_len);
   
5. void heap_build(int *arr, int note, int arr_len);
   
6. void heap_sort(int *arr, int note, int arr_len);
   
7. void heap_ex(int *arr, int i, int arr_end);
   
8. 
   
9. int
   
10. main()
    
11. {
    
12.   int arr[] = {34, 12, 77, 85, 98, 42, 33, 18, 64, 59, 83};
    
13.   int arr_len;
    
14.   int note = 0;
    
15.   arr_len = sizeof(arr) / sizeof(arr[0]);
    
16.   print_arr(arr, arr_len);  //打印未排序前的数组
    
17.   heap_build(arr, note, arr_len - 1);
    
18.   print_arr(arr, arr_len);  //打印第一次构建大根堆后的数组
    
19.   heap_sort(arr, note, arr_len - 1);
    
20.   print_arr(arr, arr_len);  //打印排序后的数组
    
21. }
    
22. 
    
23. void
    
24. heap_build(int *arr, int i_note, int arr_end)
    
25. {
    
26.   //build max_heap, the note i is the heap note
    
27.   int i;
    
28.   int arr_len = arr_end + 1;
    
29.   for (i = arr_len / 2; i > 0; i-- ) {
    
30.     heap_ex(arr, i, arr_end);  //move heap_note func
    
31.   }
    
32. }
    
33. 
    
34. void
    
35. heap_ex(int *arr, int i, int arr_end)
    
36. {
    
37.   //the core func in this program, note_i is the key of the arr
    
38.   int note_i = i - 1;
    
39.   int child_i = 2 * note_i + 1;
    
40.   while (child_i <= arr_end) {
    
41.     if (child_i + 1 <= arr_end && arr[child_i] < arr[child_i + 1])
    
42.       child_i++;
    
43.     if (child_i <= arr_end && arr[child_i] > arr[note_i]) {
    
44.       swap(&arr[child_i], &arr[note_i]);
    
45.       note_i = child_i;
    
46.       child_i = 2 * note_i + 1;
    
47.     } else
    
48.       break;
    
49.   }
    
50. }
    
51. 
    
52. void
    
53. heap_sort(int *arr, int note, int arr_end)
    
54. {
    
55.   /*
    
56.   *the first value swap with the end value,
    
57.   *than rebuild the max_heap except the end of the values which have been swaped with the first value
    
58.   */
    
59.   int i = arr_end;
    
60.   while (i >= 0) {
    
61.     swap(&arr[0], &arr[i]);
    
62.     i--;
    
63.     heap_build(arr, note, i);
    
64.   }
    
65. }
    
66. 
    
67. 
    
68. void
    
69. swap(int *a, int *b)
    
70. {
    
71.   int tmp;
    
72.   tmp = *a;
    
73.   *a = *b;
    
74.   *b = tmp;
    
75. }
    
76. 
    
77. void
    
78. print_arr(int *arr, int arr_len)
    
79. {
    
80.   int i = 0;
    
81.   while (i < arr_len) {
    
82.     printf("%d ", arr[i]);
    
83.     i++;
    
84.   }
    
85.   printf("\n");
    
86. }

复制代码