ShiYu

# 第4节 归并排序及其相关面试题

# 归并排序

  • 整体是递归，左边排好序+右边排好序+merge让整体有序
  • 让其整体有序的过程里用了排外序方法
  • 利用master公式来求解时间复杂度
  • 当然可以用非递归实现

# 归并排序复杂度

T(N) = 2*T(N/2) + O(N^1)

根据master可知时间复杂度为O(N*logN)

merge过程需要辅助数组，所以额外空间复杂度为O(N)

归并排序的实质是把比较行为变成了有序信息并传递，比O(N^2)的排序快

# 归并排序递归版本与非递归版本实现

package class04;

/**
 * 	归并排序算法练习
 * @author yangyanchao
 *
 */
public class Test01_MergeSort {
	/**
	 * 	归并排序递归版本的
	 */
	public static void mergeSortByRecursion(int[] arr) {
		if(arr == null || arr.length == 0) {
			return ;
		}
		// arr 在0....N-1上排序
		process(arr, 0, arr.length - 1);
	}

	/**
	 * 	递归函数
	 * 	实现左边有序再实现右边有序 然后合并操作
	 * 	T(N) = 2 * T(N / 2) + O(N)
	 * 	O(N * logN)
	 * @param arr
	 * @param L
	 * @param R
	 */
	private static void process(int[] arr, int L, int R) {
		if (L == R) { // base case
			return;
		}
		int middle = L + ((R - L) >> 1);
		process(arr, L, middle);
		process(arr, middle + 1, R);
		merge(arr, L, middle, R);
	}

	/**
	 * 	合并函数
	 * @param arr
	 * @param L
	 * @param M
	 * @param R
	 */
	private 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至少有一个先溢出
		while(p1 <= M) {
			// p2先溢出
			help[i++] = arr[p1++];
		}
		while(p2 <= R) {
			// p1先溢出
			help[i++] = arr[p2++];
		}
		// copy
		for(i = 0; i < help.length; i++) {
			arr[L + i] = help[i];
		}
	}
	
	/**
	 * 	归并排序非递归版本的
	 */
	public static void mergeSortNonRecursion(int[] arr) {
		if(arr == null || arr.length == 0) {
			return ;
		}
		int setp = 1;
		int len = arr.length;
		while(setp < len) {
			int L = 0;
			while(L < len) {
				if(setp >= (len - L)) {
					break;
				}
				int M = L + setp - 1;
				int R = M + Math.min(setp, len - M - 1);
				L = R + 1;
			}
			// 防止数值溢出
			if(setp > (len >> 1)) {
				break;
			}
			setp <<= 1;
		}
	}
	
	// for test
		public static int[] generateRandomArray(int maxSize, int maxValue) {
			int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
			for (int i = 0; i < arr.length; i++) {
				arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
			}
			return arr;
		}

		// for test
		public static int[] copyArray(int[] arr) {
			if (arr == null) {
				return null;
			}
			int[] res = new int[arr.length];
			for (int i = 0; i < arr.length; i++) {
				res[i] = arr[i];
			}
			return res;
		}

		// for test
		public static boolean isEqual(int[] arr1, int[] arr2) {
			if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
				return false;
			}
			if (arr1 == null && arr2 == null) {
				return true;
			}
			if (arr1.length != arr2.length) {
				return false;
			}
			for (int i = 0; i < arr1.length; i++) {
				if (arr1[i] != arr2[i]) {
					return false;
				}
			}
			return true;
		}

		// for test
		public static void printArray(int[] arr) {
			if (arr == null) {
				return;
			}
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i] + " ");
			}
			System.out.println();
		}

		// for test
		public static void main(String[] args) {
			int testTime = 500000;
			int maxSize = 100;
			int maxValue = 100;
			System.out.println("测试开始");
			for (int i = 0; i < testTime; i++) {
				int[] arr1 = generateRandomArray(maxSize, maxValue);
				int[] arr2 = copyArray(arr1);
				mergeSortByRecursion(arr1);
				mergeSortNonRecursion(arr2);
				if (!isEqual(arr1, arr2)) {
					System.out.println("出错了！");
					printArray(arr1);
					printArray(arr2);
					break;
				}
			}
			System.out.println("测试结束");
		}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

# 常见面试题1

在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。 例子：[1,3,4,2,5] 1左边比1小的数：没有 3左边比3小的数：1 4左边比4小的数：1、3 2左边比2小的数：1 5左边比5小的数：1、3、4、 2 所以数组的小和为1+1+3+1+1+3+4+2=16

转化思路：求解右组中有多少个比左组上的数X大

例如：[1,3,4,6|2,3,5,8]

