ShiYu

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

# 归并排序附加题(难)

题目描述： https://leetcode.com/problems/count-of-range-sum/ 给定一个数组arr，两个整数lower和upper， 返回数组arr中有多少个子数组的累加和在[lower,upper]范围上

归并排序(MergeSort)解题思路：

  1. 求数组arr[i]的前缀和数组sum[i]
  2. 原目标范围[lower,upper]-->>[x-upper,x-lower]
  3. 遍历sum[i]，假设sum[i-1]==x，求0-i之前的所有前缀和中有多少个前缀和在[x-upper,x-lower]上
  4. 归并排序，分组递归，然后merge()
  5. merge左右 不回退 要求O(N)merge() ==>>若[lower,upper]=[-1,2],sum[i] == [1,3,4,4,5,2,7,8,8,9]二分法分为俩组，左组[1,3,4,4,5]与右组[2,7,8,8,9]，对于右组第一个元素sum[5]==2的目标是左组中有多少个目标落在[2-upper,2-lower]，命中则ans++，否则不加，找出规律：sum[5]的目标[2-upper(0),2-lower(3)]<sum[6]的目标[7-upper(5),7-lower(8)]<sum[7]的目标[8-upper(6),8-lower(9)]<sum[8]的目标[8-upper(6),8-lower(9)]<sum[9]的目标[9-upper(7),9-lower(10)]
  6. 每个右组算出左组的范围下标为：windowL(左侧的范围下标)与windowR(下侧的范围下标) 不回退
package class05;

/**
 * 	给定一个数组arr，两个整数lower和upper，
 * 	返回数组arr中有多少个子数组的累加和在[lower,upper]范围上
 * 	这道题直接在leetcode测评：
 * 	https://leetcode.com/problems/count-of-range-sum/
 * @author yangyanchao
 *
 */
public class Test01_CountOfRangeSum {
	/**
	 * 	给定一个数组arr，两个整数lower和upper，
	 * 	返回数组arr中有多少个子数组的累加和在[lower,upper]范围上
	 * @param arr
	 * @param lower
	 * @param upper
	 * @return
	 */
	public static int countOfRangeSum(int[] arr, int lower, int upper) {
		if(arr == null || arr.length == 0) {
			return 0;
		}
		// 1、求解前缀和数组
		long[] sum = new long[arr.length];
		sum[0] = arr[0];
		for(int i = 1; i < arr.length; i++) {
			sum[i] = arr[i] + sum[i - 1];
		}
		// 2、前置知识 若sum数组上位置j的数值X 
		// 将目标[lower, upper] ==>> [X - upper, X - lower]
		// 3、归并排序 再merge操作
		return process(sum, 0, sum.length - 1, lower, upper);
	}

	/**
	 * 	归并排序 递归操作
	 * @param sum
	 * @param L
	 * @param R
	 * @return
	 */
	private static int process(long[] sum, int L, int R, int lower, int upper) {
		if(L == R) {
			// 需要单独判断一下 是否再此范围
			if(sum[L] >= lower && sum[L] <= upper) {
				return 1;
			} else {
				return 0;
			}
		}
		int M = L + ((R - L) >> 1);
		int leftPart = process(sum, L, M, lower, upper);
		int rightPart = process(sum, M + 1, R, lower, upper);
		int mergePart = merge(sum, L, M, R, lower, upper);
		return leftPart + rightPart + mergePart;
	}

