顺序统计
问题场景：给定具有n个元素的数组，已知数组是无序的，请找到第k小的元素并返回该元素（TOP K问题）。
根据之前所学的算法我们可以得出一个原始方案：
使用运行时间为Θ (nlgn)的排序算法（堆排序、归并排序）进行排序后返回数组索引为K的元素。
该问题当K为如下特殊值的时候的情形：
- K=1 : 最小值
- K=n : 最大值
-
K=(n-1)/2: 中值
k值表示的不同意义
随机化分治法
- 随机化选择法
用到了前面讲的随机化快速排序的子操作randomizedPartition。
方法的大致运行流程是这样的：
如果开始位置和结束位置一样时算法视为找到，返回开始位置的元素；否则进行随机化分割，当分割后的主元位置和需要查找的第index小的位置对应时视为找到，当前主元就是需要查找的元素。否则，将问题划分为更小规模的问题，如果主元位置p>index那么在[left,p]范围内的数据进行随机化选择操作；否则从主元的右侧进行随机话选择操作。方法介绍完毕，需要注意的是不同的分割导致index的变化是一个需要关注的点。
package me.ziuo.ai.intro;
import java.util.Random;
/**
*
* {48,6,57,88,60,42,83,73,49,85,99,1424,35,242,6567,34,2,5};
*
* ------------------------------------------------
* 随机化选择第 index 小的元素
* top 1 is 2.
* top 2 is 5.
* top 3 is 6.
* top 4 is 34.
* top 5 is 35.
* top 6 is 42.
* top 7 is 48.
* top 8 is 49.
* top 9 is 57.
* top 10 is 60.
* top 11 is 73.
* top 12 is 83.
* top 13 is 85.
* top 14 is 88.
* top 15 is 99.
* top 16 is 242.
* top 17 is 1424.
* top 18 is 6567.
*
* @author eboy
*
* @description 随机化的选择算法，用于求解top k 问题
**/
public class RandomizedSelect {
/**
* @return 随机化主元分割点位置
*
* @param src
* 待划分的数组，分割后的结果保证，mid前的元素都是小于等于它的，右侧的元素都是大于等于它的
* @param left
* 左边界
* @param right
* 右边界
*/
private static int randomizedPartition(int[] src, int left, int right) {
/*随机选取主元元素*/
Random random = new Random();
int random_index = random.nextInt(right-left+1)+left;
//感兴趣的话，可以打印一下主元的位置
// System.out.println("random_index="+random_index);
/**
* 交换
*/
int temp = src[random_index];
src[random_index] = src[left];
src[left]=temp;
int key = src[left];//挖坑
int i = left;
int j = right;
while (i < j) {
while (i < j && src[j] > key) {
j--;
}
if (i < j) {
src[i++] = src[j];// 挖坑填数
}
while (i < j && src[i] < key) {
i++;
}
if (i < j) {
src[j--] = src[i];// 挖坑填数
}
}
src[i] = key;//填空
// 这种情况下第一趟结束 i的坐标都比他小i的右边都比他大
return i;
}
/**
*
* @param src
* @param left
* @param right
* @param index
* @return 返回 第 index 小的元素
*/
public static int randomizedSelect(int[] src, int left, int right, int index) {
if(left==right) return src[left];//待分割的边界到只有一个元素时，该元素作为结果返回
int mid =randomizedPartition(src, left, right);//随机化分割后，主元所在位置
int key=mid-left+1;
if(index==key) return src[mid];
else if(index<key) return randomizedSelect(src, left, mid-1, index);
else return randomizedSelect(src, mid+1, right, index-key);//top i问题分解成top i-key
}
}
该算法的最坏情况的运行时间是Θ(n²);期望运行时间为Θ（n）。
虽然，随机化选择算法的期望运行时间是线性的，但是出现最坏的情况的话效率很低，尽管出现最坏的情况的概率是极其低的。
最终人类还是创造出最坏情况为线性的选择算法。
最坏情况为线性的选择算法
选择算法概述
该算法是对随机化选择主元的优化版本，最坏情况的运行时间是线性的即O(n)。和随机化的选择排序一样，快速选择算法通过对输入数组的递归划分找出所需的元素，但是该算法那能给个保证得到对数组的一个好的划分。快速选择算法使用的也是来自快速排序的确定性划分算法PARTITION,做了部分修改，将划分的主元也作为输入参数。
代码如下：
package me.ziuo.ai.intro;
import java.util.Random;
/**
*
* {7,9,8,6,3,5,2,4,1
,18,10,15,17,10,12,19,14,13
,34,58,79,21,16,53,23,22,11
,23,48,29,16,55,37,28,51,50
,22,18,27,35,53,27,96,88,101}
*
* ------------------------------------------------
* 最坏情况运行时间为线性的选择第 index 小的元素
* top 1 is 1.
* top 2 is 2.
* top 3 is 3.
* top 4 is 4.
* top 5 is 5.
* top 6 is 6.
* top 7 is 7.
* top 8 is 8.
* top 9 is 9.
* top 10 is 10.
* top 11 is 10.
* top 12 is 11.
* top 13 is 12.
* top 14 is 13.
* top 15 is 14.
* top 16 is 15.
* top 17 is 16.
* top 18 is 16.
* top 19 is 17.
* top 20 is 18.
* top 21 is 18.
* top 22 is 19.
* top 23 is 21.
* top 24 is 22.
* top 25 is 22.
* top 26 is 23.
* top 27 is 23.
* top 28 is 27.
* top 29 is 27.
* top 30 is 28.
* top 31 is 29.
* top 32 is 34.
* top 33 is 35.
* top 34 is 37.
* top 35 is 48.
* top 36 is 50.
* top 37 is 51.
* top 38 is 53.
* top 39 is 53.
* top 40 is 55.
* top 41 is 58.
* top 42 is 79.
* top 43 is 88.
* top 44 is 96.
* top 45 is 101.
*
* @author eboy
*
* @description 确定性划分算法的选择算法，用于求解top k 问题
**/
public class Select {
int[] midianArray;//中位数数组
/**
* @return 随机化主元分割点位置
*
* @param src
* 待划分的数组，分割后的结果保证，mid前的元素都是小于等于它的，右侧的元素都是大于等于它的
* @param left
* 左边界
* @param right
* 右边界
*/
private int partition(int[] src, int left, int right,int pivotIndex) {
/**
* 交换
*/
int temp = src[pivotIndex];
src[pivotIndex] = src[left];
src[left]=temp;
int key = src[left];//挖坑
int i = left;
int j = right;
while (i < j) {
while (i < j && src[j] > key) {
j--;
}
if (i < j) {
src[i++] = src[j];// 挖坑填数
}
while (i < j && src[i] < key) {
i++;
}
if (i < j) {
src[j--] = src[i];// 挖坑填数
}
}
src[i] = key;//填空
// 这种情况下第一趟结束 i的坐标都比他小i的右边都比他大
return i;
}
/**
* 最坏情况运行时间为线性的选择排序算法的入口方法
* @param src
* @param left
* @param right
* @param key
* @return
*/
public int qSelect(int[] src, int left, int right, int key){
midianArray=new int[src.length/5 + 1];
return select(src, left, right, key);
}
/**
*
* @param src
* @param left
* @param right
* @param key
* @return 返回 第 index 小的元素
*/
private int select(int[] src, int left, int right, int key) {
/**
* 1.寻找中位数的中位数
* 2.进行递归找到第k小的元素
*/
int median=findMedian(src,left,right);
// System.out.println("median is "+median);
int medianIndex=findMedianIndex(src, left, right, median);
// System.out.println("medianIndex is "+medianIndex);
int pivotIndex =partition(src, left, right,medianIndex);//根据主元进行划分，返回主元划分后的位置
int index=pivotIndex-left+1;
if(key==index) return src[pivotIndex];
else if(key<index) return select(src, left, pivotIndex-1, key);
else return select(src, pivotIndex+1, right, key-index);//top i问题分解成top i-key
}
private int findMedianIndex(int[] src ,int left,int right,int median){
for(int i=left;i<=right;i++){
if(src[i]==median)
return i;
}
return -1;
}
private int findMedian(int[] src, int left, int right) {
if(left==right) return src[left];//范围内只有一个元素时，该元素作为结果返回
/**
* 1.元素分组：将输入数组中的n个元素划分为【n/5】个中位数，且至多只有一组由剩下的n mod 5个元素组成。
* 2.寻找【n/5】个中位数：首先对没组元素进行插入排序，然后确定每组元素的中位数。
* 3.找到中位数：找出中位数的中位数。
*/
//1.元素分组
//2.寻找【n/5】个中位数
int index;
for(index=left;index<right-5;index+=5){//分组整除部分的数据
insertSort(src,index,4);
int num=index - left;
midianArray[num/5]=src[index+2];//中位数赋值
}
//分组余下的元素
int remainNum=right-index+1;
if(remainNum>0){
insertSort(src,index,remainNum-1);
int num=index - left;
midianArray[num/5]=src[index+remainNum/2];//中位数赋值
}
//3. 递归找到中位数的中位数
int elemAuxArray=(right-left)/5-1;
if((right-left)%5!=0) elemAuxArray++;
if(elemAuxArray==0)
return midianArray[elemAuxArray];
else
return findMedian(midianArray,0,elemAuxArray);
}
/**
* 子数组插入排序
* @param src 母数组
* @param left 开始为止
* @param loopLength 步长
*/
private void insertSort(int[] src, int left, int loopLength) {
for(int j=left; j<left+loopLength;j++){
int key=src[j];
int i=j-1;
while(i>left && src[i]>key){
src[i+1]=src[i];
i--;
}
src[i+1]=key;
}
}
}
测试代码如下：
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr ={48,6,57,88,60,42,83,73,49,85};
/**
* random_index=9
* random_index=3
* random_index=1
* random_index=2
* random_index=6
* =4
* random_index=5
* sorted is {6,42,48,49,57,60,73,83,85,88}
*/
System.out.println("------------------------------------------------");
System.out.println("随机化选快排的运算过程");
RandomizedQuickSort.randomizedQuickSort(arr,0, arr.length-1);
for(int i=0;i<arr.length;i++){
if(i==arr.length-1) System.out.print(arr[i]);
else System.out.print(arr[i]+",");
}
System.out.println("");
System.out.println("------------------------------------------------");
System.out.println("随机化选择第 index 小的元素");
/**
* 随机化选择第 index 小的元素
*/
int[] arr2 ={48,6,57,88,60,42,83,73,49,85,99,1424,35,242,6567,34,2,5};
for(int i=0;i<arr2.length;i++){
int indexMin=RandomizedSelect.randomizedSelect(arr2, 0, arr2.length-1, i+1);
System.out.println("top "+(i+1)+" is "+indexMin+".");
}
System.out.println("------------------------------------------------");
System.out.println("最坏情况运行时间为线性的选择第 index 小的元素");
/**
* 最坏情况运行时间为线性的选择第 index 小的元素
*/
int[] arr3 ={7,9,8,6,3,5,2,4,1
,18,10,15,17,10,12,19,14,13
,34,58,79,21,16,53,23,22,11
,23,48,29,16,55,37,28,51,50
,22,18,27,35,53,27,96,88,101};
for(int i=0;i<arr3.length;i++){
Select select=new Select();
int indexMin=select.qSelect(arr3, 0, arr3.length-1, i+1);
System.out.println("top "+(i+1)+" is "+indexMin+".");
}
}
控制台打印
------------------------------------------------
随机化选快排的运算过程
random_index=4
random_index=1
random_index=3
random_index=2
random_index=2
random_index=8
random_index=8
6,42,48,49,57,60,73,83,85,88
------------------------------------------------
随机化选择第 index 小的元素
top 1 is 2.
top 2 is 5.
top 3 is 6.
top 4 is 34.
top 5 is 35.
top 6 is 42.
top 7 is 48.
top 8 is 49.
top 9 is 57.
top 10 is 60.
top 11 is 73.
top 12 is 83.
top 13 is 85.
top 14 is 88.
top 15 is 99.
top 16 is 242.
top 17 is 1424.
top 18 is 6567.
------------------------------------------------
最坏情况运行时间为线性的选择第 index 小的元素
top 1 is 1.
top 2 is 2.
top 3 is 3.
top 4 is 4.
top 5 is 5.
top 6 is 6.
top 7 is 7.
top 8 is 8.
top 9 is 9.
top 10 is 10.
top 11 is 10.
top 12 is 11.
top 13 is 12.
top 14 is 13.
top 15 is 14.
top 16 is 15.
top 17 is 16.
top 18 is 16.
top 19 is 17.
top 20 is 18.
top 21 is 18.
top 22 is 19.
top 23 is 21.
top 24 is 22.
top 25 is 22.
top 26 is 23.
top 27 is 23.
top 28 is 27.
top 29 is 27.
top 30 is 28.
top 31 is 29.
top 32 is 34.
top 33 is 35.
top 34 is 37.
top 35 is 48.
top 36 is 50.
top 37 is 51.
top 38 is 53.
top 39 is 53.
top 40 is 55.
top 41 is 58.
top 42 is 79.
top 43 is 88.
top 44 is 96.
top 45 is 101.
算法系列文章，因为水平所限，只做记录，不做过多介绍。
以上，谢谢阅读，希望你有所收获！
以上，谢谢阅读，希望你有所收获！
算法导论公开课笔记（一）算法分析与设计
算法导论公开课笔记（二）快速排序和随机化算法
算法导论公开课笔记（三）线性时间排序
算法导论公开课笔记（四）顺序统计、中值
动态规划算法