当左指针p1来到数组0位置时 比较右组中有多少个数比1大

划分两组分为左组与右组，定义左组指针指向的当前左边数X，右组指针指向的当前右边数Y

若X<Y，那么X向后移动，并产生小和。

若X>Y，那么Y向后移动，不产生小和。

若X==Y，那么Y向后移动，不产生小和。

package class04;

/**
 * 	数组小和问题
 * 	在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和。
 * @author yangyanchao
 *
 */
public class Test02_SmallSum {
	
	/**
	 * 	使用归并排序求解数组小和问题
	 * 	时间复杂度为O(N*LogN)
	 * @param arr
	 * @return
	 */
	public static int smallSum(int[] arr) {
		if(arr == null || arr.length < 2) {
			return 0;
		}
		return process(arr, 0, arr.length - 1);
	}
	
	/**
	 * 	递归调用 求解数组小和问题
	 * @param arr
	 * @param L
	 * @param R
	 * @return
	 */
	private static int process(int[] arr, int L, int R) {
		if(L == R) { // base case
			return 0;
		}
		int M = L + ((R - L) >> 1);
		return process(arr, L, M) 
				+ process(arr, M + 1, R) 
				+ merge(arr, L, M, R);
	}

	/**
	 * 	合并操作
	 * 	求解右组中有多少个比左组上的数X大
	 * 	划分两组分为左组与右组，定义左组指针指向的当前左边数X，右组指针指向的当前右边数Y
	 * 	若X<Y，那么X向后移动，并产生小和。
	 * 	若X>Y，那么Y向后移动，不产生小和。
	 * 	若X==Y，那么Y向后移动，不产生小和。
	 * @param arr
	 * @param L
	 * @param M
	 * @param R
	 * @return
	 */
	private static int 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;
		int ans = 0;
		while(p1 <= M && p2 <= R) {
			ans += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0 ;
			// 若是arr[p1]==arr[p2]复制右组数据
			help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
		}
		while(p1 <= M) {
			help[i++] = arr[p1++];
		}
		while(p2 <= R) {
			help[i++] = arr[p2++];
		}
		for(i = 0; i < help.length; i++) {
			arr[L + i] = help[i];
		}
		return ans;
	}

	/**
	 * 	比对函数
	 * @param arr
	 * @return
	 */
	public static int comparator(int[] arr) {
		if(arr == null || arr.length < 2) {
			return 0;
		}
		int ans = 0;
		for(int i = 1; i < arr.length; i++) {
			for(int j = 0; j < i; j++) {
				ans += arr[j] < arr[i] ? arr[j] : 0;
			}
		}
		return ans;
	}
	
	public static void main(String[] args) {
		int maxTimes = 500000;
		int maxSize = 5;
		int maxValue = 5;
		boolean suecced = true;
		for(int i = 0; i < maxTimes; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			int res1 = smallSum(arr1);
			int res2 = comparator(arr2);
			if(res1 != res2) {
				suecced = false;
				printArray(arr1);
				printArray(arr2);
				System.out.println("smallSum:" + res1);
				System.out.println("compare:" + res2);
				break;
			}
		}
		System.out.println(suecced ? "Nice." : "ooVoo." );
	}

	/**
	 * 	打印数组
	 * @param arr1
	 */
	private static void printArray(int[] arr1) {
		if(arr1 == null) {
			return;
		}
		System.out.print("{ ");
		for(int num : arr1) {
			System.out.print(num + " ");
		}
		System.out.println("}");
	}

	/**
	 * 	复制数组
	 * @param arr1
	 * @return
	 */
	private static int[] copyArray(int[] arr1) {
		if(arr1 == null) {
			return null;
		}
		int[] arr2 = new int[arr1.length];
		for(int i = 0; i < arr1.length; i++) {
			arr2[i] = arr1[i];
		}
		return arr2;
	}

	/**
	 * 	生成长度及数值随机的数组
	 * @param maxSize
	 * @param maxValue
	 * @return
	 */
	private static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int)( (maxSize+1) * Math.random() )];
		for(int i = 0; i < arr.length; i++) {
			arr[i] = (int)( ((maxSize+1) * Math.random())  - (maxSize * Math.random()) );
		}
		return arr;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

# 常见面试题2

在一个数组中， 任何一个前面的数a，和任何一个后面的数b， 如果(a,b)是降序的，就称为逆序对 返回数组中所有的逆序对

转化思路：求解右组中有多少个比左组上的数X小

例如：[1,3,4,6 | 2,3,5,8]

定义L、M、R

定义p1在M位置上，定义p2在R位置上

划分两组分为左组与右组，定义左组指针指向的当前左边数X，右组指针指向的当前右边数Y

