首页 > 其他 > 详细

算法导论第6章代码之堆排序

时间:2014-03-26 03:01:19      阅读:480      评论:0      收藏:0      [点我收藏+]


算法:

// 对第i个节点构建最大堆
void build_max_heap(int *a, int i, int n)
{
    int max = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
                    
    if (left < n && a[left] > a[max]) {
        max = left;
    }
                    
    if (right < n && a[right] > a[max]) {
        max = right;
    }
                    
    if (i != max) {
                        
        int temp = a[i];
        a[i] = a[max];
        a[max] = temp;
                        
        build_max_heap(a, max, n);
                        
    }
                    
}
void HeapSort(int *a, int n)
{
    int i;
    for (i = n / 2; i >= 0; i--) {
        build_max_heap(a, i, n);
    }
                    
    for (i = n - 1; i > 0; i--) {
                        
        int temp = a[i];
        a[i] = a[0];
        a[0] = temp;
                        
        build_max_heap(a, 0, i);
    }
                    
}
int main(int argc, const char * argv[])
{
    int a[] = {3, 5, 1, 2, 5, 4};
    int n = sizeof(a) / sizeof(*a);
                    
    HeapSort(a, n);
                    
    int i = 0;
    for (; i < n; i++) {
        printf("%d ", a[i]);
    }
                    
    return 0;
}


输出:1 2 3 4 5 5



本文出自 “移动开发” 博客,请务必保留此出处http://ikinglai.blog.51cto.com/6220785/1384007

算法导论第6章代码之堆排序,布布扣,bubuko.com

算法导论第6章代码之堆排序

原文:http://ikinglai.blog.51cto.com/6220785/1384007

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!