堆排序

堆排序

堆排序_百度百科
堆排序_维基百科

堆_百度百科 
堆 (数据结构)_维基百科

堆排序是和快排、归并排序一样常见的复杂度为o(nlogn)的算法，速度比较快。

那么，要进行堆排序，首先要把n个数据进行最大堆化(也就是把整个数据整理成一个最大堆)
这样子首元素就是数组最大的元素了。把它和最后的元素进行交换，那么就可以得到最后的元素是最大的。
如此类推，由于最后一个元素已经是有序的，对前面n-1个元素再进行堆调整，

inline void sort_branch(int nums[], int start, int end) {
  // sorts a branch making the maxinum in the brach to the root
  // @Param |nums|: the data array regarded as a heap
  // @|start|: the beginning index of |nums|
  // @|end|: the non-include end index of |nums|

  int larger_child;  // find the larger child and record the node

  // from node(|root|)
  // each time we search the larger child for the next step
  // loop until we have moved all larger child nodes to the upper node
  for (int root = start;
       2 * root + 1 < end;
       root = larger_child) {
    larger_child = 2 * root + 1;  // first dim larger_child as the left_child
    if (larger_child < end - 1 && nums[larger_child + 1] > nums[larger_child])
      larger_child++;

    if (nums[root] < nums[larger_child])
      swap(nums[root], nums[larger_child]);
    else
      break;
  }
}

inline void heap_sort(int nums[], int start, int end) {
  // sort with a maxinum heap.
  // @Param |nums|: the data array regarded as a heap
  // @|start|: the beginning index of |nums|
  // @|end|: the non-include end index of |nums|

  // build up a maxinum heap for the first time
  for (int i = end / 2; i >= start; i--) sort_branch(nums, i, end);

  // Now, the max number of |nums| between |start| and |end|-1 is |nums[start]|
  // for we have built up a maxinum heap. Then swap it with the last number
  // so the last number will be the largest.
  // Then sort the branch from the root to find the next maxinum number and
  // do the same again. Loop until there is only an element left, which means
  // we have sorted all elements
  for (int j = end - 1; j > start; j--) {
    swap(nums[0], nums[j]);
    sort_branch(nums, start, j);
  }
}