堆排序是另外一種常用的遞歸排序。因?yàn)槎雅判蛴兄鴥?yōu)秀的排序性能，所以在軟件設(shè)計(jì)中也經(jīng)常使用。堆排序有著屬于自己的特殊性質(zhì)，和二叉平衡樹(shù)基本是一致的。打一個(gè)比方說(shuō)，處于大堆中的每一個(gè)數(shù)據(jù)都必須滿足這樣一個(gè)特性：

（1）每一個(gè)array[n] 不小于array[2*n]

（2）每一個(gè)array[n]不小于array[2 * n + 1]

構(gòu)建這樣一個(gè)堆只是基礎(chǔ)，后面我們需要每次從堆的頂部拿掉一個(gè)數(shù)據(jù)，不斷調(diào)整堆，直到這個(gè)數(shù)組變成有序數(shù)組為主。所以詳細(xì)的堆排序算法應(yīng)該是這樣的：

1）構(gòu)建大堆，使得堆中的每一個(gè)數(shù)據(jù)都滿足上面提到的性質(zhì)

2）將堆的第一個(gè)數(shù)據(jù)和堆的最后一個(gè)數(shù)據(jù)進(jìn)行互換，然后重新調(diào)整堆，直到堆重新平衡為止

3）重復(fù)2）的過(guò)程，直到整個(gè)數(shù)組有序。

上面的描述過(guò)程很簡(jiǎn)單，那么實(shí)踐操作是怎么樣的呢？

a）對(duì)入?yún)⑦M(jìn)行判斷

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）構(gòu)建大堆和調(diào)整大堆**

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）構(gòu)建大堆的細(xì)節(jié)操作部分

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）大堆迭代調(diào)整

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);
    }
}

e）對(duì)單分支節(jié)點(diǎn)和滿分支節(jié)點(diǎn)分別處理

int adjust_normal_position(int array[], int index)
{
    int left = index << 1 ;
    int right = left + 1;
    int median = 0;
    int swap = 0;

    if(array[index] >= array[left]){
        if(array[index] >= array[right]){
            return -1;
        }else{
            swap = right;
        }
    }else{
        if(array[index] >= array[right]){
            swap = left;
        }else{
            swap = array[left] > array[right] ? left : right;
        }
    }

    if(swap == left) {
        median = array[index];
        array[index] = array[left];
        array[left] = median;
    }else{
        median = array[index];
        array[index] = array[right];
        array[right] = median;
    }

    return swap;
}

STATUS adjust_leaf_position(int array[], int index)
{
    int median = 0;
    if(array[index] > array[index << 1])
        return TRUE;

    median = array[index];
    array[index] = array[index << 1];
    array[index << 1] = median;
    return FALSE;
}

f）堆排序算法介紹完畢，創(chuàng)建測(cè)試用例驗(yàn)證

static void test1()
{
    int array[] = {1};
    heap_sort(array, sizeof(array)/sizeof(int));
}

static void test2()
{
    int array[] = {2, 1};
    heap_sort(array, sizeof(array)/sizeof(int));
    assert(1 == array[0]);
    assert(2 == array[1]);
}

static void test3()
{
    int array[] = {3, 2, 1};
    heap_sort(array, sizeof(array)/sizeof(int));
    assert(1 == array[0]);
    assert(2 == array[1]);
    assert(3 == array[2]);
}

static void test4()
{
    int array[] = {2, 3, 1};
    heap_sort(array, sizeof(array)/sizeof(int));
    assert(1 == array[0]);
    assert(2 == array[1]);
    assert(3 == array[2]);
}

static void test5()
{
    int array[] = {5,3, 4, 1};
    heap_sort(array, sizeof(array)/sizeof(int));
    assert(1 == array[0]);
    assert(3 == array[1]);
    assert(4 == array[2]);
    assert(5 == array[3]);
}

static void test6()
{
    int array[] = {2, 3,6, 8, 7};
    heap_sort(array, sizeof(array)/sizeof(int));
    assert(2 == array[0]);
    assert(3 == array[1]);
    assert(6 == array[2]);
    assert(7 == array[3]);
    assert(8 == array[4]);
}

static void test7()
{
    int array[] = {3,4,2,7,1,9,8,6,5};
    heap_sort(array, sizeof(array)/sizeof(int));
    assert(1 == array[0]);
    assert(2 == array[1]);
    assert(3 == array[2]);
    assert(4 == array[3]);
    assert(5 == array[4]);
    assert(6 == array[5]);
    assert(7 == array[6]);
    assert(8 == array[7]);
    assert(9 == array[8]);
}