	/**
	 * 	合并操作
	 * 	左组上的数X 与左组中的数Y 是否落在[Y - upper, Y - lower]
	 * 	发现规律-- 虽然每个数的指标不同但是lower与upper呈现递增趋势 
	 * 	定义windowsL指向lower窗口位置、windowsR指向upper窗口位置
	 * @param sum
	 * @param L
	 * @param M
	 * @param R
	 * @param lower
	 * @param upper
	 * @return
	 */
	private static int merge(long[] sum, int L, int M, int R, int lower, int upper) {
		int ans = 0;
		int windowsL = L; // lower 的窗口位置
		int windowsR = L; // upper 的窗口位置
		int index = M + 1;    // 当前右组比对的位置
		while(index <= R) {
			long lowerVar = sum[index] - upper; // 新的lower指标
			long upperVar = sum[index] - lower; // 新的upper指标
			while(windowsR <= M && sum[windowsR] <= upperVar) { 
				// 需要小于等于upperVar 为什么是等于 因为需要windowsR到最后一个等于值的范围
				windowsR++;
			}
			while(windowsL <= M && sum[windowsL] < lowerVar) { 
				// 需要小于lowerVar 为什么不加等于 因为需要windowsL到最后一个小于lowerVar的值的范围 不能加等于
				windowsL++;
			}
			ans += (windowsR - windowsL);
			index++;
		}
		// merge
		long[] help = new long[R - L + 1];
		int i = 0;
		int p1 = L;
		int p2 = M + 1;
		while(p1 <= M && p2 <= R) {
			help[i++] = sum[p1] < sum[p2]? sum[p1++] : sum[p2++];
		}
		while(p1 <= M) {
			help[i++] = sum[p1++];
		}
		while(p2 <= R) {
			help[i++] = sum[p2++];
		}
		// copy
		for(i = 0; i < help.length; i++) {
			sum[L + i] = help[i];
		}
		return ans;
	}
}
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

# 代码技巧问题--荷兰国旗问题

给定数组arr[]中，目标数x：

要求:

  • 不能使用辅助数组即 额外空间复杂度为O(1)
  • 时间复杂度为O(N)

版本一： <=x 放arr[]左边 >x放arr[]右边

  • 定义变量LT初始值为-1，记录<=区域下标
  • 循环arr[]
  • 循环体中判断arr[i]<=x
    • 将arr[i]与arr[LT+1](<=区域的下一个值)交换
    • LT++(<=区域向右扩)
    • 当前数跳下一个(i++)
  • 循环体中判断arr[i]>x，当前数跳下一个(i++)
  • 结论：<=区域在推着>区域往前走

版本二：<x放arr[]左边=x放arr[]中间>x放arr[]右边

  • 定义变量LT初始值为-1，记录<区域下标，定义变量RT初始值为arr.length，记录<区域下标
  • 循环arr[] i<RT当前数的下标不能与>区域的左边界撞上
  • 循环体中判断arr[i]<x
    • 将arr[i]与arr[LT+1](<区域的下一个值)交换
    • LT++(<区域向右扩)
    • 当前数跳下一个(i++)
    • 转化为 arr[i++]与arr[++LT]交换
  • 循环体中判断arr[i]==x，当前数跳下一个(i++)
  • 循环体中判断arr[i]>x
    • 将arr[i]与arr[RT-1](>区域的上一个值)交换
    • RT--(>区域向左扩)
    • 当前数不动不要跳下一个
    • 转化为 arr[i]与arr[--RT]交换

升级小函数：

传入数组及下标范围返回下标范围最右侧的元素值相等的等值区域下标信息

int[] netherlandsFlag(int[] arr, int L, int R)

  • int[]返回等于区域的范围下标

  • int[] arr 数组 L左侧下标 R右侧下标

  • 给定数组arr[]中，没有目标数了，将arr[len-1]作为目标数

    • 可以分析出将arr[0~len-2]范围上的进行左、中、右划分，再将arr[len-1](数组最后一个数)与arr[RT](右区域第一个数)交换即可，相当于将目标数归于等于区域
// arr[L...R] 玩荷兰国旗问题的划分，以arr[R]做划分值
	// <arr[R] ==arr[R] > arr[R]
	public static int[] netherlandsFlag(int[] arr, int L, int R) {
		if (L > R) { // L...R L>R
			return new int[] { -1, -1 };
		}
		if (L == R) {
			return new int[] { L, R };
		}
		int less = L - 1; // < 区 右边界
		int more = R; // > 区 左边界
		int index = L;
		while (index < more) { // 当前位置，不能和 >区的左边界撞上
			if (arr[index] == arr[R]) {
				index++;
			} else if (arr[index] < arr[R]) {
//				swap(arr, less + 1, index);
//				less++;
//				index++;						
				swap(arr, index++, ++less);
			} else { // >
				swap(arr, index, --more);
			}
		}
		swap(arr, more, R); // <[R]   =[R]   >[R]
		return new int[] { less + 1, more };
	}
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

