/***********************************************************************\功  能：实现两种排序算法，并比较这两种算法程序首先输出原数组，然后输出经两种算法排序过的数组，并输出排序时间，数组小排序时间都会显示为 0 ms   编译环境：VC ++ 6.0  author：江南孤峰  data: 2006--6--11    \************************************************************************/ #include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include <time.h> #define SIZE 100    //数组大小设置 void Exchange(int *a,int *b){   //交换 *a 与 *b int t;  t = *a; *a = *b; *b = t;} void PutOut(int array[]){   //输出排序后的结果 int i,len;  for(i=1,len=array[0]; i<=array[0]; i ++)  printf("%d ",array[i]);} void GetRandArray(int array[],int size){ //获取 size 大小的随机数组 int i;  for(i = 1; i <= size; i ++)  array[i] = rand(); array[0] = size;} /************************** 堆排序 ***********************************/#define PARRENT(i) i>>1    //获取i的父节点#define LEFT(i) i<<1    //获取i的左孩子节点#define RIGHT(i) (i<<1)+1    //获取i的右孩子节点 void KeepHeap(int array[],int i){  //使以 i 为根节点的树保持堆性质 int l,r,big; int len=array[0];   //array[0] 是数组长度  if(i>=array[0])  return; r = RIGHT(i); l = LEFT(i); if(array[l]>array[i] && l <= len)  big = l; else big = i;  if(array[r]>array[big] && r <= len)  big = r; else big = big; if(big != i){  Exchange(&array[big],&array[i]);  KeepHeap(array,big);  //交换后 big 节点可能失去了堆性质 }} void BuildHeap(int array[]){   //对array 中的数建堆 int j;  for(j=array[0]>>1; j>=1; j--)  KeepHeap(array,j);} void HeapInsert(int array[],int key){  //往堆中插入节点 int i;  array[0] ++; i = array[0]; while(i>1 && key > array[PARRENT(i)]){  array[i] = array[PARRENT(i)];  i = PARRENT(i); } array[i] = key;} void HeapSort(int array[]){   //堆排序 int i,save;  BuildHeap(array);    for(save=i=array[0]; array[0]>=2;){  Exchange(&array[1],&array[array[0]]);  array[0] --;   KeepHeap(array,1); } array[0] = save;} /******************************** 快速排序 **********************************/int Partion(int array[],int start,int end){ int i = start - 1; int j = end + 1; int x = array[start];  while(1){  do{    j --;  }while(array[j] > x);  do{   i ++;  }while(array[i] < x);  if(j > i)   Exchange(&array[j],&array[i]);  else   return j; }} void QuickSortA(int array[],int start,int end){ int p;  if(end > start){  p = Partion(array,start,end);  QuickSortA(array,start,p);  QuickSortA(array,p+1,end); }}      int main(){      // 使用两种排序算法，排序同一数组 int array[SIZE+1],save[SIZE+1]; clock_t start,end;  GetRandArray(array,SIZE); memcpy(save,array,sizeof(int)*(SIZE+1)); // copy 数组供两中算法使用 printf("The source array as followed:\n\n"); PutOut(array);  start = clock(); HeapSort(array); end = clock();  printf("\n\n\nHeapSort time is %ld(ms)\n",end - start); PutOut(array);  start = clock(); QuickSortA(save,1,save[0]); end = clock();  printf("\n\n\nQuickSort Time is %ld(ms)\n",end - start); PutOut(save); return 0;}    

评论