龙空技术网

排序算法之归并排序

愁的慌 184

前言:

当前朋友们对“归并排序 空间复杂度”大体比较关怀,兄弟们都需要剖析一些“归并排序 空间复杂度”的相关文章。那么小编同时在网摘上收集了一些有关“归并排序 空间复杂度””的相关文章,希望姐妹们能喜欢,大家一起来学习一下吧!

什么是归并排序

归并,就是合并的意思。通俗的说就是把两部分合并成一部分。

归并排序的步骤

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

具体步骤如下:

1、将给定的序列,从中间分成两个子序列,然后再将子序列以同样的方式拆分子序列,直到子序列长度为1,也就是称为有序序列。

2、申请额外的空间,为两个子序列长度和,用于存放合并后的序列。然后设定两个指针分别指向两个有序子序列的起始位置,然后比较两个指针指向元素的大小,将较小的元素放入合并空间,并移动指向该元素的指针,另外一个子序列的指针不变,然后继续比较两个指针指向元素的大小,直到两个有序子序列中的值全部放入合并空间中。

3、自下而上的合并所有的子序列,直到合并完所有的子序列之后,合并空间中的序列即为有序序列。

以图为例:

假设给定的初始序列如下所示:


首先,将给定的无序序列二分,结果如下:


然后自下而上的,合并每两个子序列,过程如图所示:

第一次比较:


以第一组为例,两个子序列分别为[4]和[5],设定两个指针分别指向这两个有序序列的起始位置,然后进行比较,4<5,所以将较小的4先放入合并空间里,然后移动该序列的指针,因为已经到末尾了,所以,直接把另外一个序列的元素挨个追加到合并空间,即将5追加到合并空间后边。

然后,继续归并:


仍然以第一组为例,两个有序子序列分别为[4,5]和[2,8],设定两个指针分别指向4和2,2<4,所以先把2放入合并空间,移动指针指向8,4<8,再把4放入合并空间,移动指针,指向5,5<8,再把5放入合并空间,指针已经到达末尾,所以,将8追加到合并空间,完成归并。

最后一次归并结果如下:


至此,归并完毕。

代码实现

public class MergeSort { 	public static int[] mergeSort(int[] arr) {		if (arr == null || arr.length < 2) {			return arr;		}		// 找出当前序列的中间位置		int middle = (int)Math.floor(arr.length / 2);		// 将序列分隔成两部分		int[] left = Arrays.copyOfRange(arr, 0, middle);		int[] right = Arrays.copyOfRange(arr, middle, arr.length);		// 合并两部分序列,拆分序列,直到每一部分只剩下一个元素,然后合并。递归		return merge(mergeSort(left), mergeSort(right));	} 	private static int[] merge(int[] left, int[] right) {		int[] result = new int[left.length + right.length];		int i = 0;		while (left.length > 0 && right.length > 0) {			if (left[0] <= right[0]) {				result[i++] = left[0];				left = Arrays.copyOfRange(left, 1, left.length);			} else {				result[i++] = right[0];				right = Arrays.copyOfRange(right, 1, right.length);			}		}		while (left.length > 0) {			result[i++] = left[0];			left = Arrays.copyOfRange(left, 1, left.length);		}		while (right.length > 0) {			result[i++] = right[0];			right = Arrays.copyOfRange(right, 1, right.length);		}		return result;	}}
复杂度分析

因为归并排序的性能不受初始数据的影响,不管初始数据是否已经排序或者完全倒序,归并排序的时间复杂度都是O(nlogn),比选择排序性能要好,但是代价是需要额外的空间。

标签: #归并排序 空间复杂度 #归并排序空间复杂度比较小吗