线性选择java描述

使用五位数中值取中分割法的快速选择算法的运行时间为O（n）定理：如果（a1+a2+···+ak)1(k0),则方程T(N)T(a1N)+T(a2N)+···+T(akN)+O(

使用五位数中值取中分割法的快速选择算法的运行时间为O（n）

定理：如果（a₁+a₂+···+a_k)0),则方程T(N)=T(a₁N)+T(a₂N)+···+T(a_kN)+O(N)的解为T(N)=O(N)

分析：如果有10k+5个数组成的数组，在这种情况下，对这个数组进行五位数一组的分割，一共得到2k+1组数，则存在k个小于中值的中值的数（命名为S）和k个大于中值的中值的数（命名为L），至少有（k+2k+2）S和（k+2k+2）个L。于是在这种情况下，递归调用最多可以包含(10k+5)-(3k+2)-1=7k+2个数，7k+2<0.7*(10k+5)。而对分组的中值取中采用递归，时间复杂度为T(N/5)。对N/5个组进行5个数的冒泡排序，时间复杂度为O(N)。因此总的运行时间为 T(N)=T(0.7N)+T(0.2N)+O(N)，根据定理知运行时间为O（N）.

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) { 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=j) { break; } int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } return j; }}

【文章原创作者：香港云服务器 http://www.558idc.com/ne.html 复制请保留原URL】