无序数组的中位数 - _dshizhh - 博客园

参考：http://mp.weixin.qq.com/s?__biz=MjM5ODIzNDQ3Mw%3D%3D&idx=1&mid=2649965551&scene=0&sn=bc769eb3fbd2f4075c58524f4cc8332d

中位数，就是数组排序后处于数组最中间的那个元素。说来有些麻烦，如果数组长度是奇数，最中间就是位置为（n+1）／2 的那个元素。如果是偶数呢，标准的定义是位置为 n/2 和位置为 n/2+1 的两个元素的和除以 2 的结果，有些复杂。为了解答的方便，我们假设数组长度暂且都为奇数吧。

面试时，大家是不是经常被问到，怎么求一个无序数组（长度为 n）的中位数？

不假思索的算法是，首先将数组排序，然后直接从排序数组中找出中位数。这个算法的复杂度是 O（nlogn），就是排序的复杂度。当然，答案是有了，但不会 impress 面试官的：）。but it is ok, 如果你能写出代码。

排序代码

1 public　void　sort(int　arr[],int　low,int　high)
2 {
3 int　l=low;
4 int　h=high;
5 int　povit=arr[low];
6
7 while(l 8 {
9 while(l=povit) h—; 10 if(l 17 while(l 19 if(l 27 if(l>low) sort(arr,low,l-1); 28 if(l<high) sort(arr,l+1,high); 29 }

另外一个优化的快速算法是快速中位数算法，类似于快速排序，采用的是分而治之的思想。基本思路是：任意挑一个元素，以该元素为支点，将数组分成两部分，左部分是小于等于支点的，右部分是大于支点的。如果你的运气爆棚，左部分正好是（n－1）／2 个元素，那么支点的那个数就是中位数。否则的话，相信你知道怎么推理了。写出没有 bug 的代码还是需要一点点功力的。作为家庭作业好了。

代码

1 public static double median2(int[] array){2 if(arraynull || array.length0) return 0;
3 int left = 0;
4 int right = array.length-1;
5 int midIndex = right >> 1;
6 int index = -1;
7 while(index != midIndex){ 8 index = partition(array, left, right); 9 if(index < midIndex) left = index + 1; 10 else if (index > midIndex) right = index - 1; 11 else break; 12 } 13 return array[index]; 14 } 15
16 public static int partition(int[] array, int left, int right){17 if(left> right) return -1; 18 int pos = right; 19 right—; 20 while(left <= right){ 21 while(leftleft && array[right]>array[pos]) right—; 23 if(left>= right) break; 24 swap(array, left, right); 25 } 26
27 swap(array, left, pos); 28 return left; 29 }

这里，给大家介绍一个让人眼前一亮的算法，至少，看着很美妙，可以细细品味。算法的核心是使用最小堆（heap），你想到了吗？

首先将数组的前（n+1）／2 个元素建立一个最小堆。

然后，对于下一个元素，和堆顶的元素比较，如果小于等于，丢弃之，接着看下一个元素。如果大于，则用该元素取代堆顶，再调整堆，接着看下一个元素。重复这个步骤，直到数组为空。

当数组都遍历完了，那么，堆顶的元素即是中位数。

可以看出，长度为（n＋1）／2 的最小堆是解决方案的精华之处。

代码

1 public static double median(int[] array){
2 int heapSize = array.length/2 + 1;
3 PriorityQueue heap = new PriorityQueue<>(heapSize);
4 for(int i=0; i 5 heap.add(array[i]);
6 }
7 for(int i=heapSize; i 8 if(heap.peek()<array[i]){9 heap.poll(); 10 heap.add(array[i]); 11 } 12 } 13 if(array.length % 2 == 1){ 14 return (double)heap.peek(); 15 } 16 else{ 17 return (double)(heap.poll()+heap.peek())/2.0; 18 } 19 }

https://www.cnblogs.com/shizhh/p/5746151.html