堆排序实现
时间：2010-06-11 来源：wsnhyjj
代码是一个堆排序的实现，实现的是最大堆，主函数写了个简单的测试用例。
#include <stdio.h>
void Swap(int *a,int *b) { int tmp;
tmp = *a; *a = *b; *b = tmp;
}
void Heapify(int *A,int idx,int max) { int left = 2*idx + 1; int right = 2*idx + 2; int largest;
if((left<max)&&(A[left]>A[idx])) largest = left; else largest = idx; if((right<max)&&(A[right]>A[largest])) largest = right; if(largest!=idx) { Swap(&A[idx],&A[largest]); Heapify(A,largest,max); } }
void BuildHeap(int *A,int n) { int i = n/2-1; while(i>=0) { Heapify(A,i,n); i--; } }
void Sort(int *A,int n) { int i; BuildHeap(A,n); i = n-1; while(i>=1) { Swap(&A[0],&A[i]); Heapify(A,0,i); i--; } }
int main() { int A[8] = {5,3,16,2,10,14,1,8}; int k;
Sort(A,8); printf("Array A after sorted is : "); for(k=0;k<8;k++) { printf(" %d ", A[k]); } printf("\n"); return 0; }
#include <stdio.h>
void Swap(int *a,int *b) { int tmp;
tmp = *a; *a = *b; *b = tmp;
}
void Heapify(int *A,int idx,int max) { int left = 2*idx + 1; int right = 2*idx + 2; int largest;
if((left<max)&&(A[left]>A[idx])) largest = left; else largest = idx; if((right<max)&&(A[right]>A[largest])) largest = right; if(largest!=idx) { Swap(&A[idx],&A[largest]); Heapify(A,largest,max); } }
void BuildHeap(int *A,int n) { int i = n/2-1; while(i>=0) { Heapify(A,i,n); i--; } }
void Sort(int *A,int n) { int i; BuildHeap(A,n); i = n-1; while(i>=1) { Swap(&A[0],&A[i]); Heapify(A,0,i); i--; } }
int main() { int A[8] = {5,3,16,2,10,14,1,8}; int k;
Sort(A,8); printf("Array A after sorted is : "); for(k=0;k<8;k++) { printf(" %d ", A[k]); } printf("\n"); return 0; }
相关阅读 更多 +