# 快速排序三个版本

1.0版本：数组arr[]上的最后一个值作为目标值x，将数组划为>=x区域与<x区域，确定目标值的位置为>=x区域最后一个元素的位置，然后递归，周而复始

2.0版本：利用上述的升级版的小函数传入数组及下标范围返回下标范围最右侧的元素值相等的等值区域下标信息，然后递归，周而复始

最好情况的复杂度是Master公式T(N)=O(N)+2*T(N/2)=O(N*logN)，最差情况的复杂度是O(N^2)

3.0版本：随机快排

在2.0版本的基础上增加一行代码搞定

package class05;

import java.util.Arrays;

/**
 * 	时间复杂度为O(N) 额外空间复杂度为O(1)实现将以小于目标数在数组左边等于的来到中间大于的来到右边 两个版本分割
 * 	1、以数组最后一个位置上的数做为目标数，并以小于等于区域划分数组并返回小于等于区域最后的位置
 * 	2、荷兰国旗问题以数组最后一个位置上的数做为目标数，并以小于、大于区域划分数组并返回长度为2的int[]代表等于区域的位置范围
 * 	快排问题
 * @author yangyanchao
 *
 */
public class Test02_PartitionAndQuickSort {
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	
	/**
	 * 	以数组最后一个位置上的数做为目标数，并以小于等于区域划分数组并返回小于等于区域最后的位置
	 * @param arr
	 * @param L
	 * @param R
	 * @return
	 */
	public static int partition(int[] arr, int L, int R) {
		if(L > R) { // 违规位置
			return -1;
		}
		if(L == R) { // base case
			return L;
		}
		
		int lessEqual = L - 1;
		int target = arr[R];
		int i = L;
		while(i < R) {
			if(arr[i] <= target) {
				// arr[i]将于小于等于区域的下一个位置的值交换 然后小于等于区域向右扩 最后跳下一个
				swap(arr, i, ++lessEqual);
			}
			i++;
		}
		// 将arr[R]于小于等于区域的下一个位置上的数交换
		swap(arr, ++lessEqual, R);
		return lessEqual;
	}
	
	/**
	 * 	荷兰国旗问题以数组最后一个位置上的数做为目标数，并以小于、大于区域划分数组并返回长度为2的int[]代表等于区域的位置范围
	 * @param arr
	 * @param L
	 * @param R
	 * @return
	 */
	public static int[] netherlandsFlag(int[] arr, int L, int R) {
		if(L > R) { // 违规位置
			return new int[] { -1, -1 };
		}
		if(L == R) { // base case
			return new int[] { L, L };
		}
		int lessEqual = L - 1; // 小于区域位置
		int greaterEqual = R;  // 大于区域位置
		int target = arr[R];   // 目标值
		int i = L;
		while(i < greaterEqual) {
			if(arr[i] < target) {
				// 小于 arr[i]与lessEqual的下一个位置交换 并且小于区域往右扩 i++ 跳下一个
				swap(arr, i++, ++lessEqual);
			} else if(arr[i] > target) {
				// 大于 arr[i]与greaterEqual的上一个位置交换 并且小于区域往左扩 i值不变
				swap(arr, i, --greaterEqual);
			} else {
				// 相等
				i++;
			}
		}
		// 将目标值与大于区域的第一个位置交换
		swap(arr, greaterEqual, R);
		return new int[] { lessEqual + 1, greaterEqual};
	}
	