若X<Y，那么X向前移动，并不产生相加。

若X>Y，那么Y向前移动，产生相加。

若X==Y，那么Y向前移动，不产生相加。

package class04;

/**
 * 	逆序对问题
 * 	在一个数组中，
 * 	任何一个前面的数a，和任何一个后面的数b，
 * 	如果(a,b)是降序的，就称为逆序对
 * 	返回数组中所有的逆序对
 * 	转化思路：求解右组中有多少个比左组上的数X小
 * @author yangyanchao
 *
 */
public class Test03_ReversePair {
	/**
	 * 	比对函数
	 * @param arr
	 * @return
	 */
	public static int comparator(int[] arr) {
		if(arr == null || arr.length < 2) {
			return 0;
		}
		int ans = 0;
		for(int i = 1; i < arr.length; i++) {
			for(int j = 0; j < i; j++) {
				ans += arr[j] > arr[i] ? 1 : 0;
			}
		}
		return ans;
	}
	/**
	 * 	返回数组中所有的逆序对
	 * 	转化思路：求解右组中有多少个比左组上的数X大
	 * @param arr
	 * @return
	 */
	public static int reversePair(int[] arr) {
		if(arr == null || arr.length < 2) {
			return 0;
		}
		return process(arr, 0, arr.length - 1);
	}
	
	/**
	 * 	递归调用 划分左组与右组 然后合并操作
	 * @param arr
	 * @param L
	 * @param R
	 * @return
	 */
	private static int process(int[] arr, int L, int R) {
		if(L == R) { // base case
			return 0;
		}
		int M = L + ((R - L) >> 1);
		return process(arr, L, M)
				+ process(arr, M + 1, R)
				+ merge(arr, L, M, R);
	}
	
	/**
	 * 	合并操作
	 * 	比对右组中有多少个比左组的数小
	 * 	定义ans = 0   p1 = M, p2 = R
	 * 	arr[p1] > arr[p2]     需要相加 并且p1向前移动
	 * 	arr[p1] <= arr[p2]   不需要相加  并且p2向前移动
	 * @param arr
	 * @param L
	 * @param M
	 * @param R
	 * @return
	 */
	private static int merge(int[] arr, int L, int M, int R) {
		int[] help = new int[R - L + 1];
		int i = help.length - 1;
		int ans = 0;
		int p1 = M;
		int p2 = R;
		while(p1 >= L && p2 > M) {
			ans += arr[p1] > arr[p2] ? (p2 - M) : 0 ;
			help[i--] = arr[p1] > arr[p2] ? arr[p1--] : arr[p2--];
		}
		while (p1 >= L) {
			help[i--] = arr[p1--];
		}
		while (p2 > M) {
			help[i--] = arr[p2--];
		}
		for (i = 0; i < help.length; i++) {
			arr[L + i] = help[i];
		}
		return ans;
	}
	
	public static void main(String[] args) {
		int maxTimes = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succed = true;
		for(int i = 0; i < maxTimes; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			int ans1 = reversePair(arr1);
			int ans2 = comparator(arr2);
			if(ans1 != ans2) {
				succed = false;
				printArray(arr1);
				printArray(arr2);
				System.out.println("reversePair:" + ans1);
				System.out.println("comparator:" + ans2);
			}
		}
		System.out.println(succed ? "Nice." : "ooVoo." );
	}
	/**
	 * 	打印数组
	 * @param arr1
	 */
	private static void printArray(int[] arr1) {
		if(arr1 == null) {
			return;
		}
		System.out.print("{ ");
		for(int i = 0; i < arr1.length; i++) {
			if(i != 0) {
				System.out.print(", ");
			}
			System.out.print(arr1[i]);
		}
		System.out.println("}");
	}
	/**
	 * 	复制数组
	 * @param arr1
	 * @return
	 */
	private static int[] copyArray(int[] arr1) {
		if(arr1 == null) {
			return null;
		}
		int[] arr2 = new int[arr1.length];
		for(int i = 0; i < arr1.length; i++) {
			arr2[i] = arr1[i];
		}
		return arr2;
	}
	/**
	 * 	生成长度及数值随机的数组
	 * @param maxSize
	 * @param maxValue
	 * @return
	 */
	private static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int)( (maxSize + 1) * Math.random())];
		for(int i = 0; i < arr.length; i++) {
			arr[i] = (int)( ((maxValue + 1) * Math.random()) - (maxValue * Math.random()) );
		}
		return arr;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

# 常见面试题3

