一步一步写算法（之堆排序）

 

【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：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_normal_position(array, index))){

              reconstruct_heap(array, swap, length);

       }

}    e）对单分支节点和满分支节点分别处理

 

 

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; 

} 

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）堆排序算法介绍完毕，创建测试用例验证

 

 

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

} 

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

}