几种排序方法的比较（选择、冒泡、归并、快排）_随机数比较冒泡排序 快速排序

代码：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
const int maxn = 50000;
 
//冒泡排序：
void bubble(int a[],int len){
	for(int i = 0;i < len-1;i++){
		for(int j = 0; j < len-i-1; j++){
			if(a[j] > a[j+1]){
				int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp;
			}
		}
	}
} 
 
//选择排序：
void select(int a[],int len){
	for(int i = 0 ; i < len-1; i++){
		int min = i;
		for(int j = i; j < len; j++){
			if(a[min] > a[j]){
				min = j;
			}
		}
		if(min != i){
			int temp = a[i]; a[i] = a[min]; a[min] = temp;
		}
	}
} 
 
 
//归并算法： 
void Merge(int a[],int b[],int left, int i ,int right){
     int j = 0;
	 int r = i+1;
	 int l = left;
	 int k;
	 int t;
	 while(l<=i && r<=right){
		 if(a[l] <= a[r]){
		    b[j++] = a[l++];
		 }else{
		    b[j++] = a[r++];
		 }
	 }
 
	 if(l<=i){
		 for(k = l; k <= i; k++){
		    b[j++] = a[k];
		 }
	 }
	 else if(r<=right){
		 for(k = r; k <= right; k++){
		     b[j++] = a[k];
		 }
	 }
 
	 //从b数组合并到a数组
 
	 j = 0;
     for(k = left; k <= right; k++){
	    a[k] = b[j++];
	 }
}
 
void MergeSort(int a[],int b[],int left,int right){
	int i;
	if(left < right){
	  i = (left+right)/2;
	  MergeSort(a,b,left,i);
	  MergeSort(a,b,i+1,right);
	  Merge(a,b,left,i,right); //合并
	}
} 
 
 
 
//快速排序： 
int Partition(int a[],int p,int r){
    int i = p;
	int j = r,x = a[p];
	while(i<j){
	  while(j>=p && a[j]>x)j--;
	  if(i < j){
	  	a[i++] = a[j];
	  }
	  while(i<=r && a[i]<x)i++;
	  if(i < j){
	  	a[j--] = a[i];
	  }
	}
      a[j] = x;
	return j;
}
 
 
void QuickSort(int a[],int p,int r){
	if(p<r){
	  int q = Partition(a,p,r);
	  QuickSort(a,p,q-1);
	  QuickSort(a,q+1,r);
	}
} 
 
 
int main(){
	int a[maxn] , b[maxn] , c[maxn];
	for(int i = 0; i < maxn; i++){ //产生随机数 
		a[i] = rand();
		c[i] = a[i];
	}
	
	double bstart = clock();
	bubble(a,maxn);
	double bend = clock();
	
	for(int i = 0; i < maxn; i++){  //保证每次排序的数据及顺序相同 
		a[i] = c[i];
	}
	double sstart = clock();
	select(a,maxn);
	double send = clock();
	
	for(int i = 0; i < maxn; i++){
		a[i] = c[i];
	}
	double qstart = clock();	
	QuickSort(a,0,maxn-1); 
	double qend = clock();
	
	for(int i = 0; i < maxn; i++){
		a[i] = c[i];
	}
	double mstart = clock();	
	MergeSort(a,b,0,maxn-1);
	double mend = clock();
	
//	for(int i = 0; i < 100; i++){ //测试排序是否正确 
//		printf("%d ",a[i]);
//	}
	printf("\n");
    printf("用冒泡、选择、快排、归并排序50000个随机数，时间复杂度做比较：\n"); 
    printf("冒泡排序所用时间：%.2lf\n",bend-bstart);
    printf("选择排序所用时间：%.2lf\n",send-sstart);
    printf("快速排序所用时间：%.2lf\n",qend-qstart);
    printf("归并排序所用时间：%.2lf\n",mend-mstart);
	return 0;
}

测试了一些数据，貌似归并是最快的，当然快排也不赖