堆排序

堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。

核心代码

  1 #define LEFT  (2*nRootID+1)
  2 #define RIGHT (2*nRootID+2)
  3 
  4 void Adjust(int arr[], int len, int nRootID)
  5 {
  6     assert(arr!=NULL && len>0);
  7 
  8     while(1)
  9     {
 10         //两个孩子
 11         if(RIGHT < len)
 12         {
 13             //左比右大
 14             if(arr[LEFT] > arr[RIGHT])
 15             {
 16                 //左比父亲大
 17                 if(arr[LEFT] > arr[nRootID])
 18                 {
 19                     //交换
 20                     arr[LEFT] = arr[LEFT] ^ arr[nRootID];
 21                     arr[nRootID] = arr[LEFT] ^ arr[nRootID];
 22                     arr[LEFT] = arr[LEFT] ^ arr[nRootID];
 23 
 24                     //被交换位置作为新的调整位置
 25                     nRootID = LEFT;
 26                     continue;
 27                 }
 28                 else
 29                 {
 30                     break;
 31                 }
 32             }
 33             else
 34             {
 35                 //右比父亲大
 36                 if(arr[RIGHT] > arr[nRootID])
 37                 {
 38                     //交换
 39                     arr[RIGHT] = arr[RIGHT] ^ arr[nRootID];
 40                     arr[nRootID] = arr[RIGHT] ^ arr[nRootID];
 41                     arr[RIGHT] = arr[RIGHT] ^ arr[nRootID];
 42 
 43                     //被交换位置作为新的调整位置
 44                     nRootID = RIGHT;
 45                     continue;
 46                 }
 47                 else
 48                 {
 49                     break;
 50                 }
 51             }
 52         }
 53         //一个孩子
 54         else if(LEFT < len)
 55         {
 56             //左比父亲大
 57             if(arr[LEFT] > arr[nRootID])
 58             {
 59                 //交换
 60                 arr[LEFT] = arr[LEFT] ^ arr[nRootID];
 61                 arr[nRootID] = arr[LEFT] ^ arr[nRootID];
 62                 arr[LEFT] = arr[LEFT] ^ arr[nRootID];
 63 
 64                 //被交换位置作为新的调整位置
 65                 nRootID = LEFT;
 66                 continue;
 67             }
 68             else
 69             {
 70                 break;
 71             }
 72         }
 73         //没有孩子
 74         else
 75         {
 76             break;
 77         }
 78     }
 79 }
 80 
 81 void HeapSort(int arr[], int len)
 82 {
 83     int i;
 84 
 85     assert(arr!=NULL && len>0);
 86 
 87     //建堆
 88     //从最后一个父亲节点开始调整
 89     for(i=len/2-1; i>=0; --i)
 90     {
 91         //调整
 92         Adjust(arr, len, i);
 93     }
 94 
 95     //排序
 96     for(i=len-1; i>0; --i)
 97     {
 98         //堆顶和最后位置交换
 99         arr[i] = arr[i] ^ arr[0];
100         arr[0] = arr[i] ^ arr[0];
101         arr[i] = arr[i] ^ arr[0];
102 
103         //调整
104         Adjust(arr, i, 0);
105     }
106 }

函数Adjust()代码的优化

 1 void Adjust2(int arr[], int len, int nRootID)
 2 {
 3     int nMax;
 4 
 5     assert(arr!=NULL && len>0);
 6 
 7     for(nMax=LEFT; nMax<len; nMax=LEFT)
 8     {
 9         //两个孩子
10         if(RIGHT < len)
11         {
12             if(arr[RIGHT] > arr[LEFT])
13             {
14                 nMax = RIGHT;
15             }
16         }
17 
18         //最大值和父亲进行比较
19         if(arr[nMax] > arr[nRootID])
20         {
21             //交换
22             arr[nMax] = arr[nRootID] ^ arr[nMax];
23             arr[nRootID] = arr[nRootID] ^ arr[nMax];
24             arr[nMax] = arr[nRootID] ^ arr[nMax];
25 
26             //被交换位置作为新的调整位置
27             nRootID = nMax;
28         }
29         else
30         {
31             break;
32         }
33     }
34 }

算法分析：

　　最好时间复杂度：O(nlog2(n))

　　平均时间复杂度：O(nlog2(n))

　　最坏时间复杂度：O(nlog2(n))

　　　　空间复杂度：O(1)

　　　　　　稳定性：不稳定