当前位置: 首页 > 网站开发 > 正文

堆排序

1 星2 星3 星4 星5 星 (2 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void HeapAdjust(int array[] , int s , int m)   // 对堆进行调整,使下标从s到m的无序序列成为一个大顶堆    
{  
    int j , temp = array[s];  
    for(j = 2*s; j <= m ; j *= 2)  
    {  
        if(j < m && array[j] < array[j + 1])   // 如果结点的左孩子小于右孩子增加j的值  
            ++j;              // 用于记录较大的结点的下标  
        if(temp >= array[j])  // 如果父结点大于等于两个孩子,则满足大顶堆的定义,跳出循环  
            break;  
        array[s] = array[j];    // 否则用较大的结点替换父结点  
        s = j;          // 记录下替换父结点的结点下标    
    }  
    array[s] = temp;        // 把原来的父结点移动到替换父结点的结点位置    
}  
 
void HeapSort(int array[] , int len)  
{  
    int i;  
    for(i = len / 2; i >= 0 ; --i)    // 建立大顶堆  
        HeapAdjust(array , i , len-1);  
    for(i = len - 1 ; i > 0 ; --i)  
    {  
        swap(array[0] , array[i] );       // 第个元素和最后一个元素进行交换    
        HeapAdjust(array , 0 , i-1);      // 建立大顶堆    
    }  
}

本文固定链接: http://www.chepoo.com/heap-sort.html | IT技术精华网

【上一篇】
【下一篇】

堆排序:等您坐沙发呢!

发表评论