	/**
	 * 	快速排序1.0版本 递归
	 * @param arr
	 */
	public static void quickSort1(int[] arr) {
		if(arr == null || arr.length < 2) {
			return ;
		}
		process1(arr, 0, arr.length - 1);
	}
	private static void process1(int[] arr, int L, int R) {
		if(L >= R) {
			return ;
		}
		int equleVal = partition(arr, L, R);
		process1(arr, L, equleVal - 1);
		process1(arr, equleVal + 1, R);
	}
	
	/**
	 * 	快速排序2.0版本 递归
	 * @param arr
	 */
	public static void quickSort2(int[] arr) {
		if(arr == null || arr.length < 2) {
			return ;
		}
		process2(arr, 0, arr.length - 1);
	}
	private static void process2(int[] arr, int L, int R) {
		if(L >= R) {
			return ;
		}
		int[] equleArea = netherlandsFlag(arr, L, R);
		process2(arr, L, equleArea[0] - 1);
		process2(arr, equleArea[1] + 1, R);
	}
	
	/**
	 * 	快速排序3.0 递归版本 随机快排
	 * @param arr
	 */
	public static void quickSort3(int[] arr) {
		if(arr == null || arr.length < 2) {
			return ;
		}
		process3(arr, 0, arr.length - 1);
	}
	private static void process3(int[] arr, int L, int R) {
		if(L >= R) {
			return ;
		}
		// 随机交换数组其它位置上的数与最后位置上的数
		swap(arr, L + (int)((R - L + 1) * Math.random()), R);
		int[] equleArea = netherlandsFlag(arr, L, R);
		process3(arr, L, equleArea[0] - 1);
		process3(arr, equleArea[1] + 1, R);
	}
	
	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[] arr3 = copyArray(arr1);
			int[] arr4 = copyArray(arr1);
//			quickSort1(arr1);
//			quickSort2(arr2);
			quickSort3(arr3);
			Arrays.sort(arr4);
//			if(!isEqual(arr1, arr4)) {
//				succed = false;
//				printArray(arr1);
//				printArray(arr4);
//			}
//			if(!isEqual(arr2, arr4)) {
//				succed = false;
//				printArray(arr2);
//				printArray(arr4);
//			}
			if(!isEqual(arr3, arr4)) {
				succed = false;
				printArray(arr3);
				printArray(arr4);
			}
		}
		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
	 * @param arr2
	 * @return
	 */
	private static boolean isEqual(int[] arr1, int[] arr2) {
		boolean flag = true;
		if(arr1 == null || arr2 == null || arr1.length != arr2.length) {
			flag = false;
		}
		for(int i = 0; i < arr1.length; i++) {
			if(arr1[i] != arr2[i]) {
				flag = false;
			}
		}
		return flag;
	}

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

	/**
	 * 	生成长度及数值随机的数组
	 * @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())) - ((int)(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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244

# 随机快排的时间复杂度分析

1）通过分析知道，划分值越靠近中间，性能越好；越靠近两边，性能越差 2）随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件 3）把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N 4）那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望！

时间复杂度O(N*logN)，额外空间复杂度O(logN)都是这么来的。

# 随机快速排序递归与非递归版本

递归版本是将荷兰国旗问题递归加上随机交换数组最后一个位置上的值

非递归版本要将等值区域记录下一次的左右边界值，使用Stack记录

package class05;

import java.util.Arrays;
import java.util.Stack;

/**
 * 	递归版本是将荷兰国旗问题递归加上随机交换数组最后一个位置上的值
 * 	非递归版本要将等值区域记录下一次的左右边界值，使用Stack记录
 * @author yangyanchao
 *
 */
