Java 计算数组的中值。
计算数组的中位数。
实例源码：
源代码：
执行
执行中...
x
1
2
3
//package com.nowjava;/**来 自 时 代 Java - nowjava.com**/4
5
6
public class Main {7
8
public static void main(String[] argv) throws Exception {9
10
double[] v = new double[] { 34.45, 35.45, 36.67, 37.78, 37.0000,11
12
37.1234, 67.2344, 68.34534, 69.87700 };13
14
System.out.println(median(v));15
16
}17
18
19
/**20
21
* Computes the median of an array.22
23
* If the array contains an even number of elements,24
25
* then the mean of the lower and upper medians is returned.26
27
*/28
29
public static double median(double[] v) {30
31
if (v.length == 3) {32
33
return median3(copy(v));34
35
} else if (v.length == 5) {36
37
return median5(copy(v));38
39
} else if (v.length == 7) {40
41
return median7(copy(v));42
43
} else if (v.length % 2 == 1) { // odd44
45
return quickSelect(copy(v), false);46
47
} else { // even// from 时 代 J a v a - N o w J a v a . c o m48
49
double[] tmp = copy(v);50
51
double lowerMedian = quickSelect(tmp, false);52
53
double upperMedian = quickSelect(tmp, true);54
55
return (lowerMedian + upperMedian) / 2.0;56
57
}58
59
}60
61
62
/**63
64
* Computes the median of an array.65
66
* If the array contains an even number of elements,67
68
* the lower median is returned.69
70
*/71
72
public static int median(int[] v) {73
74
if (v.length == 3) {75
76
return median3(copy(v));77
78
} else if (v.length == 5) {79
80
return median5(copy(v));81
82
} else if (v.length == 7) {83
84
return median7(copy(v));85
86
} else {87
88
return quickSelect(copy(v));89
90
}91
92
}93
94
95
private static double median3(double[] v) {96
97
sortInPlace(v, 0, 1);98
99
sortInPlace(v, 1, 2);100
101
sortInPlace(v, 0, 1);102
103
return v[1];104
105
}106
107
108
private static int median3(int[] v) {109
110
sortInPlace(v, 0, 1);111
112
sortInPlace(v, 1, 2);113
114
sortInPlace(v, 0, 1);115
116
return v[1];117
118
}119
120
121
/**122
123
* Returns a copy of the array.124
125
*/126
127
//a call to array.clone() may also work although this is a primitive type. I haven't checked128
129
//it even may be faster130
131
public static int[] copy(int[] array) {132
133
int[] result;134
135
result = new int[array.length];136
137
System.arraycopy(array, 0, result, 0, array.length);138
139
return result;140
141
}142
143
144
/**145
146
* Returns a copy of the array.147
148
*/149
150
//a call to array.clone() may also work although this is a primitive type. I haven't checked151
152
//it even may be faster153
154
public static long[] copy(long[] array) {155
156
long[] result;157
158
result = new long[array.length];159
160
System.arraycopy(array, 0, result, 0, array.length);161
162
return result;163
164
}165
166
167
/**168
169
* Returns a copy of the array.170
171
*/172
173
//a call to array.clone() may also work although this is a primitive type. I haven't checked174
175
//it even may be faster176
177
public static float[] copy(float[] array) {178
179
float[] result;180
181
result = new float[array.length];182
183
System.arraycopy(array, 0, result, 0, array.length);184
185
return result;186
187
}188
189
190
/**191
192
* Returns a copy of the array.193
194
*/195
196
//a call to array.clone() may also work although this is a primitive type. I haven't checked197
198
//it even may be faster199
200
public static double[] copy(double[] array) {201
202
double[] result;203
204
result = new double[array.length];205
206
System.arraycopy(array, 0, result, 0, array.length);207
208
return result;209
210
}211
212
213
/**214
215
* Returns a copy of the array.216
217
*/218
219
public static double[][] copy(double[][] v) {220
221
double[][] ans = new double[v.length][];222
223
for (int k = 0; k < v.length; k++)224
225
ans[k] = copy(v[k]);226
227
return (ans);228
229
}230
231
232
/**233
234
* Returns a copy of the array.235
236
*/237
238
public static int[][] copy(int[][] v) {239
240
int[][] ans = new int[v.length][];241
242
for (int k = 0; k < v.length; k++)243
244
ans[k] = copy(v[k]);245
246
return (ans);247
248
}249
250
251
private static double median5(double[] v) {252
253
sortInPlace(v, 0, 1);254
255
sortInPlace(v, 3, 4);256
257
sortInPlace(v, 0, 3);258
259
sortInPlace(v, 1, 4);260
261
sortInPlace(v, 1, 2);262
263
sortInPlace(v, 2, 3);264
265
sortInPlace(v, 1, 2);266
267
return v[2];268
269
}270
271
272
private static int median5(int[] v) {273
274
sortInPlace(v, 0, 1);275
276
sortInPlace(v, 3, 4);277
278
sortInPlace(v, 0, 3);279
280
sortInPlace(v, 1, 4);281
282
sortInPlace(v, 1, 2);283
284
sortInPlace(v, 2, 3);285
286
sortInPlace(v, 1, 2);287
288
return v[2];289
290
}291
292
293
private static double median7(double[] v) {294
295
sortInPlace(v, 0, 5);296
297
sortInPlace(v, 0, 3);298
299
sortInPlace(v, 1, 6);300
301
sortInPlace(v, 2, 4);302
303
sortInPlace(v, 0, 1);304
305
sortInPlace(v, 3, 5);306
307
sortInPlace(v, 2, 6);308
309
sortInPlace(v, 2, 3);310
311
sortInPlace(v, 3, 6);312
313
sortInPlace(v, 4, 5);314
315
sortInPlace(v, 1, 4);316
317
sortInPlace(v, 1, 3);318
319
sortInPlace(v, 3, 4);320
321
return v[3];322
323
}324
325
326
private static int median7(int[] v) {327
328
sortInPlace(v, 0, 5);329
330
sortInPlace(v, 0, 3);331
332
sortInPlace(v, 1, 6);333
334
sortInPlace(v, 2, 4);335
336
sortInPlace(v, 0, 1);337
338
sortInPlace(v, 3, 5);339
340
sortInPlace(v, 2, 6);341
342
sortInPlace(v, 2, 3);343
344
sortInPlace(v, 3, 6);345
346
sortInPlace(v, 4, 5);347
348
sortInPlace(v, 1, 4);349
350
sortInPlace(v, 1, 3);351
352
sortInPlace(v, 3, 4);353
354
return v[3];355
356
}357
358
359
private static double quickSelect(double[] v, boolean upperMedian) {360
361
int low = 0, high = v.length - 1;362
363
final int median = upperMedian ? high / 2 + 1 : high / 2;364
365
int middle, ll, hh;366
367
368
for (;;) {369
370
if (high <= low) { /* One element only */371
372
return v[median];373
374
}375
376
377
if (high == low + 1) { /* Two elements only */378
379
if (v[low] > v[high])380
381
swap(v, low, high);382
383
return v[median];384
385
}386
387
388
/* Find median of low, middle and high items; swap into position low */389
390
middle = (low + high) / 2;391
392
if (v[middle] > v[high])393
394
swap(v, middle, high);395
396
if (v[low] > v[high])397
398
swap(v, low, high);399
400
if (v[middle] > v[low])401
402
swap(v, middle, low);403
404
405
/* Swap low item (now in position middle) into position (low+1) */406
407
swap(v, middle, low + 1);408
409
410
/* Nibble from each end towards middle, swapping items when stuck */411
412
ll = low + 1;413
414
hh = high;415
416
for (;;) {417
418
do419
420
ll++;421
422
while (v[low] > v[ll]);423
424
do425
426
hh--;427
428
while (v[hh] > v[low]);429
430
431
if (hh < ll)432
433
break;434
435
436
swap(v, ll, hh);437
438
}439
440
441
/* Swap middle item (in position low) back into correct position */442
443
swap(v, low, hh);444
445
446
/* Re-set active partition */447
448
if (hh <= median)449
450
low = ll;451
452
if (hh >= median)453
454
high = hh - 1;455
456
}457
458
}459
460
461
private static int quickSelect(int[] v) {462
463
int low = 0, high = v.length - 1;464
465
final int median = high / 2;466
467
int middle, ll, hh;468
469
470
for (;;) {471
472
if (high <= low) { /* One element only */473
474
return v[median];475
476
}477
478
479
if (high == low + 1) { /* Two elements only */480
481
if (v[low] > v[high])482
483
swap(v, low, high);484
485
return v[median];486
487
}488
489
490
/* Find median of low, middle and high items; swap into position low */491
492
middle = (low + high) / 2;493
494
if (v[middle] > v[high])495
496
swap(v, middle, high);497
498
if (v[low] > v[high])499
500
swap(v, low, high);501
502
if (v[middle] > v[low])503
504
swap(v, middle, low);505
506
507
/* Swap low item (now in position middle) into position (low+1) */508
509
swap(v, middle, low + 1);510
511
512
/* Nibble from each end towards middle, swapping items when stuck */513
514
ll = low + 1;515
516
hh = high;517
518
for (;;) {519
520
do521
/**代码未完, 请加载全部代码(NowJava.com).**/执行结果：
本文系作者在时代Java发表，未经许可，不得转载。如有侵权，请联系nowjava@qq.com删除。
编辑于
关注时代Java