归并排序以及Master公式

归并排序以及Master公式
文章图片

一、概念 归并排序(Merge Sort)是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。
二、排序过程 1、归并操作,指的是将两个顺序序列合并成一个顺序序列的方法。
如:数组 {6,202,100,301,38,8,1}
初始状态:6,202,100,301,38,8,1
第一次归并后:{6,202},{100,301},{8,38},{1};
第二次归并后:{6,100,202,301},{1,8,38};
第三次归并后:{1,6,8,38,100,202,301};
2、归并操作步骤如下:
【归并排序以及Master公式】(1)申请空间,大小为两个已经排好序的序列之和,该空间用来做辅助数组
(2)设定两个指针,最初位置分别为两个已经排序序列的起始位置
(3)比较两个指针所指向的元素,选择相对小的元素放入到合并空间(相等选择左组),并移动指针到下一位置。
重复步骤3直到某一指针越界。将另一序列剩下的所有元素直接复制到合并序列(辅助数组)尾,将辅助数组数据拷贝回原数组。
三、Master公式估计时间复杂度 Master公式:分析递归函数的时间复杂度,要求子问题规模一致

形如:
T(N) = a * T(N/b) + O(N^d)(其中a、b、d都是常数)的递归函数,可以直接通过Master公式来确定时间复杂度
1)如果log(b,a) < d,时间复杂度为O(N^d)
2)如果log(b,a) > d,时间复杂度为O(N^log(b,a))
3)如果log(b,a) == d,时间复杂度为O(N^d * logN)
根据Master公式可得 T(N) =2 * T(N/2) + O(N)
因为每次都是拆分为两个子问题,每个子问题占总规模的一半,且合并过程的时间复杂度是O(N)
可得归并排序的时间复杂度是O(N*logN)。
四、代码实现 1、递归方法实现
/** * 1.递归方法实现 */ public static void mergeSort1(int[] arr) { if (arr == null || arr.length < 2) { return; } process(arr, 0, arr.length - 1); }private static void process(int[] arr, int l, int r) { if (l == r) { return; } int mid = l + ((r - l) >> 1); // 左组递归 process(arr, l, mid); // 右组递归 process(arr, mid + 1, r); // 合并 merge(arr, l, mid, r); }private static void merge(int[] arr, int l, int m, int r) { // 辅助数组 int[] help = new int[r - l + 1]; int i = 0; // 左组位置 int pL = l; // 右组位置 int pR = m + 1; while (pL <= m && pR <= r) { // 谁小拷贝谁,相等的拷贝左组 help[i++] = arr[pL] <= arr[pR] ? arr[pL++] : arr[pR++]; } // pL和pR有且只有一个会越界,也就是下面两个while只有一个会执行 while (pL <= m) { help[i++] = arr[pL++]; } while (pR <= r) { help[i++] = arr[pR++]; } // 拷贝回原数组 for (int j = 0; j < help.length; j++) { arr[l + j] = help[j]; } }

2、迭代方式实现
定义一个步长,初始值为1。从0位置的数开始,每两个步长的数merge完后拷贝回原数组,步长*2;再从0位置的数开始,每两个步长的数merge完后拷贝回原数组,步长*2……直到(步长 > 数组长度 / 2)
/** * 2.迭代方式实现归并排序 * * 步长调整次数 复杂度是logN,每次调整步长都会遍历一遍整个数组 复杂度是N,整个的时间复杂度是O(N*logN) */ public static void mergeSort2(int[] arr) { if (arr == null || arr.length < 2) { return; } int N = arr.length; // 步长初始值 int mergeSize = 1; // 步长不能超过数组长度 while (mergeSize < N) { // 当前左组的第一个位置 int L = 0; // 左组也不能超过数组长度 while (L < N) { // 左组最后一个位置 int M = L + mergeSize - 1; // 如果左组最后一个位置越界,表明左组都不够则不需要merge if (M >= N) { break; }// 右组的最后一个位置 // 右组第一个位置是 M + 1,满足个数要求则右组大小是mergeSize,所以最后一个位置是 (M + 1) + mergeSize - 1 // 不满足则是数组的最大位置 N - 1 int R = Math.min(M + mergeSize, N - 1); // 目前 左组:L......M,右组:M+1......R merge(arr, L, M, R); // 下一次左组的位置(所以才需要判断L < N) L = R + 1; }// 防止溢出 // 当步长很靠近N的最大值时,乘以2扩大步长后,步长就溢出了 // 不能取 >=,假设最大值是9,mergeSize = 4时就不会扩大步长了,但是mergeSize = 8时还有一次merge,所以不能取 = if (mergeSize > N / 2) { break; }// 步长每次扩大2倍 mergeSize <<= 1; }}

    推荐阅读