前言:
当前朋友们对“归并排序 空间复杂度”大体比较关怀,兄弟们都需要剖析一些“归并排序 空间复杂度”的相关文章。那么小编同时在网摘上收集了一些有关“归并排序 空间复杂度””的相关文章,希望姐妹们能喜欢,大家一起来学习一下吧!什么是归并排序
归并,就是合并的意思。通俗的说就是把两部分合并成一部分。
归并排序的步骤
归并排序(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),比选择排序性能要好,但是代价是需要额外的空间。
标签: #归并排序 空间复杂度 #归并排序空间复杂度比较小吗