看到網上的一段關于對數組操作的代碼，覺得有用，在此備用。
|
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
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
|
import java.util.Arrays; import java.util.List; import java.util.Map; import java.util.Random; import java.util.TreeMap; /** * @desc 數組操作工具 * @author OuyangPeng * @datatime 2013-5-11 10:31:02 * */public class MyArrayUtils { /** * 排序算法的分類如下： 1.插入排序（直接插入排序、折半插入排序、希爾排序）； 2.交換排序（冒泡泡排序、快速排序）； * 3.選擇排序（直接選擇排序、堆排序）； 4.歸并排序； 5.基數排序。 * * 關于排序方法的選擇： (1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。 * (2)若文件初始狀態基本有序(指正序)，則應選用直接插人、冒泡或隨機的快速排序為宜； * (3)若n較大，則應采用時間復雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。 * */ /** * 交換數組中兩元素 * * @since 1.1 * @param ints * 需要進行交換操作的數組 * @param x * 數組中的位置1 * @param y * 數組中的位置2 * @return 交換后的數組 */ public static int[] swap(int[] ints, int x, int y) { int temp = ints[x]; ints[x] = ints[y]; ints[y] = temp; return ints; } /** * 冒泡排序方法:相鄰兩元素進行比較 性能：比較次數O(n^2),n^2/2；交換次數O(n^2),n^2/4<br> * 冒泡排序（Bubble Sort）是一種簡單的排序算法。它重復地走訪過要排序的數列，一次比較兩個元素，<br> * 如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，<br> * 也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。<br> 冒泡排序算法的運作如下:<br> 1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。<br> 2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。<br> 3. 針對所有的元素重復以上的步驟，除了最后一個。<br> 4. 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。<br> * @since 1.1 * @param source * 需要進行排序操作的數組 * @return 排序后的數組 */ public static int[] bubbleSort(int[] source) { /*for (int i = 0; i < source.length - 1; i++) { // 最多做n-1趟排序 for (int j = 0; j < source.length - i - 1; j++) { // 對當前無序區間score[0......length-i-1]進行排序(j的范圍很關鍵，這個范圍是在逐步縮小的) if (source[j] > source[j + 1]) { // 把大的值交換到后面 swap(source, j, j + 1); } } }*/ for (int i = source.length - 1; i>0 ; i--) { for (int j = 0; j < i; j++) { if (source[j] > source[j + 1]) { swap(source, j, j + 1); } } } return source; } /** * 選擇排序法 方法：選擇排序(Selection sort)是一種簡單直觀的排序算法，其平均時間復雜度為O(n2)。 * 它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后， * 再從剩余未排序元素中繼續尋找最小元素，然后放到排序序列末尾。以此類推，直到所有元素均排序完畢。 * 性能：選擇排序的交換操作介于0和(n-1)次之間， 選擇排序的比較操作為n(n-1)/2次之間， * 選擇排序的賦值操作介于0和3(n-1)次之間，其平均時間復雜度為O(n2) * 交換次數比冒泡排序少多了，由于交換所需CPU時間比比較所需的CUP時間多，所以選擇排序比冒泡排序快。 * 但是N比較大時，比較所需的CPU時間占主要地位，所以這時的性能和冒泡排序差不太多，但毫無疑問肯定要快些。 * * @since 1.1 * @param source * 需要進行排序操作的數組 * @return 排序后的數組 */ public static int[] selectSort(int[] source) { for (int i = 0; i < source.length; i++) { for (int j = i + 1; j < source.length; j++) { if (source[i] > source[j]) { swap(source, i, j); } } } return source; } /** * 插入排序 方法：將一個記錄插入到已排好序的有序表（有可能是空表）中,從而得到一個新的記錄數增1的有序表。 性能：比較次數O(n^2),n^2/4 * 復制次數O(n),n^2/4 比較次數是前兩者的一般，而復制所需的CPU時間較交換少，所以性能上比冒泡排序提高一倍多，而比選擇排序也要快。 * * @since 1.1 * @param source * 需要進行排序操作的數組 * @return 排序后的數組 */ public static int[] insertSort(int[] source) { for (int i = 1; i < source.length; i++) { for (int j = i; (j > 0) && (source[j] < source[j - 1]); j--) { swap(source, j, j - 1); } } return source; } /** * 快速排序 快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。 步驟為： * 1. 從數列中挑出一個元素，稱為 "基準"（pivot）， 2. * 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面 * （相同的數可以到任一邊）。在這個分割之后，該基準是它的最后位置。這個稱為分割（partition）操作。 3. * 遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。 * 遞回的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了 * 。雖然一直遞回下去，但是這個算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。 * * @since 1.1 * @param source * 需要進行排序操作的數組 * @return 排序后的數組 */ public static int[] quickSort(int[] source) { return qsort(source, 0, source.length - 1); } /** * 快速排序的具體實現，排正序 * * @since 1.1 * @param source * 需要進行排序操作的數組 * @param low * 開始低位 * @param high * 結束高位 * @return 排序后的數組 */ private static int[] qsort(int source[], int low, int high) { int i, j, x; if (low < high) { i = low; j = high; x = source[i]; while (i < j) { while (i < j && source[j] > x) { j--; } if (i < j) { source[i] = source[j]; i++; } while (i < j && source[i] < x) { i++; } if (i < j) { source[j] = source[i]; j--; } } source[i] = x; qsort(source, low, i - 1); qsort(source, i + 1, high); } return source; } // ///////////////////////////////////////////// // 排序算法結束 // //////////////////////////////////////////// /** * 二分法查找 查找線性表必須是有序列表 * * @since 1.1 * @param source * 需要進行查找操作的數組 * @return 需要查找的值在數組中的位置，若未查到則返回-1 */ public static int[] binarySearch(int[] source) { int i,j; int low, high, mid; int temp; for (i = 0; i < source.length; i++) { temp=source[i]; low=0; high=i-1; while (low <= high) { mid = (low + high)/2; if (source[mid]>temp) { high=mid-1; } else { low = mid + 1; } } for (j= i-1; j>high;j--) source[j+1]=source[j]; source[high+1]=temp; } return source; } /** * 反轉數組 * * @since 1.1 * @param source * 需要進行反轉操作的數組 * @return 反轉后的數組 */ public static int[] reverse(int[] source) { int length = source.length; int temp = 0; for (int i = 0; i < length >> 1; i++) { temp = source[i]; source[i] = source[length - 1 - i]; source[length - 1 - i] = temp; } return source; } /** * 在當前位置插入一個元素,數組中原有元素向后移動; 如果插入位置超出原數組，則拋IllegalArgumentException異常 * * @param array * @param index * @param insertNumber * @return */ public static int[] insert(int[] array, int index, int insertNumber) { if (array == null || array.length == 0) { throw new IllegalArgumentException(); } if (index - 1 > array.length || index <= 0) { throw new IllegalArgumentException(); } int[] dest = new int[array.length + 1]; System.arraycopy(array, 0, dest, 0, index - 1); dest[index - 1] = insertNumber; System.arraycopy(array, index - 1, dest, index, dest.length - index); return dest; } /** * 整形數組中特定位置刪除掉一個元素,數組中原有元素向前移動; 如果插入位置超出原數組，則拋IllegalArgumentException異常 * * @param array * @param index * @return */ public static int[] remove(int[] array, int index) { if (array == null || array.length == 0) { throw new IllegalArgumentException(); } if (index > array.length || index <= 0) { throw new IllegalArgumentException(); } int[] dest = new int[array.length - 1]; System.arraycopy(array, 0, dest, 0, index - 1); System.arraycopy(array, index, dest, index - 1, array.length - index); return dest; } /** * 2個數組合并，形成一個新的數組 * * @param array1 * @param array2 * @return */ public static int[] merge(int[] array1, int[] array2) { int[] dest = new int[array1.length + array2.length]; System.arraycopy(array1, 0, dest, 0, array1.length); System.arraycopy(array2, 0, dest, array1.length, array2.length); return dest; } /** * 數組中有n個數據，要將它們順序循環向后移動k位， 即前面的元素向后移動k位，后面的元素則循環向前移k位， * 例如，0、1、2、3、4循環移動3位后為2、3、4、0、1。 * * @param array * @param offset * @return */ public static int[] offsetArray(int[] array, int offset) { int length = array.length; int moveLength = length - offset; int[] temp = Arrays.copyOfRange(array, moveLength, length); System.arraycopy(array, 0, array, offset, moveLength); System.arraycopy(temp, 0, array, 0, offset); return array; } /** * 隨機打亂一個數組 * * @param list * @return */ public static List shuffle(List list) { java.util.Collections.shuffle(list); return list; } /** * 隨機打亂一個數組 * * @param array * @return */ public int[] shuffle(int[] array) { Random random = new Random(); for (int index = array.length - 1; index >= 0; index--) { // 從0到index處之間隨機取一個值，跟index處的元素交換 exchange(array, random.nextInt(index + 1), index); } return array; } // 交換位置 private void exchange(int[] array, int p1, int p2) { int temp = array[p1]; array[p1] = array[p2]; array[p2] = temp; } /** * 對兩個有序數組進行合并,并將重復的數字將其去掉 * * @param a * ：已排好序的數組a * @param b * ：已排好序的數組b * @return 合并后的排序數組 */ private static List<Integer> mergeByList(int[] a, int[] b) { // 用于返回的新數組，長度可能不為a,b數組之和，因為可能有重復的數字需要去掉 List<Integer> c = new ArrayList<Integer>(); // a數組下標 int aIndex = 0; // b數組下標 int bIndex = 0; // 對a、b兩數組的值進行比較，并將小的值加到c，并將該數組下標+1， // 如果相等，則將其任意一個加到c，兩數組下標均+1 // 如果下標超出該數組長度，則退出循環 while (true) { if (aIndex > a.length - 1 || bIndex > b.length - 1) { break; } if (a[aIndex] < b[bIndex]) { c.add(a[aIndex]); aIndex++; } else if (a[aIndex] > b[bIndex]) { c.add(b[bIndex]); bIndex++; } else { c.add(a[aIndex]); aIndex++; bIndex++; } } // 將沒有超出數組下標的數組其余全部加到數組c中 // 如果a數組還有數字沒有處理 if (aIndex <= a.length - 1) { for (int i = aIndex; i <= a.length - 1; i++) { c.add(a[i]); } // 如果b數組中還有數字沒有處理 } else if (bIndex <= b.length - 1) { for (int i = bIndex; i <= b.length - 1; i++) { c.add(b[i]); } } return c; } /** * 對兩個有序數組進行合并,并將重復的數字將其去掉 * * @param a * :已排好序的數組a * @param b * :已排好序的數組b * @return合并后的排序數組,返回數組的長度=a.length + b.length,不足部分補0 */ private static int[] mergeByArray(int[] a, int[] b) { int[] c = new int[a.length + b.length]; int i = 0, j = 0, k = 0; while (i < a.length && j < b.length) { if (a[i] <= b[j]) { if (a[i] == b[j]) { j++; } else { c[k] = a[i]; i++; k++; } } else { c[k] = b[j]; j++; k++; } } while (i < a.length) { c[k] = a[i]; k++; i++; } while (j < b.length) { c[k] = b[j]; j++; k++; } return c; } /** * 對兩個有序數組進行合并,并將重復的數字將其去掉 * * @param a * ：可以是沒有排序的數組 * @param b * ：可以是沒有排序的數組 * @return合并后的排序數組 打印時可以這樣： Map<Integer,Integer> map=sortByTreeMap(a,b); * Iterator iterator = map.entrySet().iterator(); while * (iterator.hasNext()) { Map.Entry mapentry = * (Map.Entry)iterator.next(); * System.out.print(mapentry.getValue()+" "); } */ private static Map<Integer, Integer> mergeByTreeMap(int[] a, int[] b) { Map<Integer, Integer> map = new TreeMap<Integer, Integer>(); for (int i = 0; i < a.length; i++) { map.put(a[i], a[i]); } for (int i = 0; i < b.length; i++) { map.put(b[i], b[i]); } return map; } /** * 在控制臺打印數組，之間用逗號隔開,調試時用 * * @param array */ public static String print(int[] array) { StringBuffer sb = new StringBuffer(); for (int i = 0; i < array.length; i++) { sb.append("," + array[i]); } System.out.println("\n"+sb.toString().substring(1)); return sb.toString().substring(1); } } |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：http://blog.csdn.net/ouyang_peng/article/details/8913690
