【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】
堆排序是另外一种常用的递归排序。因为堆排序有着优秀的排序性能，所以在软件设计中也经常使用。堆排序有着属于自己的特殊性质，和二叉平衡树基本是一致的。打一个比方说，处于大堆中的每一个数据都必须满足这样一个特性：
（1）每一个array[n] 大于array[2*n]
（2）每一个array[n]大于array[2 * n + 1]
构建这样一个堆只是基础，后面我们需要每次从堆的顶部拿掉一个数据，不断调整堆，直到这个数组变成有序数组为主。所以详细的堆排序算法应该是这样的：
1）构建大堆，使得堆中的每一个数据都满足上面提到的性质
2）将堆的第一个数据和堆的最后一个数据进行互换，然后重新调整堆，直到堆重新平衡为止
3）重复2）的过程，直到整个数组有序。
上面的描述过程很简单，那么实践操作是怎么样的呢？
a）对入参进行判断
void heap_sort(int array[], int length)
{
if(NULL == array || 0 == length)
return ;
/* to make sure data starts at number 1 */
_heap_sort(array-1, length);
}
void heap_sort(int array[], int length)
{
if(NULL == array || 0 == length)
return ;
/* to make sure data starts at number 1 */
_heap_sort(array-1, length);
} b）构建大堆和调整大堆
void _heap_sort(int array[], int length)
{
int index = 0;
int median = 0;
construct_big_heap(array, length);
for(index = length; index > 1; index --)
{
median = array[1];
array[1] = array[index];
array[index] = median;
reconstruct_heap(array, 1, index-1);
}
}
void _heap_sort(int array[], int length)
{
int index = 0;
int median = 0;
construct_big_heap(array, length);
for(index = length; index > 1; index --)
{
median = array[1];
array[1] = array[index];
array[index] = median;
reconstruct_heap(array, 1, index-1);
}
} c）构建大堆的细节操作部分
void set_sorted_value(int array[], int length)
{
int index = length;
int median = 0;
if(length == 1) return;
while(index > 1){
if(array[index >> 1] >= array[index])
break;
median = array[index];
array[index] = array[index >> 1];
array[index >> 1] = median;
index >>= 1;
}
}
void construct_big_heap(int array[], int length)
{
int index = 0 ;
for(index = 1; index <= length; index ++)
{
set_sorted_value(array, index);
}
}
void set_sorted_value(int array[], int length)
{
int index = length;
int median = 0;
if(length == 1) return;
while(index > 1){
if(array[index >> 1] >= array[index])
break;
median = array[index];
array[index] = array[index >> 1];
array[index >> 1] = median;
index >>= 1;
}
}
void construct_big_heap(int array[], int length)
{
int index = 0 ;
for(index = 1; index <= length; index ++)
{
set_sorted_value(array, index);
}
} d）大堆迭代调整
void reconstruct_heap(int array[], int index, int length)
{
int swap = 0;
if(length < index << 1)
return;
if(length == index << 1){
adjust_leaf_position(array, index);
return;
}
if(-1 != (swap = adjust_normal_position(array, index))){
reconstruct_heap(array, swap, length);
}
}
void reconstruct_heap(int array[], int index, int length)
{
int swap = 0;
if(length < index << 1)
return;
if(length == index << 1){
adjust_leaf_position(array, index);
return;
}
if(-1 != (swap = adjust_no