sort.cpp

这是本人精心搜集的关于常用图论算法的一套源码

#include <stdlib.h>
#include <iostream.h>
#include <time.h>
#include "sqlist.h"
void SimpleInsert(recordfile, int);       //简单插入排序
void  BinarySort(recordfile, int);        //二分法插入排序
void BubbleSort (recordfile, int);        //冒泡排序
void BubbleSort_better(recordfile r,int);  //改进冒泡排序
void selesort(recordfile, int);           //简单选择排序
void shellsort(recordfile, int);          //Shell排序
void qksort(recordfile, int, int);        //快速排序
void mergesort(recordfile, recordfile ,int);   // 2-路归并排序 
void heapsort(recordfile,int );                 //堆排序
void main(void)
{
  int i;  time_t t; clock_t start, finish;
  recordfile org,r,r1;
  srand((unsigned)time(&t));
  cout<<"Random generate "<<maxn-1<< " integers\n\n";
  for(i=1;i<maxn; i++) org[i].key=rand();

  
  for(i=1;i<maxn; i++) r[i].key=org[i].key;
  start = clock(); 
  selesort(r,maxn-1);
  finish = clock();   
  cout<<" SimpleSelectSort CostTime is "<<(double)(finish - start) / CLOCKS_PER_SEC <<endl;
  
  for(i=1;i<maxn; i++) r[i].key=org[i].key;
  start = clock();
  SimpleInsert(r,maxn-1);
  finish = clock();
  cout<<" SimpleInsert CostTime is "<<(double)(finish - start) / CLOCKS_PER_SEC <<endl;
 
  for(i=1;i<maxn; i++) r[i].key=org[i].key;
  start = clock(); 
  BinarySort(r,maxn-1);
  finish = clock();  
  cout<<" BinarySort CostTime is "<<(double)(finish - start) / CLOCKS_PER_SEC <<endl;

  for(i=1;i<maxn; i++) r[i].key=org[i].key;
  start = clock(); 
  BubbleSort(r,maxn-1);
  finish = clock();   
  cout<<" BubbleSort CostTime is "<<(double)(finish - start) / CLOCKS_PER_SEC <<endl;

/*  for(i=1;i<maxn; i++) r[i].key=org[i].key;
  start = clock(); cout<<"\n\nBubbleSort_better start: "<<start<<endl;
  BubbleSort_better(r,maxn-1);
  finish = clock();   cout<<"BubbleSort_better finish: "<<finish<<endl;
  cout<<" BubbleSort_better CostTime is "<<(double)(finish - start) / CLOCKS_PER_SEC<<endl;
*/  

  for(i=1;i<maxn; i++) r[i].key=org[i].key;
  start = clock(); 
  shellsort(r,maxn-1);
  finish = clock();  
  cout<<" SellSort CostTime is "<< (double)(finish - start) / CLOCKS_PER_SEC<<endl;
  
  for(i=1;i<maxn; i++) r[i].key=org[i].key;
  start = clock();
  qksort(r,1,maxn-1);
  finish = clock();
  cout<<" quickSort CostTime is "<<(double)(finish - start) / CLOCKS_PER_SEC<<endl;

  for(i=1;i<maxn; i++) r[i].key=org[i].key;
  start = clock(); 
  mergesort(r,r1,maxn-1);
  finish = clock();
  cout<<" MergeSort CostTime is "<<(double)(finish - start) / CLOCKS_PER_SEC<<endl;

  for(i=1;i<maxn; i++) r[i].key=org[i].key;
  start = clock(); 
  heapsort(r,maxn-1);
  finish = clock();   
  cout<<" HeapSort CostTime is "<<(double)(finish - start) / CLOCKS_PER_SEC<<endl;
}

void SimpleInsert(recordfile r,int n)            //简单插入排序
  // r[1]~r[n]存储待排序记录,r[0]是监视哨
{ int  i,j;
  for(i=2;i<=n;i++)                    // 从第2个记录起逐个插入
      { r[0]=r[i]; j=i-1;
        while(r[0].key<r[j].key) r[j+1]=r[j--];  // 寻找插入位置
        r[j+1]=r[0];                             // 将第i个记录插入
      }  //end_for
}
void  BinarySort(recordfile r,int n )         //简单选择排序
 { int  i,l,u,m;   
   for(i=2;i<=n;i++)                          // 从第二个记录起逐个插入
      { r[0]=r[i]; l=1; u=i-1;                      // l 和 u 为二分查找的上下界
        while(l<=u){m=(l+u)/2;                   // 用二分查找寻找插入位置
                    if(r[0].key<r[m].key)u=m-1;  else l=m+1;
                   }//end_while
        for(m=i-1;m>=l;m--) r[m+1]=r[m];         // 记录后移
        r[l]=r[0];                                  // 将第i个记录插入
      } // end_for i
}

