当前位置:首页 » 计算机算法

算法堆排序堆排序

2013-05-03 19:43 本站整理 浏览(6)
新手发帖,很多方面都是刚入门,有错误的地方请大家见谅,欢迎批评指正
堆排序算法
开始时,堆排序算法先用BuildMaxHeap 将入输数组data[0...n-1]构形成一个最大堆。因为数组中最大素元在根data[0],则可以通过把它与data[n-1]互换来到达终最准确的位置。但是新的根素元可能违背了最大堆性子。这时用调MaxHeapify(data,0,size)以可就持保这一性子,在data[0...n-2]中构造出最大堆。对排序算法一直重复这个程过,堆的小大由n-1 始终降到 2,排序终了。
每日一道理
如果只看到太阳的黑点,那你的生活将缺少温暖;如果你只看到月亮的阴影,那么你的生命历程将难以找到光明;如果你总是发现朋友的缺点,你么你的人生旅程将难以找到知音;同样,如果你总希望自己完美无缺,假设你的这一愿望真的能如愿以偿,那么你最大的缺点就是没有缺点。
//Heap Sort
//by yew1eb
#include <iostream>
#include <algorithm>
using namespace std;
#define N 1000

/*
*堆化
*MaxHeapify让a[i]在堆中"下落",使以i为根的子树持保堆的性子。
*/
void MaxHeapify(int *data, int i, const int size) {
    int p = i*2 + 1;
    while ( p<size ) {
        if( p+1<size ) {
            if( data[p]>data[p+1] )
                ++p;
        }
        if(data[i]>data[p] ) {
            swap(data[p], data[i]);
            i = p;
            p =i*2 + 1;
        } else
            break;
    }
}
void BuildMaxHeap(int *data, int size) {
    for(int i=size/2; i>=0; --i)
        MaxHeapify(data, i, size);
}

void HeapSort(int *data, int size) {
    BuildMaxHeap(data,size);
    for(int i = size -1; i>0; --i) {
        swap(data[0], data[i]);
        MaxHeapify(data,0,i);
    }
}

void PrintArray(int *data, int size) {
    for(int i=0; i<size; ++i)
        cout<<data[i]<<" ";
    cout<<endl;
}

int main() {
    int size;
    int data
;
    cin>>size;
    for(int i=0; i<size; ++i)
        cin>>data[i];
    HeapSort(data,size);
    PrintArray(data,size);
    return 0;
}

练习题:
HDU 1040 As Easy As A+B
我的代码
文章结束给大家分享下程序员的一些笑话语录: IBM和波音777
  波音777是有史以来第一架完全在电脑虚拟现实中设计制造的飞机,所用的设备完全由IBM公司所提供。试飞前,波音公司的总裁非常热情的邀请IBM的技术主管去参加试飞,可那位主管却说道:“啊,非常荣幸,可惜那天是我妻子的生日,So..”..
  波音公司的总载一听就生气了:“胆小鬼,我还没告诉你试飞的日期呢!”