看到網(wǎng)上的一段關(guān)于對(duì)數(shù)組操作的代碼，覺得有用，在此備用。
|
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 數(shù)組操作工具 * @author OuyangPeng * @datatime 2013-5-11 10:31:02 * */public class MyArrayUtils { /** * 排序算法的分類如下： 1.插入排序（直接插入排序、折半插入排序、希爾排序）； 2.交換排序（冒泡泡排序、快速排序）； * 3.選擇排序（直接選擇排序、堆排序）； 4.歸并排序； 5.基數(shù)排序。 * * 關(guān)于排序方法的選擇： (1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。 * (2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序?yàn)橐耍? * (3)若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。 * */ /** * 交換數(shù)組中兩元素 * * @since 1.1 * @param ints * 需要進(jìn)行交換操作的數(shù)組 * @param x * 數(shù)組中的位置1 * @param y * 數(shù)組中的位置2 * @return 交換后的數(shù)組 */ public static int[] swap(int[] ints, int x, int y) { int temp = ints[x]; ints[x] = ints[y]; ints[y] = temp; return ints; } /** * 冒泡排序方法:相鄰兩元素進(jìn)行比較 性能：比較次數(shù)O(n^2),n^2/2；交換次數(shù)O(n^2),n^2/4<br> * 冒泡排序（Bubble Sort）是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過要排序的數(shù)列，一次比較兩個(gè)元素，<br> * 如果他們的順序錯(cuò)誤就把他們交換過來。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，<br> * 也就是說該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。<br> 冒泡排序算法的運(yùn)作如下:<br> 1. 比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。<br> 2. 對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。<br> 3. 針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。<br> 4. 持續(xù)每次對(duì)越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。<br> * @since 1.1 * @param source * 需要進(jìn)行排序操作的數(shù)組 * @return 排序后的數(shù)組 */ 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++) { // 對(duì)當(dāng)前無序區(qū)間score[0......length-i-1]進(jìn)行排序(j的范圍很關(guān)鍵，這個(gè)范圍是在逐步縮小的) 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)是一種簡(jiǎn)單直觀的排序算法，其平均時(shí)間復(fù)雜度為O(n2)。 * 它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后， * 再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最小元素，然后放到排序序列末尾。以此類推，直到所有元素均排序完畢。 * 性能：選擇排序的交換操作介于0和(n-1)次之間， 選擇排序的比較操作為n(n-1)/2次之間， * 選擇排序的賦值操作介于0和3(n-1)次之間，其平均時(shí)間復(fù)雜度為O(n2) * 交換次數(shù)比冒泡排序少多了，由于交換所需CPU時(shí)間比比較所需的CUP時(shí)間多，所以選擇排序比冒泡排序快。 * 但是N比較大時(shí)，比較所需的CPU時(shí)間占主要地位，所以這時(shí)的性能和冒泡排序差不太多，但毫無疑問肯定要快些。 * * @since 1.1 * @param source * 需要進(jìn)行排序操作的數(shù)組 * @return 排序后的數(shù)組 */ 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; } /** * 插入排序 方法：將一個(gè)記錄插入到已排好序的有序表（有可能是空表）中,從而得到一個(gè)新的記錄數(shù)增1的有序表。 性能：比較次數(shù)O(n^2),n^2/4 * 復(fù)制次數(shù)O(n),n^2/4 比較次數(shù)是前兩者的一般，而復(fù)制所需的CPU時(shí)間較交換少，所以性能上比冒泡排序提高一倍多，而比選擇排序也要快。 * * @since 1.1 * @param source * 需要進(jìn)行排序操作的數(shù)組 * @return 排序后的數(shù)組 */ 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）策略來把一個(gè)序列（list）分為兩個(gè)子序列（sub-lists）。 步驟為： * 1. 從數(shù)列中挑出一個(gè)元素，稱為 "基準(zhǔn)"（pivot）， 2. * 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面 * （相同的數(shù)可以到任一邊）。在這個(gè)分割之后，該基準(zhǔn)是它的最后位置。這個(gè)稱為分割（partition）操作。 3. * 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。 * 遞回的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了 * 。雖然一直遞回下去，但是這個(gè)算法總會(huì)結(jié)束，因?yàn)樵诿看蔚牡╥teration）中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。 * * @since 1.1 * @param source * 需要進(jìn)行排序操作的數(shù)組 * @return 排序后的數(shù)組 */ public static int[] quickSort(int[] source) { return qsort(source, 0, source.length - 1); } /** * 快速排序的具體實(shí)現(xiàn)，排正序 * * @since 1.1 * @param source * 需要進(jìn)行排序操作的數(shù)組 * @param low * 開始低位 * @param high * 結(jié)束高位 * @return 排序后的數(shù)組 */ 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; } // ///////////////////////////////////////////// // 排序算法結(jié)束 // //////////////////////////////////////////// /** * 二分法查找 查找線性表必須是有序列表 * * @since 1.1 * @param source * 需要進(jìn)行查找操作的數(shù)組 * @return 需要查找的值在數(shù)組中的位置，若未查到則返回-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; } /** * 反轉(zhuǎn)數(shù)組 * * @since 1.1 * @param source * 需要進(jìn)行反轉(zhuǎn)操作的數(shù)組 * @return 反轉(zhuǎn)后的數(shù)組 */ 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; } /** * 在當(dāng)前位置插入一個(gè)元素,數(shù)組中原有元素向后移動(dòng); 如果插入位置超出原數(shù)組，則拋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; } /** * 整形數(shù)組中特定位置刪除掉一個(gè)元素,數(shù)組中原有元素向前移動(dòng); 如果插入位置超出原數(shù)組，則拋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個(gè)數(shù)組合并，形成一個(gè)新的數(shù)組 * * @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; } /** * 數(shù)組中有n個(gè)數(shù)據(jù)，要將它們順序循環(huán)向后移動(dòng)k位， 即前面的元素向后移動(dòng)k位，后面的元素則循環(huán)向前移k位， * 例如，0、1、2、3、4循環(huán)移動(dòng)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; } /** * 隨機(jī)打亂一個(gè)數(shù)組 * * @param list * @return */ public static List shuffle(List list) { java.util.Collections.shuffle(list); return list; } /** * 隨機(jī)打亂一個(gè)數(shù)組 * * @param array * @return */ public int[] shuffle(int[] array) { Random random = new Random(); for (int index = array.length - 1; index >= 0; index--) { // 從0到index處之間隨機(jī)取一個(gè)值，跟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; } /** * 對(duì)兩個(gè)有序數(shù)組進(jìn)行合并,并將重復(fù)的數(shù)字將其去掉 * * @param a * ：已排好序的數(shù)組a * @param b * ：已排好序的數(shù)組b * @return 合并后的排序數(shù)組 */ private static List<Integer> mergeByList(int[] a, int[] b) { // 用于返回的新數(shù)組，長(zhǎng)度可能不為a,b數(shù)組之和，因?yàn)榭赡苡兄貜?fù)的數(shù)字需要去掉 List<Integer> c = new ArrayList<Integer>(); // a數(shù)組下標(biāo) int aIndex = 0; // b數(shù)組下標(biāo) int bIndex = 0; // 對(duì)a、b兩數(shù)組的值進(jìn)行比較，并將小的值加到c，并將該數(shù)組下標(biāo)+1， // 如果相等，則將其任意一個(gè)加到c，兩數(shù)組下標(biāo)均+1 // 如果下標(biāo)超出該數(shù)組長(zhǎng)度，則退出循環(huán) 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++; } } // 將沒有超出數(shù)組下標(biāo)的數(shù)組其余全部加到數(shù)組c中 // 如果a數(shù)組還有數(shù)字沒有處理 if (aIndex <= a.length - 1) { for (int i = aIndex; i <= a.length - 1; i++) { c.add(a[i]); } // 如果b數(shù)組中還有數(shù)字沒有處理 } else if (bIndex <= b.length - 1) { for (int i = bIndex; i <= b.length - 1; i++) { c.add(b[i]); } } return c; } /** * 對(duì)兩個(gè)有序數(shù)組進(jìn)行合并,并將重復(fù)的數(shù)字將其去掉 * * @param a * :已排好序的數(shù)組a * @param b * :已排好序的數(shù)組b * @return合并后的排序數(shù)組,返回?cái)?shù)組的長(zhǎng)度=a.length + b.length,不足部分補(bǔ)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; } /** * 對(duì)兩個(gè)有序數(shù)組進(jìn)行合并,并將重復(fù)的數(shù)字將其去掉 * * @param a * ：可以是沒有排序的數(shù)組 * @param b * ：可以是沒有排序的數(shù)組 * @return合并后的排序數(shù)組 打印時(shí)可以這樣： 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; } /** * 在控制臺(tái)打印數(shù)組，之間用逗號(hào)隔開,調(diào)試時(shí)用 * * @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); } } |
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://blog.csdn.net/ouyang_peng/article/details/8913690
