目录
1 问题描述
中值问题是求一个n个数列表中某一数组下标k，它要求该下标元素比列表中的一半元素大，又比另一半元素小，这个中间的值被称为中值。
选择问题是求一个n个数列表的第k个最小元素的问题。
2 解决方案
2.1 计算中值问题
本文使用Lomuto划分算法思想，此处引用《算法设计与分析基础》第三版上一段文字介绍及配图，具体如下：
具体实现代码如下：
package com.liuzhen.chapter4;public class MedianProblem { //Lomuto划分 /* * 参数A：给定的随机数数组 * 参数start：开始进行选择的数组元素位置 * 参数end：最后一个进行选择的数组元素位置 * 函数功能：返回A[start]到A[end]元素中间的某一元素位置result，使得 左边部分元素 < A[result] <=右边部分元素 */ public int LomutoPartition(int[] A,int start,int end){ int begin = A[start]; int result = start; for(int i = start+1;i <= end;i++){ if(A[i] < begin){ /* * 一旦出现小于begin的元素，result向后移动一位； * 出现大于的不移动，当再次出现小于begin的元素，result向后移动一位， * 此时result恰好指向第一个大于begin的元素，此时执行swap(A,result,i) */ result = result + 1; swap(A,result,i); } } swap(A,start,result); return result; } //交换数组中位置为m和n上的元素值 public void swap(int[] A,int m,int n){ int temp = A[m]; A[m] = A[n]; A[n] = temp; } public static void main(String[] args){ MedianProblem test = new MedianProblem(); int[] A = {4,1,10,8,7,12,9,2,15}; int result = test.LomutoPartition(A, 0, A.length-1); System.out.println("对数组进栈Lomuto划分后结果："); for(int i = 0;i < A.length;i++) System.out.print(A[i]+" "); System.out.println("\n"+"进行Lomuto划分后的数组中轴位置："+result); }} 运行结果：
对数组进栈Lomuto划分后结果：2 1 4 8 7 12 9 10 15 进行Lomuto划分后的数组中轴位置：2
2.2 选择问题
通过2.1 计算中值问题中Lomuto算法的运用，那么如何寻找n个元素中第k个最小元素呢？此处调用2.1中相关函数，具体实现代码如下：
package com.liuzhen.chapter4;public class SelectProblem { //快速选择 /* * 参数A:给定随机数数组 * 参数k:要求输出的第k个最小元素 * 函数功能：返回数组A的第k个最小元素的值 */ public int quickSelect(int[] A,int k){ int start = 0; int end = A.length-1; int mid = new MedianProblem().LomutoPartition(A, start,end); while(true){ if(mid > k-1){ end = mid-1; mid = new MedianProblem().LomutoPartition(A, start,end); } else if(mid < k-1){ start = mid+1; mid = new MedianProblem().LomutoPartition(A, start,end); } else break; } return A[mid]; } public static void main(String[] args){ SelectProblem test = new SelectProblem(); int[] A = {4,1,10,8,7,12,9,2,15}; int result = test.quickSelect(A, 5); System.out.println("对数组进行快速选择并执行划分后结果："); for(int i = 0;i < A.length;i++) System.out.print(A[i]+" "); System.out.println("\n"+"进行快速选择后得到数组第5最小元素（从小到大排序）："+result); }} 运行结果：
对数组进行快速选择并执行划分后结果：2 1 4 7 8 12 9 10 15 进行快速选择后得到数组第5最小元素（从小到大排序）：8