算法之堆排序

堆排序是是指利用堆这种数据结构所设计的一种排序算法。
c语言的实现如下：
[cpp]  
#include <stdio.h>  
  
#define SIZE 10  
  
//打印数组  
void display(int array[],int size){  
        printf("the array is:");  
        int i;  
        for(i=0;i<size;i++){  
                printf("%d ",array[i]);  
        }  
        printf("\n");  
}  
  
//创建堆，使最大的数位于树根  
void createHeap(int array[], int size){  
        int parent,child,temp;  
    //刚开始时，parent的值为最后一个父节点，依次往前将斤左右孩子中较大的节点与父节点交换，最后使树根为最大数  
        for(parent=(size+1)/2-1;parent>=0;parent--){  
        //获取父节点的左孩子  
                child = parent*2+1;  
                  
        //如果该父节点存在右孩子，并且比做孩子大，则使用右孩子，否则还是使用左孩子  
                if((child+1)<=size){  
                        if(array[child+1] > array[child]){  
                                child++;  
                        }  
                }  
                  
        //将左右孩子中较大者与父节点交换  
                if(array[parent] < array[child]){  
                        temp = array[parent];  
                        array[parent] = array[child];  
                        array[child] = temp;  
                }  
        }  
}  
  
//堆排序  
void heap(int array[], int size){  
        int i,temp;  
        for(i=size-1;i>=0;i--){  
        //创建堆，使最大的数位于树根  
                createHeap(array,i);  
        //将树根和最后一个节点交换  
                temp = array[i];  
                array[i] = array[0];  
                array[0] = temp;  
                  
                display(array,SIZE);  
        }  
}  
  www.zzzyk.com
int main(void){  
        int array[SIZE]={34,45,1,39,21,68,65,100,4,51};  
        display(array,SIZE);  
    //堆排序函数  
        heap(array,SIZE);  
        display(array,SIZE);  
        return 0;  
}  
 

补充：软件开发 , C++ ,

上一个：codeforces 111C Petya and Spiders
下一个：自行设计NPAPI开发框架