什么是次序选择：
就是需要找出给定序列中第k小元素（其中k大于等于1小于等于n）。
比如当k=3时，我们需要找出该序列中第三小元素。
分治法解决次序选择问题：
我们可以借用随机主元的快速排序的思维去解决该问题（点击查看本人另一篇博文随机化快速排序：随机化快速排序），与快速排序不同的是，在主元下标等于k时，我们就可以直接退出，不需要再进行剩下的分解问题和合并问题解过程。其时间复杂度的数学期望为O(n)，是一个非常高效的算法。
比如我们要寻找第4小元素，给定数组为945721683，下面我们对其进行分析：
开始——>（比主元大的用蓝色表示，比主元小的用橙色表示，i指向数组首端的前一个，j指向数组首端，即i=left-1，j=left）.
刚开始i指向空，j指向9.
1.随机选择主元，假设选择主元为6；
2.主元6与末尾3交换，变为：945721386
3.主元6与j所指9比较，比6小，j++，j指向4，数组变为：945721386
4.主元6与j所指4比较，比4大，i++，i此时指向9，i与j交换，j++，变为：495721386
5.主元6与j所指5比较，比5大，i++，i此时指向9，i与j交换，j++，变为：459721386
6.主元6与j所指7比较，比7小，j++，变为：457921386
7…省略2138的比较与上述类似，变为：452139786
8.j指向了数组最后一个，即主元，则i+1与主元交换，即9与主元6交换
9.然后判断第4小元素，即k=4与主元下标i+1的大小，若k<i+1,则选取左半边重复上述过程；如果k>i+1,则选取右半边重复上述过程.
直到交换后的主元下标等于k。
代码部分：
public void toSelection(int []arr,int left,int right,int k) {
int principalElement = left+(int)(Math.random()*(right-left+1)); //选取随机主元
//把随机主元放到数组尾部
int temp = arr[principalElement];
arr[principalElement] = arr[right];
arr[right] = temp;
int i = left -1;
for(int j = left;j<right;j++) {
if(arr[j]<arr[right]) {
++i;
int temp1 = arr[j];
arr[j] = arr[i];
arr[i] = temp1;
}
}
int temp2 = arr[right];
arr[right] = arr[i+1];
arr[i+1] = temp2;
if(k == i+1)
System.out.print("第"+(k+1)+"小数为:"+arr[k]);
if(k<i+1)
toSelection(arr,left,i,k);
if(k>i+1)
toSelection(arr, i+2, right, k);
}
AI 代码解读
函数调用，运行结果：
