中值问题是求一个n个数列表中某一数组下标k，它要求该下标元素比列表中的一半元素大，又比另一半元素小，这个中间的值被称为中值。
使用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