【转】c语言版堆排序
#include<stdio.h>#include<stdlib.h>
#include<time.h>
#define random(i) (rand()%i)
#define N 15
//维护堆的性质，这里是用的最大堆
//且为二叉堆
void MAX_HEAPIFY(int A[],int i,int heapSize){
int l;//表示节点i的左孩子
int r;//表示节点i的右孩子
int largest;//表示最大元素，也就是根.
int temp;//临时变量，用于交换
int k;
l=2*i+1;
r=2*i+2;
if((l<heapSize)&&(A>A)) //如果左孩子大，那么记下下标
{
largest=l;
}
else
{
largest=i;
}
if ((r<heapSize)&&(A>A))
{
largest=r;
}
if (largest!=i)
{
temp=A;
A=A;
A=temp;
//递归调用
MAX_HEAPIFY(A,largest,heapSize);
}
}
//建堆
void BUILD_HEAP(int A[]){
int i;
for (i=N/2-1;i>=0;i--)
{
MAX_HEAPIFY(A,i,N);
}
}
//堆排序
void HEAP_SORT(int A[]){
int i;
int j=0;
int temp; //交换时用的临时变量
int size=N; //size代表元素个数
//先建堆
BUILD_HEAP(A);
for(i=N-1;i>0;i--)
{
//因为根节点总是最大的数，我们每次把根节点换到相应位置即可实现排序
//堆排序的时间复杂度为O（nlgn）
temp=A;
A=A;
A=temp;
size--;
MAX_HEAPIFY(A,0,size);
}
for(j=0;j<N;j++)
{
printf("%5d",A);
}
}
void main(){
int rand_no=0;
int i=0;
int a; //n表示数组长度
srand((int)time(0)); //设置随机数种子
printf("==============================排序前=========================================");
printf("\n");
for(rand_no=0;rand_no<N;rand_no++)
{
a=random(100);
printf("%5d",a);
}
printf("\n");
printf("==============================排序后=========================================\n");
HEAP_SORT(a);
printf("\n");
}
好顶赞，不明觉厉，不觉明厉
好顶赞，不明觉厉，不觉明厉
好顶赞，不明觉厉，不觉明厉
好顶赞，不明觉厉，不觉明厉
好顶赞，不明觉厉，不觉明厉
好顶赞，不明觉厉，不觉明厉
好顶赞，不明觉厉，不觉明厉
好顶赞，不明觉厉，不觉明厉
好顶赞，不明觉厉，不觉明厉
页:
[1]
2