排序算法---归并排序

桃扇骨 2022-03-11 06:16 303阅读 0赞

归并排序的基本思路是江两个有序的系列合并，成为一个新的有序序列。

首先考虑如何合并两个有序序列：

//两个有序数组合并 
    void mergSortArray(int a[] ,int n,int b[],int m ,int c[]){
    	int i,j,k;
    	i = j = k = 0;
    	while(i<n&&j<m){
    		if(a[i]<b[j]){
    			c[k++] = a[i++];
    		}else{
    			c[k++] = b[j++];
    		}
    	}
    	while(i<n){
    		c[k++] = a[i++];
    	}
    	while(j<m){
    		c[k++] = b[j++];
    	}
    }

以上合并有序序列效率还是比较高的，可以达到O(n)。

解决了两个有序的序列的合并，再来看看归并排序。

其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先**递****归**的分解数列，再**合****并**数列就完成了**归并**排序

下面是c语言实现：

#include <stdio.h>
    
    //一个数组 条件（mid两边有序） 合并 
    void mergSortArray(int a[] ,int first ,int mid,int last ,int temp[]){
    	int i = first;
    	int m = mid;
    	int j = mid+1;
    	int n = last;
    	int k = 0;
    	while(i<=m&&j<=n){
    		if(a[i]<a[j]){
    			temp[k++] = a[i++];
    		}else{
    			temp[k++] = a[j++];
    		}
    	}
    	while(i<=m){
    		temp[k++] = a[i++];
    	}
    	while(j<=n){
    		temp[k++] = a[j++];
    	}
    	for( int i = 0;i<k;i++){
    		a[first +i ] = temp[i];
    	}
    }
    
    //归并排序 先递归把 数组分成只有一段 然后在执行 合并mergSortArray（） 方法 
    void mergeSort(int a[] ,int first,int last,int temp[]){
    	if(first<last){
    		int mid = (first + last) /2;
    		mergeSort(a,first,mid,temp);
    		mergeSort(a,mid+1,last,temp);
    		mergSortArray(a,first,mid,last,temp);
    	}
    }
    
    void print(int a[] ,int n)
    {
        for (int i = 0;i<n;i++)
        {
            printf("%d  ",a[i]);
        }  
        printf("\n");
    }
    int main(int argc, char *argv[])
    {
    	int a[]={
    		0,59,48,75,98,86,23,37,60
    	};
    	print(a,9);
    	int *temp = new int[8];
    	mergeSort(a,1,8,temp);
    	print(a,9);
    	print(temp,8);
    	return 0;
    }