网站流量增加,php 网站开发360,虾皮跨境电商平台入驻,三亚门户网站一、什么是归并排序
1、整体是递归#xff0c;左边排好序右边排好序merge让整体有序 2、让其整体有序的过程里用了排外序方法 3、利用master公式来求解时间复杂度 4、当然可以用非递归实现
二、归并排序说明
1、首先有一个f函数 void f(arr, L, R) 说明#xff1a;在arr上…一、什么是归并排序
1、整体是递归左边排好序右边排好序merge让整体有序 2、让其整体有序的过程里用了排外序方法 3、利用master公式来求解时间复杂度 4、当然可以用非递归实现
二、归并排序说明
1、首先有一个f函数 void f(arr, L, R) 说明在arr上从L到R范围上让它变成有序的
2、递归调用
1先f(L, M)之间有序 2f(M1, R)之间有序 3变成整体有序
左边是2、3、5右边是056 准备一个一样长的辅助空间然后左指针指向2右指针指向0谁小拷贝谁 然后右边的指针往后移再次比较2和5谁小拷贝谁以此类推
4整体有序后再把这一块空间刷回去
三、代码
package class03;public class Code01_MergeSort {/*** 变成整体有序* param arr* param L 数组下标* param M 数组下标* param R 数组下标*/public static void merge(int[] arr, int L, int M, int R) {int [] help new int[R - L 1];int i 0;int p1 L;int p2 M 1;while (p1 M p2 R) {help[i] arr[p1] arr[p2] ? arr[p1] : arr[p2];}//要么p1越界了要么p2越界了//看左边小于等于Mwhile (p1 M) {help[i] arr[p1];}//还是右边小于等于Rwhile (p2 R) {help[i] arr[p2];}for (i 0; i help.length; i) {arr[L i] help[i];}}/*** 递归方法实现* arr[L...R]范围上变成有序* param arr*/public static void mergeSort1(int[] arr) {if (arr null || arr.length 2) {return;}process(arr, 0, arr.length - 1);}public static void process(int[] arr, int L, int R) {if (L R) { // base casereturn;}int mid L ((R - L) 1);process(arr, L, mid);process(arr, mid 1, R);merge(arr, L, mid, R);}/*** 非递归方法实现* param arr*/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;if (M N) {break;}int R Math.min(M mergeSize, N - 1);merge(arr, L, M, R);L R 1;}if (mergeSize N / 2) { //防止溢出break;}mergeSize 1; //左移后赋值相当于乘2后赋值}}public static void main(String[] args) {int[] aaa {99, 100, 50, 70, 88, 10, 9, 35, 1, 98};int[] bbb {99, 100, 50, 70, 88, 10, 9, 35, 1, 98};mergeSort1(aaa);for (int i: aaa) {System.out.print(i );}System.out.println();mergeSort2(bbb);for (int i: bbb) {System.out.print(i );}System.out.println();}
}1递归说明
2非递归说明
原理 k2 相邻两个数之间merge在一起 k4 四个数一组merge在一起 ... 一直到k到达N或者超过N
回到代码代码中mergeSize就是k外层while循环 N 10 mergeSize 1 L 0 内层while循环 M 0 R 1 merge(arr, 0, 0, 1) L 2 M 2 R 3 merge(arr, 2, 2, 3) L 4 M 4 R 5 merge(arr, 4, 4, 5) L 6 ...
然后mergeSize变成2变成4...
四、归并排序复杂度
T(N)2*T(N/2)O(N^1) 根据master可知时间复杂度为O(N*logN) merge过程需要辅助数组所以额外空间复杂度为O(N) 归并排序的实质是把比较行为变成了有序信息并传递比O(N^2)的排序快
