- public class FindKthLargestNum { public static void main(String[] args) {
- int[] arr= {1,3,5,7,9,10,8,6,4,2,11,13,15,17,19,20,18,16,14,12};
- for(int i=0;i<arr.length;i++) {
- System.out.print(select(arr,0,arr.length-1,i+1)+" ");
- }
- }
- //select 算法
- public static int select(int[] array,int begin,int end,int k) {
- //begin 到 end 不超过 5 个数, 采用冒泡算法先排序后将第 k 小的数输出, 也是递归的出口
- if(end-begin+1<=5) {
- bubbleSort(array,begin,end);
- return array[begin+k-1];
- }
- // 将数组中的数据按五个一组分组并用冒泡排序将每组中的五个数排序, 找出各组的中值, 依次放在数组的前端
- // 这样就可以对数组的第 0 到 group 个数递归调用 select 排序
- int group=(end-begin+1)/5;
- for(int i=0;i<group;i++) {
- int left=begin+i*5;
- int right=begin+(i+1)*5-1;
- int mid=(left+right)/2;
- bubbleSort(array,left,right);
- int temp=array[begin+i];
- array[begin+i]=array[mid];
- array[mid]=temp;
- }
- // 递归调用 select 找出各组中值的中值
- int m=select(array,begin,begin+group-1,(group+1)/2);
- // 将比 m 小的值放在 m 左边, 比 m 大的放在 m 右边, 并返回 m 的下标 j
- int j=partition(array,begin,end,m);
- // 从 begin 开始, j 前面的元素个数为 leftnum
- int leftnum=j-begin;
- if(k==leftnum+1) {
- return array[j];
- }
- else if (k<=leftnum+1) {
- return select(array,begin,j-1,k);
- }else{
- return select(array,j+1,end,k-leftnum-1);
- }
- }
- // 冒泡排序
- public static void bubbleSort(int[] arr,int begin,int end) {
- for(int i=begin,k=0;i<end;i++,k++) {
- for(int j=begin;j+1<=end-k;j++) {
- if(arr[j]>arr[j+1]) {
- int temp=arr[j+1];
- arr[j+1]=arr[j];
- arr[j]=temp;
- }
- }
- }
- }
- // 把比 X 小的房 X 左边, 比 X 大的放 X 右边, 返回排序后 X 的下标
- public static int partition(int[] arr,int begin,int end,int x) {
- int i=begin;
- int j=end;
- while(true) {
- while(arr[i]<x&&i<end) {
- ++i;
- }
- while(arr[j]>x) {
- --j;
- }
- if(i>=j) {
- break;
- }
- int temp=arr[i];
- arr[i]=arr[j];
- arr[j]=temp;
- }
- return j;
- }
- }
来源: http://www.bubuko.com/infodetail-2721091.html