堆排序

堆排序，我是从算法导论里面看到的，它的最基本思想就是：把一个数据建立成一个堆(我看来就是一个简单的二叉树)每一个子树的根节点是在本树里面的最大数，这时候树根就是整棵树里面最大的，然后我们每次把树根提取出来换成叶节点，也就是每次都会减少树的一个节点(就是树根的最大值)，但是根节点并不是没了，而是换成最后的一个叶节点，提取以后再重新调整树，使其符合最大(最小堆)的定义：二叉树的每个子树根节点都是本子树的最大(最小)值。

这几幅图就是建堆，先是8, 3取最大值放在本子树的根节点位置，然后是20, 17, 7取最大值放在本子树的根节点位置，以此类推到根，建堆完成。

这里3作为根显然不满足最大堆的定义，所以我们重新需要调整

这样我们就把数组排列好了，下面贴上代码

#include <iostream>
#include <stdio.h>
using namespace std;
int in[100];
void adjustHeap(int a[], int i, int sizea){
    int lChild = 2*i+1;
    int rChild = 2*i+2;//左右孩子
    int maxx = i;//暂时拿出子树根节点坐标

    if(lChild < sizea && a[lChild] > a[maxx]){
        maxx = lChild;
    }
    if(rChild < sizea && a[rChild] > a[maxx]){
        maxx = rChild;
    }                                           //记录左右孩子和根的最大
    if(maxx != i){
        swap(a[i], a[maxx]);//交换，继续往下调整，以免影响到下面的子树
        adjustHeap(a, maxx, sizea);
    }
}

void buildHeap(int sizea, int a[]){     //建堆
    for(int i = (sizea-1)/2;i >= 0;i--){//i = (sizea-1)/2从一半的地方开始，就是除去叶节点坐标
        adjustHeap(a, i, sizea);
    }
}

void heapSort(int *a, int sizea){//堆排序
    int p;
    buildHeap(sizea, a);
    for(int i = sizea-1; i > 0;i--){//这里注意i是从sizea-1开始的
        swap(a[i], a[0]);
        adjustHeap(a,0,i);
    }
}
int main()
{
    int a[100], sizea;
    while(scanf("%d",&sizea)==1 && sizea>0){
        for(int i =0;i < sizea;i++){
            cin>>a[i];
        }
        heapSort(a,sizea);
        for(int i =0;i < sizea;i++){
            cout<<a[i]<<"   ";
        }
    }
    return 0;
}

?

?

?

堆排序

原文：http://we-are-here.iteye.com/blog/2157949