计算归并排序和快速排序算法排序100-1000个数组的时间（重点在时间精确到微妙us）

蔚落 2022-06-05 23:28 123阅读 0赞

//#include<sys/time.h> //注意引用这个头文件
    //#include<unistd.h>
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    //#include<sys/time.h> //注意引用这个头文件
    //#include<unistd.h>
    #include <windows.h>
    typedef int RecType;//要排序元素类型  
    void Merge(RecType *R,int low,int m,int high)  
    {  
        //将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]  
        int i=low,j=m+1,p=0;                //置初始值  
        RecType *R1;                        //R1是局部向量  
        R1=(RecType *)malloc((high-low+1)*sizeof(RecType));  
        if(!R1)  
        {  
            return;                         //申请空间失败  
        }  
      
        while(i<=m&&j<=high)                //两子文件非空时取其小者输出到R1[p]上  
        {  
            R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];  
        }  
      
        while(i<=m)                         //若第1个子文件非空，则复制剩余记录到R1中  
        {  
            R1[p++]=R[i++];  
        }  
        while(j<=high)                      //若第2个子文件非空，则复制剩余记录到R1中  
        {  
            R1[p++]=R[j++];  
        }  
      
        for(p=0,i=low;i<=high;p++,i++)  
        {  
            R[i]=R1[p];                     //归并完成后将结果复制回R[low..high]  
        }  
    }  
      
    void MergeSort(RecType R[],int low,int high)  
    {     
        //用分治法对R[low..high]进行二路归并排序  
        int mid;  
        if(low<high)  
        {   //区间长度大于1   
            mid=(low+high)/2;               //分解  
            MergeSort(R,low,mid);           //递归地对R[low..mid]排序  
            MergeSort(R,mid+1,high);        //递归地对R[mid+1..high]排序  
            Merge(R,low,mid,high);          //组合，将两个有序区归并为一个有序区  
        }  
    }  
    
    
    
    
    
    
    
    //快速排序
    
    
    //实现交换  
    void Swap(int a[] ,int low ,int high)   
    {   
       int tmp; 
       tmp=a[low];  
      a[low]=a[high];   
      a[high]=tmp;  
    }   
    /************************************************************************** 
      函数名:partition()                                             
       功能: 计算基准点的函数,并将小于基准点的元素放于基准点的左边,大于基准点的数放于基准点右边                                           
    输入参数: int a[]:待排序的数组                                        
    int low：数组的起始位置                                     
    int high:数组的结束位置                    
     返回值:int 基准点                                    
    ***************************************************************************     
    */  
    int partition(int a[],int low,int high)     
    {   
      int point;    
      //基准点定位为第一个元素     
      point=a[low];     
      while( low < high)    
     {  
      //将大于基准点的数放于基准点的右边    
      while( low < high && a[high] >= point )   
           high--; //移到前一个元素    
    
    
      //当不满足大于基准点，交换基准点     
      Swap(a,low,high); 
    
    
      //将小于基准点的数放于基准点的左边    
      while( low < high && a[low] <= point)     
         low++; //移到下一个元素   
    
    
      //当不满足小于基准点，交换基准点     
       Swap(a,low,high);    
    }   
      return low;//返回的中间点，当退出循环后low 与high指向同一个元素    
    }   
    
    
     //low 为数组起始位置 high为数组的结束位置
    void QSort(int a[],int low,int high)    
    {   
      int point;//定义变量存放基准点     
      if( low < high )  
      {     
       point=partition(a,low,high);//对基准点定位     
       //对基准点左边进行递归调用   
       QSort(a,low,point-1);    
       //对基准点右边进行递归调用
       QSort(a,point+1,high);   
     }  
    }   
    
    
    //外层函数，由于快速排序需要三个参数，为零满足只要两个参数，定义一个外层函数调用实际操作的函数    
    void QuickSort(int a[],int len)     
    {   
      //调用实际操作的函数   
      QSort(a,0,len-1);   
    }  
    
    
    
    
    void main()  
    {  
    
    int a[7]={49,38,65,97,76,13,27}; //这里对8个元素进行排序  
        int low=0,high=6;  //初始化low和high的值
    int shuzu1[1000];
    int shuzu2[1000];
    int i;
    int count;
       //定义两个结构体，来记录开始和结束时间
        clock_t start, finish;
    // unsigned  long diff;
      double  duration;
      FILETIME beg,end;
      long dur;
    LARGE_INTEGER litmp;
       LONGLONG Qpart1,Qpart2;
       double dfMinus,dfFreq,dfTime;
       /* 测量一个事件持续的时间*/
    
    srand(time(0));
    // count = 100;
    for(count = 100; count < 1001; count = count + 100)
    {
    low = 0;
    high = count - 1;
    for(i=0;i<count;i++)
    {
    shuzu1[i] = rand()%10000+1;
    shuzu2[i] = shuzu1[i];
    //  printf("%3d ",shuzu2[i]);
    }
    
    
       QueryPerformanceFrequency(&litmp);
       dfFreq = (double)litmp.QuadPart;
       QueryPerformanceCounter(&litmp);
       Qpart1 = litmp.QuadPart; //开始计时
    
    
    MergeSort(shuzu1,low,high); 
    
    
      QueryPerformanceCounter(&litmp);
      Qpart2 = litmp.QuadPart; //终止计时
      dfMinus = (double)(Qpart2 - Qpart1);//计算计数器值
      dfTime = dfMinus / dfFreq * 1000000;//获得对应时间，单位为秒 你可以乘1000000精确到毫秒级（us）
    
    
    
    
    
    
       printf( "Mergesort %d array所用时间：%lf us\n", count,dfTime );
          QueryPerformanceFrequency(&litmp);
       dfFreq = (double)litmp.QuadPart;
       QueryPerformanceCounter(&litmp);
       Qpart1 = litmp.QuadPart; //开始计时
    
    
       QuickSort(shuzu2,count);
    
    
         QueryPerformanceCounter(&litmp);
      Qpart2 = litmp.QuadPart; //终止计时
      dfMinus = (double)(Qpart2 - Qpart1);//计算计数器值
      dfTime = dfMinus / dfFreq * 1000000;//获得对应时间，单位为秒 你可以乘1000000精确到毫秒级（us）
        printf( "Quicksort %d array所用时间：%lf us\n", count,dfTime );
    for(i=0;i<count;i++)
    {
    //shuzu1[i] = rand()%10000+1;
    // printf("%3d ",shuzu2[i]);
     
    }
    // diff = 1000000 * (end.tv_sec-start.tv_sec)+ end.tv_usec-start.tv_usec;
     //        printf(“thedifference is %ld\n”,diff);
    printf("\n");
    }
         
    /*
      
        MergeSort(a,low,high);  
      
        printf("After merge sort:  ");  
        for( i=low;i<=high;i++)  
        {  
            printf("%d ",a[i]);             //输出测试  
        }  
        printf("\n");  
    */
    
    }

结果：

![20171024164637721][]

[20171024164637721]: /images/20220606/1f91d2f320b4460f9cf159e164ed49fc.png