# 第6节 堆和堆排序
# 比较器
1)比较器的实质就是重载比较运算符
2)比较器可以很好的应用在特殊标准的排序上
3)比较器可以很好的应用在根据特殊标准排序的结构上
4)写代码变得异常容易，还用于范型编程
# 任何比较器的统一约定
即如下方法：
@Override
public int compare(T o1, T o2) ;
1
2
2
返回负数的情况，就是o1比o2优先的情况 返回正数的情况，就是o2比o1优先的情况 返回0的情况，就是o1与o2同样优先的情况
代码示例
package class06;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeMap;
public class Code01_Comparator {
public static class Student {
public String name;
public int id;
public int age;
public Student(String name, int id, int age) {
this.name = name;
this.id = id;
this.age = age;
}
}
// 任何比较器：
// compare方法里，遵循一个统一的规范：
// 返回负数的时候，认为第一个参数应该排在前面
// 返回正数的时候，认为第二个参数应该排在前面
// 返回0的时候，认为无所谓谁放前面
public static class IdShengAgeJiangOrder implements Comparator<Student> {
// 根据id从小到大，但是如果id一样，按照年龄从大到小
@Override
public int compare(Student o1, Student o2) {
return o1.id != o2.id ? (o1.id - o2.id) : (o2.age - o1.age);
}
}
public static class IdAscendingComparator implements Comparator<Student> {
// 返回负数的时候，第一个参数排在前面
// 返回正数的时候，第二个参数排在前面
// 返回0的时候，谁在前面无所谓
@Override
public int compare(Student o1, Student o2) {
return o1.id - o2.id;
}
}
public static class IdDescendingComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o2.id - o1.id;
}
}
// 先按照id排序，id小的，放前面；
// id一样，age大的，前面；
public static class IdInAgeDe implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
return o1.id != o2.id ? o1.id - o2.id : (o2.age - o1.age);
}
}
public static void printStudents(Student[] students) {
for (Student student : students) {
System.out.println("Name : " + student.name + ", Id : " + student.id + ", Age : " + student.age);
}
}
public static void printArray(Integer[] arr) {
if (arr == null) {
return;
}
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
public static class MyComp implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
public static class AComp implements Comparator<Integer> {
// 如果返回负数，认为第一个参数应该拍在前面
// 如果返回正数，认为第二个参数应该拍在前面
// 如果返回0，认为谁放前面都行
@Override
public int compare(Integer arg0, Integer arg1) {
return arg1 - arg0;
// return 0;
}
}
public static void main(String[] args) {
Integer[] arr = { 5, 4, 3, 2, 7, 9, 1, 0 };
Arrays.sort(arr, new AComp());
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
System.out.println("===========================");
Student student1 = new Student("A", 4, 40);
Student student2 = new Student("B", 4, 21);
Student student3 = new Student("C", 3, 12);
Student student4 = new Student("D", 3, 62);
Student student5 = new Student("E", 3, 42);
// D E C A B
Student[] students = new Student[] { student1, student2, student3, student4, student5 };
System.out.println("第一条打印");
Arrays.sort(students, new IdShengAgeJiangOrder());
for (int i = 0; i < students.length; i++) {
Student s = students[i];
System.out.println(s.name + "," + s.id + "," + s.age);
}
System.out.println("第二条打印");
ArrayList<Student> studentList = new ArrayList<>();
studentList.add(student1);
studentList.add(student2);
studentList.add(student3);
studentList.add(student4);
studentList.add(student5);
studentList.sort(new IdShengAgeJiangOrder());
for (int i = 0; i < studentList.size(); i++) {
Student s = studentList.get(i);
System.out.println(s.name + "," + s.id + "," + s.age);
}
// N * logN
System.out.println("第三条打印");
student1 = new Student("A", 4, 40);
student2 = new Student("B", 4, 21);
student3 = new Student("C", 4, 12);
student4 = new Student("D", 4, 62);
student5 = new Student("E", 4, 42);
TreeMap<Student, String> treeMap = new TreeMap<>((a, b) -> (a.id - b.id));
treeMap.put(student1, "我是学生1，我的名字叫A");
treeMap.put(student2, "我是学生2，我的名字叫B");
treeMap.put(student3, "我是学生3，我的名字叫C");
treeMap.put(student4, "我是学生4，我的名字叫D");
treeMap.put(student5, "我是学生5，我的名字叫E");
for (Student s : treeMap.keySet()) {
System.out.println(s.name + "," + s.id + "," + s.age);
}
}
}
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
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）堆结构就是用数组实现的完全二叉树结构
2）完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3）完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4）堆结构的heapInsert与heapify操作
5）堆结构的增大和减少
6）优先级队列结构，就是堆结构
代码示例
package class06;
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* 手写优先级队列--堆结构
* @author yangyanchao
*
*/
public class Test02_Heap {
/**
* 我的优先级队列--大根堆结构
* @author yangyanchao
*
*/
public static class MyMaxHeap {
/**
* 数组表示完全二叉树结构
*/
private int[] heap = null;
/**
* 数组容量
*/
private int limit = 2000;
/**
* 完全二叉树结构的size
*/
private int heapSize = 0;
public MyMaxHeap() {
this.heap = new int[limit];
this.heapSize = 0;
}
public MyMaxHeap(int limit) {
this.limit = limit;
this.heap = new int[limit];
this.heapSize = 0;
}
/**
* 判断堆是否空
* @return
*/
public boolean isEmpty() {
return this.heapSize == 0;
}
/**
* 判断堆是否满
* @return
*/
public boolean isFull() {
return this.heapSize == this.limit;
}
/**
* 添加数据
* @param value
*/
public void push(int value) {
if(isFull()) {
throw new RuntimeException("heap is full.");
}
heap[heapSize] = value;
heapInsert(this.heap, heapSize++);
}
/**
* 弹出数据并将数组维持在大根堆
* @return
*/
public int poll() {
if(isEmpty()) {
throw new RuntimeException("heap is empty.");
}
int ans = this.heap[0];
swap(this.heap, 0, --heapSize);
heapify(this.heap, 0, heapSize);
return ans;
}
/**
* index与(index-1)/2父节点比较index大则交换
* 往上浮
* @param arr
* @param index
*/
private void heapInsert(int[] arr, int index) {
while(arr[index] > arr[((index-1)/2)]) {
swap(arr, index, ((index-1)/2));
index = ((index-1)/2);
}
}
/**
* index与2*index+1 较大的孩子比较 若孩子节点大则交换
* 往下沉
* @param arr
* @param index
* @param heapSize
*/
private void heapify(int[] arr, int index, int heapSize) {
// 左孩子的位置
int left = 2 * index + 1;
while(left < heapSize) {
// 将较大的孩子的位置-->> largest
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left ;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
// index和较大孩子，要互换
swap(arr, largest, index);
index = largest;
left = 2 * index + 1;
}
}
/**
* 交换
* @param arr
* @param i
* @param j
*/
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
/**
* 用于比较的大根堆结构
* @author yangyanchao
*
*/
public static class ComperatorMaxHeap {
private int[] arr;
private final int limit;
private int size;
public ComperatorMaxHeap(int limit) {
arr = new int[limit];
this.limit = limit;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
public void push(int value) {
if (isFull()) {
throw new RuntimeException("heap is full");
}
arr[size++] = value;
}
public int poll() {
if (isEmpty()) {
throw new RuntimeException("heap is empty");
}
int maxIndex = 0;
for (int i = 1; i < size; i++) {
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
int ans = arr[maxIndex];
arr[maxIndex] = arr[--size];
return ans;
}
}
public static class MyComparator implements Comparator<Integer>{
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
public static void main(String[] args) {
// 小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>(new MyComparator());
heap.add(5);
heap.add(5);
heap.add(5);
heap.add(3);
// 5 , 3
System.out.println(heap.peek());
heap.add(7);
heap.add(0);
heap.add(7);
heap.add(0);
heap.add(7);
heap.add(0);
System.out.println(heap.peek());
while(!heap.isEmpty()) {
System.out.println(heap.poll());
}
int value = 1000;
int limit = 100;
int testTimes = 1000000;
for (int i = 0; i < testTimes; i++) {
int curLimit = (int) (Math.random() * limit) + 1;
MyMaxHeap my = new MyMaxHeap(curLimit);
ComperatorMaxHeap test = new ComperatorMaxHeap(curLimit);
int curOpTimes = (int) (Math.random() * limit);
for (int j = 0; j < curOpTimes; j++) {
if (my.isEmpty() != test.isEmpty()) {
System.out.println("Oops!");
}
if (my.isFull() != test.isFull()) {
System.out.println("Oops!");
}
if (my.isEmpty()) {
int curValue = (int) (Math.random() * value);
my.push(curValue);
test.push(curValue);
} else if (my.isFull()) {
if (my.poll() != test.poll()) {
System.out.println("Oops!");
}
} else {
if (Math.random() < 0.5) {
int curValue = (int) (Math.random() * value);
my.push(curValue);
test.push(curValue);
} else {
if (my.poll() != test.poll()) {
System.out.println("Oops!");
}
}
}
}
}
System.out.println("finish!");
}
}
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
245
246
247
248
249
250
251
252
253
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
245
246
247
248
249
250
251
252
253
# 堆排序
1，先让整个数组都变成大根堆结构，建立堆的过程: 1)从上到下的方法，时间复杂度为O(NlogN) 2)从下到上的方法，时间复杂度为O(N) 2，把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(NlogN) 3，堆的大小减小成0之后，排序完成
代码示例
package class06;
import java.util.Arrays;
/**
* 堆排序 (大根堆)
* @author yangyanchao
*
*/
public class Test03_HeapSort {
/**
* index与父节点(index-1)/2进行比较 index大则交换
* index往上浮
* @param arr
* @param index
*/
private static void heapInsert(int[] arr, int index) {
while(arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
/**
* 数组中的两个位置交换
* @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;
}
/**
* index与较大的孩子节点(left=2*index+1;largest = left+1<heapSize && arr[left+1] > arr[left]? left+1 : left)进行比较
* index比largest小则交换
* index往下沉
* @param arr
* @param index
* @param heapSize
*/
private static void heapify(int[] arr, int index, int heapSize) {
int left = 2 * index + 1;
while(left < heapSize) {
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if(largest == index) { // arr[largest] <= arr[index] 不需要交换
break;
}
swap(arr, index, largest);
index = largest;
left = 2 * index + 1;
}
}
/**
* 堆排序
* 在0-N-1上入大根堆 则最大的数为arr[0]，将arr[0]与arr[N-1]交换 heapSize--
* 0位置上heapify则0-N-2上是大根堆，则将arr[0]与arr[N-2]交换 heapSize--
* 0位置上heapify则0-N-3上是大根堆，周而复始....
* 时间复杂度为O(N*logN)
* @param arr
*/
public static void heapSort(int[] arr) {
if(arr == null || arr.length < 2) {
return;
}
// 额外空间复杂度为O(N*logN)
// for(int i = 0; i < arr.length; i++) { // O(N)
// heapInsert(arr, i); // O(logN)
// }
// 额外空间复杂度为O(N) 等比数列 收敛于O(N)
for(int i = arr.length - 1; i >= 0; i--) {
heapify(arr, i, arr.length);
}
//以上是将数组加入大根堆结构
int heapSize = arr.length;
swap(arr, 0, --heapSize);
// O(N*logN)
while(heapSize > 0) {// O(N)
heapify(arr, 0, heapSize);// O(logN)
swap(arr, 0, --heapSize);// O(1)
}
}
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);
heapSort(arr1);
Arrays.sort(arr2);
if(!isEqual(arr1, arr2)) {
succed = false;
printArray(arr1);
printArray(arr2);
}
}
System.out.println(succed ? "Nice." : "ooVoo" );
}
/**
* 打印数组
* @param arr
*/
private static void printArray(int[] arr) {
if(arr == null) {
return;
}
System.out.print("{ ");
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 ans = true;
for(int i = 0; i < arr1.length; i++) {
if(arr1[i] != arr2[i]) {
return false;
}
}
return ans;
}
/**
* 复制数组
* @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)((maxSize + 1) * Math.random())) - ((int)(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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
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
# 与堆有关的题目
已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。
请选择一个合适的排序策略，对这个数组进行排序。
使用堆排序，思路：
- 原始数组无序=arr，k=5，index=0
- 那么arr在0到k范围上的数值必然有一个数是最小值X，将最小值弹出并写入arr[0]
- arr在1到k+1范围上的数值必然有一个数是最小值X，将最小值弹出并写入arr[1]
- 周而复始
- index >= arr.length
- 将堆中的遍历写入arr
代码示例
package class06;
import java.util.Arrays;
import java.util.PriorityQueue;
/**
* 已知一个几乎有序的数组。几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相对于数组长度来说是比较小的。
* 请选择一个合适的排序策略，对这个数组进行排序。 使用堆排序
* @author yangyanchao
*
*/
public class Test04_SortArrayDistanceLessK {
/**
* 思路
* - 原始数组无序=arr，k=5，index=0
* - 那么arr在0到k范围上的数值必然有一个数是最小值X，将最小值弹出并写入arr[0]
* - arr在1到k+1范围上的数值必然有一个数是最小值X，将最小值弹出并写入arr[1]
* - 周而复始
* - index >= arr.length
* - 将堆中的遍历写入arr
* @param arr
* @param k
*/
public static void sortedArrDistanceLessK(int[] arr, int k) {
if(k == 0) { // base case
return ;
}
// 定义一个小根堆 优先级队列默认就是小根堆
PriorityQueue<Integer> heap = new PriorityQueue<>();
int index = 0; //记录遍历原始数组的下标位置
for( ; index <= Math.min(arr.length - 1, k - 1); index++) {
// Math.min(arr.length - 1, k - 1) 可能存在k比数组长度还大的情况
heap.add(arr[index]);
}
int i = 0; // 记录已经完成排序的数组下标位置
for(; index < arr.length; index++) {
heap.add(arr[index]);
arr[i++] = heap.poll();
}
// 遍历完arr后 再遍历heap
while(!heap.isEmpty()) {
arr[i++] = heap.poll();
}
}
/**
* 比对函数
* @param arr
* @param k
*/
public static void comparator(int[] arr, int k) {
Arrays.sort(arr);
}
public static void main(String[] args) {
int testTime = 500000;
int maxSize = 100;
int maxValue = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int k = (int) (Math.random() * maxSize) + 1;
int[] arr = randomArrayNoMoveMoreK(maxSize, maxValue, k);
int[] arr1 = copyArray(arr);
int[] arr2 = copyArray(arr);
sortedArrDistanceLessK(arr1, k);
comparator(arr2, k);
if (!isEqual(arr1, arr2)) {
succeed = false;
System.out.println("K : " + k);
printArray(arr);
printArray(arr1);
printArray(arr2);
break;
}
}
System.out.println(succeed ? "Nice!" : "ooVoo");
}
/**
* 打印数组
* @param arr
*/
private static void printArray(int[] arr) {
if(arr == null) {
return ;
}
System.out.print("{ ");
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;
}
for(int i = 0; i < arr1.length; i++) {
if(arr1[i] != arr2[i]) {
return false;
}
}
return true;
}
/**
* 复制数组
* @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;
}
/**
* 生成长度及数值随机的数组 并保证每个元素移动的距离一定不超过k
* @param maxSize
* @param maxValue
* @param k
* @return
*/
private static int[] randomArrayNoMoveMoreK(int maxSize, int maxValue, int k) {
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()));
}
// 排序
Arrays.sort(arr);
// isSwap[i] = true 则说明i位置交换过
// isSwap[j] = false 则说明j位置没有交换过
boolean[] isSwap = new boolean[arr.length];// 初始化都没有交换过
for (int i = 0; i < arr.length; i++) {
int j = Math.min(i + (int)(Math.random() * (k + 1)), arr.length - 1);
if(isSwap[i] && isSwap[j]) {
isSwap[i] = true;
isSwap[j] = true;
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
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
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