几种排序方法的比较（选择、冒泡、归并、快排）

た入场券 2024-02-18 16:11 11阅读 0赞

代码：

#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;
    }

![Center][]

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

[Center]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/e5cfdd9337d9462f99c70613ddc13e8b.png