void shellsort(recordfile r,int n)
{  int i,j,d;
   for(d=n/3;d>0;d/=2)
       for(i=d+1;i<=n;i++)
          { r[0]=r[i];  j=i-d;
            while(j>0 && r[0].key<r[j].key) r[j+d]=r[j], j-=d;
            r[j+d]=r[0];
          } //end_for_i
}

void BubbleSort (recordfile r,int n)
{ int i,m=1,lim=n;
  while(m) //m>0 则继续进入循环. 若某趟内循环结束,没有发生交换,则m为0,退出循环
    {lim--; m=0;
     for(i=1;i<=lim;i++)
         if(r[i].key>r[i+1].key){r[0]=r[i]; r[i]=r[i+1]; r[i+1]=r[0]; m=1;}
    }//end_while
}
void BubbleSort_better(recordfile r,int n)
{ int i,j,m;
  for(i=n;i>1;)
  { m=0;
    for(j=1;j<i;j++)
      if(r[j].key>r[j+1].key)
	  {  r[0]=r[j]; 
		 r[j]=r[j+1]; 
		 r[j+1]=r[0];
		 m=j;
		}
     i=m+1;
  }//end_while
}

void selesort(recordfile r,int n)
{int i,j,k;
 for(i=1;i<n;i++){k=i;                            // 总共进行n-1趟排序
                  for(j=i+1;j<=n;j++) if(r[j].key<r[k].key) k=j;
                  if (k!=i) { r[0]=r[i]; r[i]=r[k]; r[k]=r[0]; }
                 }  // end_for
}

void qksort(recordfile r,int s,int t)   // 把r[s]至r[t]的文件进行快速排序
{ int i=s,j=t;
   if(s<t){ r[0]=r[s];
   	    do{ while (j>i&&r[j].key>=r[0].key) j--;
                if(i<j){ r[i]=r[j]; i++;  }
                while (i<j&&r[i].key<=r[0].key) i++;
                if(i<j){ r[j]=r[i]; j--; }
              } while (i<j);              // 直到i==j 脱离循环
            r[i]=r[0];
            qksort(r,s,j-1);  
            qksort(r,j+1,t);
          } //end_if
}

void merge(recordfile r,recordfile r1,int s,int m,int t)   // 两相邻文件归并过程
// 将有序子文件r[s]～r[m] 及r[m+1]～r[t] 合并成一个有序文件存入r1[s]～r1[t]
{ int  i=s,j=m+1,k=s-1;
  while((i<=m) && j<=t)
        if (r[i].key<=r[j].key) r1[++k]=r[i++];
         else   r1[++k]=r[j++];
  if(i>m) for (; j<=t; j++)  r1[++k]=r[j];
   else   for (; i<=m;i++)  r1[++k]=r[i];
}
void  mergepass(recordfile r, recordfile r1,int n,int l)    // 一趟归并过程
{ int  p=1;
 while(n-p+1>=2*l)
   { merge(r,r1,p,p+l-1,p+2*l-1);     // 将 r 中长度为 l 的两个子文件合并
       // 第 1 个文件下标从 p 到 (p+l-1),第 2 个文件下标从 p+l 到 p+2*l-1
     p+=2*l;                         // p向后移2*l，准备下一次合并
   } // end_while
if(n-p+1>l)merge(r,r1,p,p+l-1,n);    //一个长度为 l 的文件与一个长度小于 l 的文件合并
 else for(; p<=n; p++) r1[p]=r[p];  //只剩下一个长度不大于 l  的子文件将其复抄到r1
}
void mergesort(recordfile r, recordfile r1,int n)   // 归并排序
{ int   l=1;
  while(l<n){ mergepass(r,r1,n, l); l*=2;             // 从r归并至r1
              mergepass(r1,r,n, l); l*=2;             // 从r1归并至r
            }
}

void insert_heap(recordfile r,int l,int u)    // 调整算法
/*  r[l]~r[u] 是一棵完全二叉树，以 r[l +1] 和 r[l +2] 为根的左右子树已经是堆，
   本算法调整 r[l]，使整个序列 r[l]~r[u]成为一个堆   */
{ int i,j;
  i=l;  j=2*l;  r[0]=r[l];
  while(j<=u){ if(j<u&&r[j].key>r[j+1].key) j++;  // 令j指向左右孩子中较小的孩子
               if(r[0].key>r[j].key){ r[i]=r[j]; i=j; j*=2; }
                else break;            //  跳出循环
             } //end_while
  r[i]=r[0];
}

void heapsort(recordfile r,int n) //堆排序
 { int i;  record t;
   for (i= n/2; i>0; i--) insert_heap(r,i,n);
   for (i=n;i>1;i--)
    { t=r[1]; r[1]=r[i]; r[i]=t; insert_heap(r,1,i-1); }
 }