在一个数组中， 对于每个数num，求有多少个后面的数 * 2依然<num，求总个数 比如：[3,1,7,0,2] 3的后面有：1，0 1的后面有：0 7的后面有：0，2 0的后面没有 2的后面没有 所以总共有5个

思路：求解右组中有多少个数乘以2比左组上的数X小

例如：[1,3,4,6 | 2,3,5,8]

定义L、M、R

定义p1在L位置上，定义p2在M+1位置上

划分两组分为左组与右组，定义左组指针指向的当前左边数X，右组指针指向的当前右边数Y

若X>Y*2，那么Y向后移动，加p2-M-1个。

反之，Y向前移动，不需加入

package class04;

/**
 * 	大于俩倍问题
 * 	在一个数组中，
 * 	对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数
 * @author yangyanchao
 *
 */
public class Test04_BiggerThanRightTwice {
	
	/**
	 * 	在一个数组中，
	 * 	对于每个数`num`，求有多少个后面的数 `* 2 `依然`<num`，求总个数
	 * 	O(N*LogN)
	 * @param arr
	 * @return
	 */
	public static int biggerThanRightTwice(int[] arr) {
		if(arr == null || arr.length < 2) {
			return 0;
		}
		return process(arr, 0, arr.length - 1);
	}
	
	/**
	 * 	递归过程
	 * 	划分左右俩组 在每个组中找出个数 在合并操作
	 * @param arr
	 * @param L
	 * @param R
	 * @return
	 */
	private static int process(int[] arr, int L, int R) {
		if(L == R) { // base case
			return 0;
		}
		// 防止int类型溢出
		int M = L + ((R - L) >> 1);
		int leftPart = process(arr, L, M);
		int rightPart = process(arr, M + 1, R);
		int mergePart = merge(arr, L, M, R);
		return leftPart + rightPart + mergePart;
	}

	/**
	 * 	合并操作
	 * 	
	 * @param arr
	 * @param L
	 * @param M
	 * @param R
	 * @return
	 */
	private static int merge(int[] arr, int L, int M, int R) {
		int ans = 0;
		int windowR = M + 1;
		for(int i = L; i <= M; i++) {
			while(windowR <= R && arr[i] > (arr[windowR] << 1)) {
				windowR++;
			}
			ans += (windowR - M - 1);
		}
		// merge操作
		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++] ;
		}
		while(p1 <= M) {
			help[i++] = arr[p1++];
		}
		while(p2 <= R) {
			help[i++] = arr[p2++];
		}
		// copy操作
		for(i = 0; i < help.length; i++) {
			arr[L + i] = help[i];
		}
		return ans;
	}

	/**
	 * 	比对函数
	 * 	O(N^2)
	 * @param arr
	 * @return
	 */
	public static int comprator(int[] arr) {
		if(arr == null || arr.length < 2) {
			return 0;
		}
		int ans = 0;
		for(int i = 0; i < arr.length - 1; i++) {
			for(int j = i + 1; j < arr.length; j++) {
				ans += arr[i] > (arr[j] << 1) ? 1 : 0;
			}
		}
		return ans;
	}
	
	public static void main(String[] args) {
		int maxTimes = 500000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succed = true;
		for(int i = 0; i < maxTimes; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			int ans1 = biggerThanRightTwice(arr1);
			int ans2 = comprator(arr2);
			if(ans1 != ans2) {
				printArray(arr1);
				printArray(arr2);
				System.out.println("biggerThanRightTwice:"+ans1);
				System.out.println("comprator:"+ans2);
				succed = false;
				break;
			}
		}
		System.out.println(succed ? "Nice." : "ooVoo.");
	}

	/**
	 * 	打印数组
	 * @param arr1
	 */
	private static void printArray(int[] arr1) {
		if(arr1 == null) {
			return ;
		}
		System.out.print("{ ");
		for(int i = 0; i < arr1.length; i++) {
			if(i != 0) {
				System.out.print(", ");
			}
			System.out.print(arr1[i]);
		}
		System.out.println("}");
	}

	/**
	 * 	复制数组
	 * @param arr1
	 * @return
	 */
	private static int[] copyArray(int[] arr1) {
		if(arr1 == null) {
			return null;
		}
		int[] arr2 = new int[arr1.length];
		for(int i = 0; i < arr1.length; i++) {
			arr2[i] = arr1[i];
		}
		return arr2;
	}

	/**
	 * 	生成长度及数值随机的数组
	 * @return
	 */
	private static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int)((maxSize + 1) * Math.random())];
		for(int i = 0; i < arr.length; i++) {
			arr[i] = (int) (((maxValue + 1) * Math.random()) - (maxValue * Math.random()));
		}
		return arr;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

← 第5节 归并排序附加题、随机快速排序 →