各种排序算法

#include
#include
#include
#include
#include
#define  N   25000     // 待排序元素的个数

void insertsort(int R[N+1])  // 直接插入排序
{
 int i,j;
 for (i=2; i<=N; i++) {
  R[0]=R;    // 设置监视哨
  j=i-1;
  while (R[0]   R[j+1]=R[j];
   j--;
  }
  R[j+1]=R[0];
 }
}

void shellsort(int R[N+1])  // 希尔排序
{
 int i,j,gap;
 int x;
 gap=N/2;   // 设置初始增量
 while (gap>0) {
  for (i=gap+1; i<=N; i++) {
   j=i-gap;
   while (j>0)
    if(R[j]>R[j+gap]) {
     x=R[j];
     R[j]=R[j+gap];
     R[j+gap]=x;
     j=j-gap;
    }
    else
     j=0;
  }
  gap=gap/2;   // 减小增量
 }
}

void bubblesort(int R[N+1])  // 起泡排序
{
 int i,j,noswap;
 int temp;
 for (i=1; i<=N-1; i++) {
  noswap=1;
  for (j=N; j>=i+1; j--)
   if(R[j]    temp=R[j];
    R[j]=R[j-1];
    R[j-1]=temp;
    noswap=0;
   }
  if(noswap)
   break;
 }
}

int partition(int R[N+1],int low,int high)  // 快速排序的子函数（取定枢轴元素）
{
 int i,j;
 i=low;
 j=high;
 R[0]=R[low];   // 取定枢轴元素
 do {  // 从表的两端交替地向中间扫描
  while ((j>i) && (R[j]>=R[0]))
   j--;
  if(i   R=R[j];
   i++;
  }
  while ((i<=R[0]))
   i++;
  if(i   R[j]=R;
   j--;
  }
 } while (i R=R[0];  // 枢轴元素到位
 return i;   // 返回枢轴位置
}

void quicksort(int R[N+1],int low,int high)  // 快速排序
{
 int i;
 if(low  i=partition(R,low,high);  // 将表R一分为二
  quicksort(R,low,i-1);     // 对低子表递归排序
  quicksort(R,i+1,high);    // 对高子表递归排序
 }
}

void selectsort(int R[N+1])    // 直接选择排序
{
 int i,j,k;
 int temp;
 for (i=1; i<=N-1; i++) {
  k=i;
  for (j=i+1; j<=N; j++)
   if(R[j]    k=j;   // 用k指出每趟在无序区间段的最小元素
   if(k!=i) {
    temp=R;
    R=R[k];
    R[k]=temp;
   }
 }
}

void sift(int R[N+1],int s,int m)  // 堆排序的子函数（筛选算法，使R[s..m]成为一个大根堆）
{
 int i,j;
 int temp;
 temp=R[s];
 i=s;
 j=2*i;   // R[j]是R的左孩子
 while (j<=m) {
  if((j   j++;  // 若右孩子较大，则把j修改为右孩子的下标
  if(temp   R=R[j];  // 将R[j]调到父亲的位置上
   i=j;
   j=2*i;      // 修改i和j的值，以便继续向下筛选
  }
  else
   break;      // 筛选完成，终止循环
 }
 R=temp;          // 被筛结点的值放入最终位置
}

void heapsort(int R[N+1])  // 堆排序
{
 int i;
 int temp;
 for (i=N/2; i>=1; i--)
  sift(R,i,N);       // 建立初始堆
 for (i=N; i>=2; i--) { // 进行N-1次循环，完成堆排序
  temp=R[1];
  R[1]=R;
  R=temp;         // 将第一个元素同当前区间内最后一个元素对换
  sift(R,1,i-1);     // 筛选R[1]结点，得到(N-1)个结点的堆
 }
}

void main()
{
 int R[N+1],RR[N+1];     // 待排序的元素组
 clock_t start,finish;   // 用于函数运行的记时
 double duration;
 int i;

 cout<<"The initial data: "< for (i=1; i<=N; i++) {
  R=rand()%5001;
  RR=R;
  cout<<<"   ";
  if(i%10==0)
   cout< }

///////////////////////////////////////////////////////////
 getchar();        // 直接插入排序
 start = clock();  // 记时开始
 insertsort(RR);
 finish = clock();   // 记时结束
 duration = (double)(finish-start) / CLOCKS_PER_SEC;
 cout<<"The result based on the insert sort is :"< for (i=1; i<=N; i++) {
  cout<<<"    ";
  if(i%10==0)
   cout< }
 cout<<"The Run Time is: "<

///////////////////////////////////////////////////////////
    getchar();        // 希尔排序
 for (i=1; i<=N; i++) {
  RR=R;
 }
 start = clock();  // 记时开始
 shellsort(RR);
 finish = clock();   // 记时结束
 duration = (double)(finish-start) / CLOCKS_PER_SEC;
 cout<<"The result based on the shell sort is :"< for (i=1; i<=N; i++) {
  cout<<<"    ";
  if(i%10==0)
   cout< }
 cout<<"The Run Time is: "<

///////////////////////////////////////////////////////////
    getchar();        // 起泡排序
 for (i=1; i<=N; i++) {
  RR=R;
 }
 start = clock();  // 记时开始
 bubblesort(RR);
 finish = clock();   // 记时结束
 duration = (double)(finish-start) / CLOCKS_PER_SEC;
 cout<<"The result based on the shell sort is :"< for (i=1; i<=N; i++) {
  cout<<<"    ";
  if(i%10==0)
   cout< }
 cout<<"The Run Time is: "<

///////////////////////////////////////////////////////////
    getchar();        //  快速排序
 for (i=1; i<=N; i++) {
  RR=R;
 }
 start = clock();  // 记时开始
 quicksort(RR,1,N);
 finish = clock();   // 记时结束
 duration = (double)(finish-start) / CLOCKS_PER_SEC;
 cout<<"The result based on the shell sort is :"< for (i=1; i<=N; i++) {
  cout<<<"    ";
  if(i%10==0)
   cout< }
 cout<<"The Run Time is: "<

///////////////////////////////////////////////////////////
    getchar();        //  直接选择排序
 for (i=1; i<=N; i++) {
  RR=R;
 }
 start = clock();  // 记时开始
 selectsort(RR);
 finish = clock();   // 记时结束
 duration = (double)(finish-start) / CLOCKS_PER_SEC;
 cout<<"The result based on the shell sort is :"< for (i=1; i<=N; i++) {
  cout<<<"    ";
  if(i%10==0)
   cout< }
 cout<<"The Run Time is: "<

///////////////////////////////////////////////////////////
    getchar();        //  堆排序
 for (i=1; i<=N; i++) {
  RR=R;
 }
 start = clock();  // 记时开始
 heapsort(RR);
 finish = clock();   // 记时结束
 duration = (double)(finish-start) / CLOCKS_PER_SEC;
 cout<<"The result based on the shell sort is :"< for (i=1; i<=N; i++) {
  cout<<<"    ";
  if(i%10==0)
   cout< }
 cout<<"The Run Time is: "<

///////////////////////////////////////////////////////////

}
/*冒泡法排序*/
     for(i=0; i         for(j=NUM-1; j>i; j--) /*内循环：进行每趟比较*/
   if(data[j]        {temp=data[j];
          data[j]=data[j-1];
          data[j-1]=temp;
    };