一步一步写算法(之堆排序).doc

一步一步写算法(之堆排序)
【声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @】
    堆排序是另外一种常用的递归排序。因为堆排序有着优秀的排序性能,所以在软件设计中也经常使用。堆排序有着属于自己的特殊性质,和二叉平衡树基本是一致的。打一个比方说,处于大堆中的每一个数据都必须满足这样一个特性:
    (1)每一个array[n] 不小于array[2*n]
    (2)每一个array[n]不小于array[2 * n + 1]
    构建这样一个堆只是基础,后面我们需要每次从堆的顶部拿掉一个数据,不断调整堆,直到这个数组变成有序数组为主。所以详细的堆排序算法应该是这样的:
    1)构建大堆,使得堆中的每一个数据都满足上面提到的性质
    2)将堆的第一个数据和堆的最后一个数据进行互换,然后重新调整堆,直到堆重新平衡为止
    3)重复2)的过程,直到整个数组有序。
    上面的描述过程很简单,那么实践操作是怎么样的呢?
    a)对入参进行判断
[cpp] view plaincopy
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)构建大堆和调整大堆
[cpp] view plaincopy
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)构建大堆的细节操作部分
[cpp] view plaincopy
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[i