学步园

中位数（median）是一个排好序的元素中中间位置的元素，如果元素个数为偶数，则是中间两个元素的平均值。例如（3,1,5）的中位数是3，而（2,1,3,5）的中位数是2.5。查找中位数属于Selection Algorithms的一种。用快速排序可以做到每次divide之后，只需要conquer一个分支，时间复杂度为O(nlogn)。

为便于比较，以下代码包含quicksort的算法实现：

public static float findMedianByQuicksort(int[] A,int left,int right){<br /> //if(right<left)<br /> // throw new IllegalArgumentException();</p> <p> int rp = sortPivot(A,left,right);</p> <p> int leftCnt = rp;<br /> int rightCnt = A.length-rp-1;<br /> if(A.length % 2 == 0) {<br /> if(rightCnt == leftCnt+1){<br /> if(right<rp+1){<br /> return A[rp];<br /> }else{<br /> return (A[rp] + findMedianByQuicksort(A,rp+1,right))/2;<br /> }</p> <p> }else if(rightCnt+1==leftCnt){<br /> if(rp-1<left){<br /> return A[rp];<br /> }else{<br /> return (findMedianByQuicksort(A,left,rp-1)+A[rp])/2;<br /> }<br /> }else if(rightCnt > leftCnt){<br /> return findMedianByQuicksort(A,rp+1,right);<br /> }else{<br /> return findMedianByQuicksort(A,left,rp-1);<br /> }<br /> }else{<br /> if(leftCnt==rightCnt){<br /> return A[rp];<br /> }else if(rightCnt > leftCnt){<br /> return findMedianByQuicksort(A,rp+1,right);<br /> }else{<br /> return findMedianByQuicksort(A,left,rp-1);<br /> }<br /> }<br /> }</p> <p> public static void quickSort(int[] A,int left,int right){<br /> if(right<=left)<br /> return;</p> <p> int rp = sortPivot(A,left,right);</p> <p> quickSort(A,left,rp-1);<br /> quickSort(A,rp+1,right);<br /> }<br /> private static int sortPivot(int[] A,int left,int right){<br /> int pivot = A[left];<br /> int lp=left+1;<br /> int rp=right;<br /> while(lp<=rp){//consider the "equal" case: e.g. [-4 0], -4 is pivot<br /> for(;lp<=right;lp++){<br /> if(A[lp]>pivot){<br /> break;<br /> }<br /> }<br /> for(;rp>=left+1;rp--){<br /> if(A[rp]<pivot){<br /> break;<br /> }<br /> }<br /> if(lp < rp){<br /> //swap<br /> int tmp = A[lp];<br /> A[lp]=A[rp];<br /> A[rp] = tmp;<br /> lp++;<br /> rp--;<br /> }<br /> }<br /> //swap pivot with the rp's value<br /> A[left]=A[rp];<br /> A[rp] = pivot;<br /> return rp;<br /> }<br />