堆排序

堆的本质上其实就是一个数组。

分为大根堆和小根堆

大根堆：父亲的值 > 孩子；

小根堆：父亲的值 < 孩子；

堆排序：与选择排序类似，也是选择最大的放在最后的位置。

　　　　优点：比选择排序快，因为在当第一次排好大根堆后，把根与最后一个值交换。这是树中只需要调整根，也就是在左孩子和右孩子中选择一个大的与之交换，然后交换的继续向下调整。所以左子树或右子树，一定有一个不动，继续调整大根堆时，最多比较树的高度次，（log₂ⁿ向下取整+1）所以与选择排序相比减少了很多次比较。

代码：

 1 #define LEFT (Root*2+1)
 2 #define RIGHT (Root*2+2)
 3 void Heap(int* arr,int len,int Root)
 4 {
 5     int index;
 6     while(1)
 7     {
 8         if(RIGHT < len )//有左,右孩子
 9          {
10              //左右孩子中大的
11             // printf("999
");
12             index = arr[LEFT] > arr[RIGHT] ? LEFT : RIGHT;
13          }
14          else if(LEFT < len)//只有左孩子
15         {
16             index = LEFT;
17         }
18         else//没孩子
19             break;
20         if(arr[index] > arr[Root]) //与根交换
21          {
22              arr[index] = arr[index]^arr[Root];
23              arr[Root] = arr[index]^arr[Root];
24              arr[index] = arr[index]^arr[Root];
25              Root = index;
26          }
27          else
28             break;
29 
30     }
31 }
32 void HeapSort(int* arr,int len)
33 {
34     if(arr == NULL || len <= 0) return;
35     //第一次调整需要调节所有父亲节点
36      for(int i = len/2-1;i >=0 ;i--)
37         Heap(arr,len,i);
38 
39     //排序
40     for(int i = len-1;i>0;i--)
41     {
42         //交换
43         arr[0] = arr[0]^arr[i];
44         arr[i] = arr[0]^arr[i];
45         arr[0] = arr[0]^arr[i];
46 
47         //调整根
48         Heap(arr,i,0);
49     }
50 }