线性时间选择 --- Java实现

定义：给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素。

主要思想：将线性集的n个元素划分为n/5组，取出每组中位数，得到中位数的中位数（偶数取中间较大那个数），将此数作为基数进行一次快排，缩小查找范围，然后再次从分组到快排的步骤，不断缩小范围，直到缩小到自己指定的足够小的范围内，直接进行一个排序，得到最后的结果。

假设：一个数组a有25个元素，按照线性时间选择找出其第k小的数，设左指针为p,右指针为r。

将25个元素分为每5个作为一组，黑色是每组待排序的中位数所在位置

使用冒泡排序（任何排序算法都行），将每组排序好取出中位数数组

 将中位数数组进行排序，得到中位数的中位数，这个数就是能找到的最接近中间的数，后面再使用快速排序的时候，以此数作为基数可以快速排除一大半元素

最后就是不断重复以上步骤缩小范围，直到得到最后的结果 

下面用代码实现下面的题目

 主要的线性时间算法

private static int SelectSort(int[] a, int p, int r, int k) {
		
		//设置一个最小范围 r-p<5时，冒泡排序返回结果a[p+k-1](这里-1是因为数组下标是从0开始算的，第几小是从1开始算的)
		if(r-p<5) {
			BubbleSort(a,p,r);
			//输出一下，方便后面比对结果的准确性
			System.out.println(Arrays.toString(a));
			return a[p+k-1];
		}
		
		//下面就是没到最小范围，所以需要不断的划分范围
		//划分范围的步骤;找中位数--找中位数的中位数--一次快排--递归调用--得结果/再次划分范围
		
		//找中位数。大于75分开选择，一共分成（(r-p-4)/5）+1组
		for(int i=0; i<=(r-p-4)/5; i++) {
			//每个分组的开头
			int s = p+5*i;
			//每个分组的结尾
			int t = s+4;
			//得到每组中的第三小元素
			for(int j=0; j<3; j++) {
				//注意：这个冒泡不是完整的排序，而是冒泡的第二层排序
				Bubbling(a, s, t-j);
			}
			//把中位数全部交换放在前排
			Swap(a, p+i, s+2);
		}
		
		//找中位数的中位数 ,对中位数数组进行线性时间选择得出其中位数，偶数数量取中间数较大那个
		SelectSort(a, p, p+(r-p-4)/5, (r-p+6)/10);
		//将得到的中位数放在第一位
		Swap(a,p,p+(r-p+6)/10-1);
		//得到中位数的正确位置，且左小右大已定，中位数为划分界
		int i = partition(a,p,r);
		//赋值j为基准元素的后一个，即第j小
		int j = i-p+1;
		//将基准元素和要求得k进行比较
		if(k<=j) {
			return SelectSort(a,p,i,k);
		}else {
			//这里k-j的意思是，要减去前面的第j小
			return SelectSort(a,i+1,r,k-j);
		}
	}

 上面算法调用到的如下

快速排序分割算法

private static int partition(int[] a, int p, int r) {
		//基准元素
		int x = a[p];
		//游标
		int i = p; //左边游标
		int j = r+1; //右边游标
		while(true) {
			while(a[++i]<=x&&ix);
			if(i>=j) {
				break;
			}
			Swap(a,i,j);
		}
		a[p] = a[j];
		a[j] = x;
		return j;
	}

数组内数据交换

private static void Swap(int[] a, int l, int r) {
		int temp = a[l];
		a[l] = a[r];
		a[r] = temp;	
	}

冒泡排序的第二层排序

private static void Bubbling(int[] a, int p, int r) {
		for(int i=p; ia[i+1]) {
				Swap(a,i,i+1);
			}
		}
	}

冒泡排序

private static void BubbleSort(int[] a, int p, int r) {
		//减少冗余比较
		boolean judge = false;
		for(int i=0; ia[j+1]) {
					Swap(a,j,j+1);
					judge = true;
				}
			}
			//当不在有交换产生时，说明序列已经是有序的了，就可以跳出循环，减少多余的比较了
			if(!judge) {
				break;
			}
		}
	}