排序 - 合并排序（4）

╰+攻爆jí腚メ 2022-01-12 06:55 189阅读 0赞

**概念**

合并排序是利用“合并”方法来进行排序。合并是将两个或多个有序表进行合并，得到一个有序表。该算法是采用分治算法（Divide and Conquer）的一个非常典型的应用。合并排序也叫归并排序。

**算法原理**

合并的思路是：只要比较各个有序表的第一个记录的键值，挑选最小的一个用于排序后的第一个记录的键值，取出这个记录存入排序结果表中。继续比较各个有序表的第一个记录的键值，挑选出键值最小者，最为排序后的第二个记录的键值，取出这个记录存入结果表中。如此继续下去只要进行一次扫描，就可得到排序结果，若只把两个有序表合并成一个有序表，称二路合并。

**排序演示**

设待排序的表中含有n个记录，则可看成是n个子表，每个表中只含一个记录，因而是有序的。通常将首位相接的两个子表进行合并，得到【n/2】个较大的有序子表，每个子表包含两个记录，称为一趟合并。再对这些有序子表两两进行合并，如此重复，直到最后合并成一个含有n个记录的有序表为止，排序完成。其中每步合并都采用二路合并，这种排序方法称为二路合并排序。类似地，可以此阿勇“三路合并排序”或“多路合并排序”。二路合并排序过程示例如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpZ3VhbmdfODIw_size_16_color_FFFFFF_t_70][]

**代码实现**

public static void mergeSort(int[] array) {
    		int length=array.length;
    		int middle=length/2;
    		if(length>1) {
    			int[] left=Arrays.copyOfRange(array, 0, middle);
    			int[] right=Arrays.copyOfRange(array, middle, length);
    			mergeSort(left);
    			mergeSort(right);
    			merge(array,left,right);
    		}
    	}
    	//合并数组，升序
    	private static void merge(int[] result,int[] left, int[] right) {
    		int i=0,l=0,r=0;
    		while(l<left.length&&r<right.length) {
    			if(left[l]<right[r]) {
    				result[i]=left[l];
    				i++;
    				l++;
    			}else {
    				result[i]=right[r];
    				i++;
    				r++;
    			}
    		}
    		while(r<right.length) {
    			result[i]=right[r];
    			i++;
    			r++;
    		}
    		while(l<left.length) {
    			result[i]=left[l];
    			i++;
    			l++;
    		}
    	}

**算法分析**

1.  时间复杂度
    
    > 最坏时间复杂度![b3119313b07eca8056ce3ede932397dda144833b.jpg][]，每次合并需要比较n次，需要合并log n次。  
    > 说明：  
    > n  
    > / \\  
    > n/2 n/2  
    > / \\ / \\  
    > n/4 n/4 n/4 n/4  
    > / \\ / \\ / \\ / \\  
    > n/8 n/8 n/8 n/8 n/8 n/8 n/8 n/8  
    > 树高logn,每层加起来都是n,一共是logn×n
    
    最好时间复杂度 ![3c6d55fbb2fb431699c0760b2aa4462308f7d3e0.jpg][]
    
    空间复杂度 ![0eb30f2442a7d9337c84e24aaf4bd11373f001de.jpg][]，因为合并的排序实现过程中，每趟合并将所有记录从一个数组移到另外一个数组中。
2.  算法复杂性  
    二路合并排序是稳定的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lpZ3VhbmdfODIw_size_16_color_FFFFFF_t_70]: /images/20220109/9cc33d7d19734595a6d9cc6cf9f9abc9.png
[b3119313b07eca8056ce3ede932397dda144833b.jpg]: https://gss3.bdstatic.com/-Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D69/sign=0ae48112b251f819f5250043dbb4bfb5/b3119313b07eca8056ce3ede932397dda144833b.jpg
[3c6d55fbb2fb431699c0760b2aa4462308f7d3e0.jpg]: https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D59/sign=2926689b8bcb39dbc5c0675fd1167059/3c6d55fbb2fb431699c0760b2aa4462308f7d3e0.jpg
[0eb30f2442a7d9337c84e24aaf4bd11373f001de.jpg]: https://gss0.bdstatic.com/-4o3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D33/sign=3124d6d4e51190ef05fb94dcce1b2048/0eb30f2442a7d9337c84e24aaf4bd11373f001de.jpg