顺序统计、中值 计算中位数---随机选择算法

本文主要是介绍顺序统计、中值 计算中位数---随机选择算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

random-partition 

随机选择算法获得第i小的数，如果i=n/2代表计算中位数

代码:

public static void main(String[] args) {//[1, 5, 9, 12, 15, 16, 30, 45, 23, 20]int[] arr = {12,20,5,16,15,1,30,45,23,9};int i = randomized_select(arr, 0, arr.length - 1, 5);System.out.println("=========================");System.out.println(i);}public static int randomized_select(int[] arr,int p,int r,int i){if(p==r){return arr[p];}int q=partition(arr,p,r);int k=q-p+1;if(i==k){return arr[q];}else if(i<k){return randomized_select(arr,p,q-1,i);}else{return randomized_select(arr,q+1,r,i-k);}}public static int partition(int[] arr,int left,int right){int privo=arr[(right-left)/2+left];System.out.println(privo);//退出循环的条件 left>rightwhile(left<=right){while(arr[left]<privo){left++;}while(arr[right]>privo){right--;}if(left<=right){swap(arr,left,right);System.out.println(Arrays.toString(arr));left++;right--;}}return left;}public static void swap(int[] arr,int i,int j){int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}

参考

1.https://www.cnblogs.com/xiaoZQ/articles/5244816.html

2.麻省理工学院公开课：算法导论-顺序统计、中值-网易公开课 

这篇关于顺序统计、中值 计算中位数---随机选择算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---