main.cpp

实现数据结构的归并排序

#include <cstdlib>
#include <iostream>
#include <cmath>
#include <iomanip>
#include "Timer.h"
#include <stdlib.h>
#include <time.h>

using namespace std;

int counter1=0,counter2=0;

void Merge(int* R,int low,int mid,int high)
{
     int* R1;
     int i=low,j=mid+1,k=0;
     R1=(int*)malloc((high-low+1)*sizeof(int));
     
     while(i<=mid&&j<=high)
         if(R[i]<=R[j])
         {
             counter1++;
             R1[k]=R[i];
             counter2++;
             i++;k++;
         }
         else
         {
             counter1++;
             R1[k]=R[j];
             counter2++;
             j++;k++;
         }
     while(i<=mid)
     {
         R1[k]=R[i];
         counter2++;
         i++;k++;
     }
     while(j<=high)
     {
         R1[k]=R[j];
         counter2++;
         j++;k++;
     }
     for(k=0,i=low;i<=high;k++,i++)
     {
         R[i]=R1[k];
         counter2++;
     }
}

void MergePass(int* R,int length,int n)
{
     int i;
     for(i=0;i+2*length-1<n;i=i+2*length)
         Merge(R,i,i+length-1,i+2*length-1);
     if(i+length-1<n)
         Merge(R,i,i+length-1,n-1);
}

void MergeSort(int* R,int n)
{
     int length;
     for(length=1;length<n;length=2*length)
         MergePass(R,length,n);
}
     
int main()
{
    int num[10000];
    
    srand(time(NULL));
    
    for(int i=0;i<=9999;i++)
        num[i]=1+rand()%1000;
    
    Timer timer;
    
    timer.start();
    
    MergeSort(num,10000);
    
    timer.stop();
    double clock=timer.seconds();
    timer.reset();
    
    for(int i=0;i<=9999;i++)
        cout<<setw(6)<<num[i];
        
    cout<<endl<<endl;
    
    cout<<"程序运行时间为："<<clock<<'s'<<endl; 
    cout<<"键值比较次数为："<<counter1<<endl;
    cout<<"键值交换次数为："<<counter2<<endl; 
    
    system("pause");
    return 0;
}