/ 数据结构和算法

一步一步写算法之堆排序

堆排序是另外一种常用的递归排序。因为堆排序有着优秀的排序性能,所以在软件设计中也经常使用。堆排序有着属于自己的特殊性质,和二叉平衡树基本是一致的。打一个比方说,处于大堆中的每一个数据都必须满足这样一个特性:

  1. 每一个array[n] 不小于array[2*n]
  2. 每一个array[n]不小于array[2 * n + 1]

构建这样一个堆只是基础,后面我们需要每次从堆的顶部拿掉一个数据,不断调整堆,直到这个数组变成有序数组为主。所以详细的堆排序算法应该是这样的:

  1. 构建大堆,使得堆中的每一个数据都满足上面提到的性质
  2. 将堆的第一个数据和堆的最后一个数据进行互换,然后重新调整堆,直到堆重新平衡为止
  3. 重复2的过程,直到整个数组有序。

上面的描述过程很简单,那么实践操作是怎么样的呢?

  1. 对入参进行判断 ```
    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);
    }

2. 构建大堆和调整大堆 ```
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);  
    }  
}  
  1. 构建大堆的细节操作部分 ```
    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);  
}  

}

4. 大堆迭代调整 ```
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);  
    }  
} 
  1. 对单分支节点和满分支节点分别处理 ```
    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;  

}

6. 堆排序算法介绍完毕,创建测试用例验证 ```
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]);  
}

声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com