/***********************************************************************\
功  能：实现两种排序算法，并比较这两种算法
程序首先输出原数组，然后输出经两种算法排序过的数组，并输出
排序时间，数组小排序时间都会显示为 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;
}

评论