mergesort.cpp

包含8种常用的排序。如快速排序

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream.h>
#include <algorithm>
using namespace std;
int E[10000];

void merge(int E[], int low, int mid, int high)
//将两个有序的子文件E[low..m)和E[m+1..high]归并成一个有序的子文件E[low..high]
{
     int i=low,j=mid+1,p=0;  //置初始值
     int E1[10000];
     while(i<=mid&&j<=high)  //两子文件非空时取其小者输出到E1[p]上
		 E1[p++]=(E[i]<=E[j])?E[i++]:E[j++];
     while(i<=mid)           //若第1个子文件非空，则复制剩余记录到E1中
       E1[p++]=E[i++];
     while(j<=high)         //若第2个子文件非空，则复制剩余记录到E1中
       E1[p++]=E[j++];
     for(p=0,i=low;i<=high;p++,i++)
       E[i]=E1[p];          //归并完成后将结果复制回E[low..high]
} 


void mergeSort(int E[], int first, int last)
 {
    int mid;
    if(first<last)
	{
        mid=(first+last)/2;
        mergeSort(E,first,mid);
        mergeSort(E,mid+1,last);
        merge(E,first,mid,last);
    }
    return;
}


void main() 
{   clock_t start=clock();/*程序开始运行的时间*/
    int i,N;

    printf("Please input N:");
    scanf("%d",&N);

    //srand((unsigned)time(NULL));//随时间的不同产生不同的随机数
    for(i=0;i<N;i++)
	{  
		E[i]=rand()%N+1;
    }

    printf("The %d nums is produced automatically:\n",N);
    for(i=0;i<N;i++)
        printf("%10d",E[i]);

    getch();
    mergeSort(E,0,N-1);

    printf("\nThe result after ordered:\n");
    for(i=0;i<N-1;i++)
        printf("%d->",E[i]);
	printf("%d\n",E[N-1]);

	clock_t end=clock();/*程序结束运行的时间*/
    cout<<"整个程序运行的时间为:";
    cout<<(end-start)<<"毫秒\n";
    getch();
}