频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
排序算法之堆排序
2011-10-06 16:00:43           
收藏   我要投稿

 

基本思想:

 

在堆排序的算法中先建一个大顶堆,既先选得一个关键字作为最大的记录并与序列中最后一个记录交换,然后对序列中前N-1记录进行选择,重新将它调整成一个大顶堆,如此反复直到排序结束。

 

 

#include <stdio.h> 

const int Length = 10; //堆大小 

void Max_Heapify(int [], int, int); 

void Build_Max_Heap(int []); 

void HeapSort(int [], int); 

/*单一子节点最大堆调整*/ 

void Max_Heapify(int L[], int i, int length) 

    int l = 2*i+1;/*根节点为0时,i的左子节点*/ 

    int r = 2*i+2;/*右子节点*/ 

    int largest; 

    int temp; 

    if(l < length && L[l] > L[i]) 

    { 

        largest = l; 

    } 

    else  

    { 

        largest = i; 

    } 

    if(r < length && L[r] > L[largest]) 

    { 

        largest = r; 

    } 

    if(largest != i) 

    { 

        temp = L[i]; 

        L[i] = L[largest]; 

        L[largest] = temp; 

        Max_Heapify(L, largest, length);//交换后的子节点比父节点小, 

        //但不能保证交换过来的子节点比他的子节点小,所以要递归,使子节点为根的子树也是最大堆  

    } 

/*建立初始最大堆*/ 

void Build_Max_Heap(int L[]) 

    int i,j; 

    for(i = Length/2; i >= 0; i--) 

    { 

        Max_Heapify(L, i, Length); 

         

    } 

/*堆排序*/ 

void HeapSort(int L[], int length) 

    int temp; 

    int i; 

    Build_Max_Heap(L); 

    for(i = length - 1; i >= 1; i--) 

    { 

        temp = L[0];// 交换堆顶和堆尾,取得最大值  

        L[0] = L[i]; 

        L[i] = temp; 

        length = length - 1;//整个数组元素个数减1  

        Max_Heapify(L, 0, length);//对新数组生成最大堆  

    } 

    for(i = 0; i < Length;i++) 

    { 

        printf("%d ", L[i]); 

    } 

    printf("\n"); 

  

int main() 

    int L[10]={4,9,2,6,0,8,3,7,5,1},i; 

    HeapSort(L, Length); 

     

    system("pause"); 

    return 0; 

creat by 张飞雪

点击复制链接 与好友分享!回本站首页
相关TAG标签 算法
上一篇:Windows批处理学习笔记
下一篇:排序算法之基数排序,随机数的产生和程序运行时间的计算
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站