常见的排序算法——归并排序

深碍√TFBOYSˉ_ 2022-05-17 10:25 159阅读 0赞

归并排序是建立在归并操作上的一种有效的排序[算法][Link 1]。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

归并排序 (merge sort) 是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。

如图所示：

![70][]

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

//将有序数组a[]和b[]合并到c[]中  
    void MemeryArray(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组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。

完整代码如下：

package wjw_99999;
    
    import java.util.Arrays;
    
    public class Merge_sort {
    	public static void main(String[] args) {  
    		  
            int[] nums = { 14,12,15,13,11,16};  
            System.out.println(Arrays.toString(nums));  
            sort(nums, 0, nums.length-1);  
            System.out.println(Arrays.toString(nums));  
        }
        
        /** 
         * 归并排序 
         * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，
         *     每个子序列是有序的。然后再把有序子序列合并为整体有序序列 
         * 时间复杂度为O(nlogn) 
         * 稳定排序方式 
         * @param nums 待排序数组 
         * @return 输出有序数组 
         */  
        public static int[] sort(int[] nums, int low, int high){
        	int mid = (low+high)/2;
        	if(low<high){
        		// 处理左边
        		sort(nums, low, mid);
        		// 处理右边
        		sort(nums, mid+1, high);
        		//合并左右
        		merge(nums, low, mid, high);
        		
        	}
        	return nums;
        }
        private static void merge(int[] nums, int low, int mid, int high) {
    	// 定义一个辅助数组，所以该算法的空间复杂度为O（n）
        	int[] temp = new int[high-low+1];
        	int i = low;
        	int j = mid+1;
        	int k = 0;
        	// 找出较小值元素放入temp数组中
        	while(i<=mid && j<=high){
        		if(nums[i]<nums[j])
        			temp[k++] = nums[i++];
        		else
        			temp[k++] = nums[j++];
        	}
        	// 有一边数组已为空，剩下的那个数组中的元素全部进入temp
        	while(i<=mid){
        		temp[k++] = nums[i++];
        	}
        	while(j<=high){
        		temp[k++] = nums[j++];
        	}
        	// 使用temp中的元素覆盖nums中元素
        	for (int t = 0; t < temp.length; t++) {
    			nums[t+low] = temp[t];
    		}
    	}
    
    }

[Link 1]: http://lib.csdn.net/base/datastructure
[70]: /images/20220517/60bb7aafdda5486fb2f40d958a90c381.png