堆排序

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

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

堆排序是和快排、归并排序一样常见的复杂度为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);  }}

堆排序