public class Test03_QuickSortRecursiveAndUnrecursive {
	/**
	 * 	荷兰国旗问题
	 * 	将arr[R]作为目标值target，将小于target的值移至数组左侧，将大于target的值移至数组右侧，中间是等于区域的值，并将等于区域的位置返回
	 * @param arr
	 * @param L
	 * @param R
	 * @return
	 */
	public static int[] netherlandsFlag(int[] arr, int L, int R) {
		if(L > R) {  // base case1
			return new int[] { -1, -1 };
		}
		if(L == R) { // base case2
			return new int[] { L, L };
		}
		// 小于区域的位置
		int lessIndex = L -1;
		// 大于区域的位置
		int moreIndex = R;
		// 当前检查的位置
		int index = L;
		int target = arr[R];
		while(index < moreIndex) {
			if(arr[index] == target) {
				index++;
			} else if(arr[index] < target) {
				// 当前值与小于区域的后一个值交换 并且index+1 lessIndex+1
				swap(arr, index++, ++lessIndex);
			} else if(arr[index] > target) {
				// 当前值与大于区域的前一个值交换 并且index+1 moreIndex-1
				swap(arr, index, --moreIndex);
			}
		}
		// 将arr[R]与大于区域的第一个位置交换
		swap(arr, R, moreIndex);
		return new int[] { lessIndex + 1, moreIndex };
	}

	/**
	 * 	交换
	 * @param arr
	 * @param i
	 * @param j
	 */
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	/**
	 * 	随机快排 递归版本
	 * @param arr
	 */
	public static void quickSortRecursive(int[] arr) {
		if(arr == null || arr.length < 2) {
			return ;
		}
		proccess(arr, 0, arr.length - 1);
	}

	private static void proccess(int[] arr, int L, int R) {
		if(L >= R) {
			return;
		}
		swap(arr, L + (int)(Math.random() * (R - L + 1)), R);
		int[] equalArea = netherlandsFlag(arr, L, R);
		proccess(arr, L, equalArea[0] - 1);
		proccess(arr, equalArea[0] + 1, R);
	}
	
	/**
	 * 	随机快排 非递归版本
	 * @param arr
	 */
	public static void quickSortUnRecursive(int[] arr) {
		if(arr == null || arr.length < 2) {
			return ;
		}
		int L = 0;
		int R = arr.length - 1;
		swap(arr, L + (int)(Math.random() * (R - L + 1)), R);
		int[] equalArea = netherlandsFlag(arr, L, R);
		Stack<Op> stack = new Stack<Op>();
		stack.push(new Op(L, equalArea[0] - 1));
		stack.push(new Op(equalArea[0] + 1, R));
		while(!stack.isEmpty()) {
			Op op = stack.pop();
			if(op.L < op.R) {
				swap(arr, op.L + (int)(Math.random() * (op.R - op.L + 1)), op.R);
				equalArea = netherlandsFlag(arr, op.L, op.R);
				stack.push(new Op(op.L, equalArea[0] - 1));
				stack.push(new Op(equalArea[0] + 1, op.R));
			}
		}
	}
	/**
	 * 	范围参数记录信息
	 * @author yangyanchao
	 *
	 */
	public static class Op{
		public int L;
		public int R;
		public Op() {
		}
		public Op(int L, int R) {
			this.L = L;
			this.R = R;
		}
	}
	
	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[] arr3 = copyArray(arr1);
			quickSortRecursive(arr1);
			quickSortUnRecursive(arr2);
			Arrays.sort(arr3);
			if(!isEqual(arr1, arr3)) {
				succed = false;
				printArray(arr1);
				printArray(arr3);
			}
			if(!isEqual(arr2, arr3)) {
				succed = false;
				printArray(arr2);
				printArray(arr3);
			}
		}
		System.out.println(succed ? "Nice." : "ooVoo" );
	}

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

	/**
	 * 	判断数组是否相等
	 * @param arr1
	 * @param arr2
	 * @return
	 */
	private static boolean isEqual(int[] arr1, int[] arr2) {
		if(arr1 == null || arr2 == null || arr1.length != arr2.length) {
			return false;
		}
		boolean flag = true;
		for(int i = 0; i < arr1.length; i++) {
			if(arr1[i] != arr2[i]) {
				flag = false;
				break;
			}
		}
		return flag;
	}

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

	/**
	 * 	生成长度及数值随机的数组
	 * @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())) - ((int)(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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218

← 第6节 堆和堆排序 →