查找无序数组的中位数，要想时间复杂度为O(n)其实用计数排序就能很方便地实现，在此讨论使用快速排序进行定位的方法。
1、中位数定义
2、算法思想
3、Java代码实现
4、时间复杂度分析
5、附录
中位数一般两种定义：
第一种：
排序后数组的中间位置的值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。
第一种(官方)：
排序后数组的中间位置的值，如果数组的个数是偶数个，则返回最中间两个数的平均数。
例如：{ 7, 9, 4, 5} 　　第一种输出5；第二种输出6.0
算法思想：大家应该都知道，快速排序每一躺都能定位一个数在这个数组的最终位置，所以可以利用此特性对数组中任意一个位置进行二分法定位。
方法就是：一趟快排的partition结束之后，将此时定位的位置与欲定位位置进行比较，如果不等于，则将partition的区间折半，直到等于为止，返回这个位置的值
Java代码实现：
因为第二种中位数定义需要定位两个位置，在第一种上扩展即可，所以先讨论第一种：
1     public static intgetMedian(int[] nums) {2         return partition(nums, 0, nums.length - 1);3 }4
5     private static int partition(int[] nums, int start, intend) {6         /***快排partition函数原代码——start***/
7         int left =start;8         int right = end + 1;9
10         int point =nums[start];11         while (true) {12             while (left < right && nums[--right] >=point)13 ;14             while (left < right && nums[++left] <=point)15 ;16             if (left ==right) {17                 break;18             } else{19                 int tmp =nums[left];20                 nums[left] =nums[right];21                 nums[right] =tmp;22 }23 }24         nums[start] =nums[left];25         nums[left] =point;26         /***快排partition函数原代码——end***/
27
28         /***定位判断***/
29         if (left == (nums.length - 1) / 2) {30             returnnums[left];31         } else if (left > (nums.length - 1) / 2) {32             return partition(nums, start, left - 1);33         } else{34             return partition(nums, left + 1, end);35 }36     }
其实就是在原来的partition结束后加了一个定位判断，此时left指向的就是已经本趟定位的那一个数，如果没有定位成功则将上下界调整折半。
【注意】：“如果数组的个数是偶数个，则返回排序后数组的第N/2个数”这句话需要用 (nums.length - 1) / 2 来实现这句描述的下标，并满足奇数时取最中间下标的效果。
时间复杂度分析：
由于此方法采用的也是递归，那么必定符合递归的复杂度通项表达式： T(n) = aT(n/b) + f(n)
其中a为每次递归会分成几个需要计算的下一层，(n/b)为下一层计算的元素个数，f(n)为本层的计算复杂度
由于是折半查找，所以有：a=1、b=2(平均)、f(n)=n(每次的遍历比较交换)
所以有
T(n) = T(n/2) +n=  T(n/4) + n/2 +n
……= T(1) + 2 + …… + n/2 +n    //T(1)≈1 等比数列求和
= (1 - n * 2)/(1 - 2)= 2n - 1
所以最后平均时间复杂度为O(n)
【最优情况下b=n复杂度O(n);
最坏情况下b=n-1/n，也就是(n/b)=(n-1),此时复杂度为O(n²)，请自行计算哈】
附录——第二种求中位数的实现
思路：第一种已经解决了定位一个数字，而第二种就是定位两个数字，由于定位一个数字的时候不能保证另一个数字已经排序好，所以还需重新调用方法
那么就把方法中定位判断的部分单独移出来做一个getByQuickSort(int[] nums，int stop)
java代码实现：
1     public static double getByQuickSort(int[] nums, intstop) {2         if (stop < 0 || stop >=nums.length) {3             throw newIndexOutOfBoundsException();4 }5
6         int start = 0;7         int end = nums.length -1;8         int par = 0;9
10         while (start <=end) {11             par =partition(nums, start, end);12             if (par ==stop) {13                 break;14             } else if (par >stop) {15                 end = par - 1;16             } else{17                 start = par + 1;18 }19 }20         returnnums[par];21     }
此处的partition(...)方法就是上一段代码中的partition方法中把 /***定位判断***/ 以下都去掉，然后加一个 return left； 即可。
而找中位数就再写一个方法getMedian2(...)判断一下奇偶，再调用getByQuickSort(....)就可以了：
1     public static doublegetMedian2(int[] nums) {2         if (nums.length % 2 == 1) {3             return getByQuickSort(nums, nums.length / 2);4         } else{5             return (getByQuickSort(nums, nums.length / 2 - 1) +
6                     getByQuickSort(nums, nums.length / 2)) / 2.0;7 }8     }

根据快排的思路来做
题目简化为求某个数组的最中间的两个数，然后根据快排的思路进行排除即可，相对于快排大大减少了比较的次数，代码如下： import java.util.*;
public class Main{
// 利用快排的思路寻找一个数组中第target大的数
private static int getTarget(int[] data, int target){
int mid=data[0], l=0, r=data.length-1;
while(l < r){
while(l < r && data[r] > mid)
r--;
if(l < r)
data[l++] = data[r];
while(l < r && data[l] < mid)
l++;
if(l < r)
data[r--] = data[l];
}
data[l] = mid;
if(l+1 == target)
return data[l];
else if(l+1 < target)
return getTarget(Arrays.copyOfRange(data, l+1, data.length), target-(l+1));
else
return getTarget(Arrays.copyOfRange(data, 0, l), target);
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt()){
int n = sc.nextInt();
if(n == 0)
break;
int[] data = new int[n];
for(int i=0; i
data[i] = sc.nextInt();
// 寻找一个数组中最中间的两个数
int mid1 = (data.length+1)/2;
int mid2 = (data.length+2)/2;
System.out.println((getTarget(data, mid1)+getTarget(data, mid2))/2);
}
sc.close();
}
}

最近工作需要 要求把python的代码写成java版本，python中有一个np.median()求中位数的方法，java决定手写一个
先说说什么是中位数：
中位数就是中间的那个数，
如果一个集合是奇数个，那么中位数就是按大小排列后，最中间那个数，
如果一个集合是偶数个，那么中位数就是按大小排列后，最中间那2个数的平均数。
比如：
1，2，3，4，5 那中位数就是3
1，2，3，4，5，6 那中位数就是 (3+4)/2 = 3.5
知道逻辑后方法就很简单了 下面是代码
public static void main(String[] args) {
List total = new ArrayList();
total.add(4);
total.add(2);
total.add(3);
total.add(1);
total.add(5);
total.add(6);
double a = median(total);
System.out.println(a);
}
private static double median(List total) {
double j = 0;
//集合排序
Collections.sort(total);
int size = total.size();
if(size % 2 == 1){
j = total.get((size-1)/2);
}else {
//加0.0是为了把int转成double类型，否则除以2会算错
j = (total.get(size/2-1) + total.get(size/2) + 0.0)/2;
}
return j;
}
1. 方法内先判断集合是奇数还是偶数，如果是奇数那么就是第n+1/2个数 ，也就是下标为n-1/2的值，
如果是偶数 就是第n/2和n/2+1的数的平均值 也就是下标为n/2-1和n/2的平均值
2. 该方法传入的是list集合 如果为数组 可以先用Arrays.aslist()方法转换后传入
补充知识：Java计算中位数、方差、标准差、众数
我就废话不多说了，大家还是直接看代码吧~
import java.text.DecimalFormat;
import java.util.*;
/**
* 数学算法(数学算法(方差、标准差、中位数、众数))
* @author
*
*/
public class MathAlgorithm {
private final static double dmax = 999;// Double.MAX_VALUE;//Double类型的最大值，太大的double值，相乘会达到无穷大
private final static double dmin = Double.MIN_VALUE;// Double类型的最小值
private final static int n = 100;// 假设求取100个doubl数的方差和标准差
public static void main(String[] args) {
Random random = new Random();
double[] x = new double[n];
for (int i = 0; i < n; i++) {// 随机生成n个double数
x[i] = Double.valueOf(Math.floor(random.nextDouble() * (dmax - dmin)));
System.out.println(x[i]);
}
// 设置doubl字符串输出格式，不以科学计数法输出
DecimalFormat df = new DecimalFormat("#,##0.00");// 格式化设置
// 计算方差
double dV = getVariance(x);
System.out.println("方差=" + df.format(dV));
// 计算标准差
double dS = getStandardDiviation(x);
System.out.println("标准差=" + df.format(dS));
int[] intArr={5,10,15,8,6};
System.out.println(Arrays.toString(intArr)+" 中位数:"+median(intArr));
int[] intArr2={5,10,15,8,6,7};
System.out.println(Arrays.toString(intArr2)+" 中位数:"+median(intArr2));
int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 2, 2, 3, 4, 5};
List modalNums = getModalNums(arr);
System.out.println("众数："+modalNums);
float[] arr2 = {0.1f, 1.1f, 2.1f, 3.1f, 4.1f, 5.1f, 6.1f, 7.1f, 8.1f, 9.1f, 10.1f, 1.1f, 1.1f, 2.1f, 2.1f, 3.1f, 4.1f, 5.1f};
List modalNums2 = getModalNums(arr2);
System.out.println("众数："+modalNums2);
}
/**
* 方差s^2=[(x1-x)^2 +...(xn-x)^2]/n
* @param x
* @return
*/
public static double getVariance(double[] x) {
int m = x.length;
double sum = 0;
for (int i = 0; i < m; i++) {// 求和
sum += x[i];
}
double dAve = sum / m;// 求平均值
double dVar = 0;
for (int i = 0; i < m; i++) {// 求方差
dVar += (x[i] - dAve) * (x[i] - dAve);
}
return dVar / m;
}
/**
* 标准差σ=sqrt(s^2)
* @param x
* @return
*/
public static double getStandardDiviation(double[] x) {
int m = x.length;
double sum = 0;
for (int i = 0; i < m; i++) {// 求和
sum += x[i];
}
double dAve = sum / m;// 求平均值
double dVar = 0;
for (int i = 0; i < m; i++) {// 求方差
dVar += (x[i] - dAve) * (x[i] - dAve);
}
return Math.sqrt(dVar / m);
}
/**
* 中位数(int)
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
public static int median(int []nums){
if(nums.length==0)
return 0;
int start=0;
int end=nums.length-1;
int index=partition(nums, start, end);
if(nums.length%2==0){
while(index!=nums.length/2-1){
if(index>nums.length/2-1){
index=partition(nums, start, index-1);
}else{
index=partition(nums, index+1, end);
}
}
}else{
while(index!=nums.length/2){
if(index>nums.length/2){
index=partition(nums, start, index-1);
}else{
index=partition(nums, index+1, end);
}
}
}
return nums[index];
}
private static int partition(int nums[], int start, int end){
int left=start;
int right=end;
int pivot=nums[left];
while(left
while(left=pivot){
right--;
}
if(left
nums[left]=nums[right];
left++;
}
while(left
left++;
}
if(left
nums[right]=nums[left];
right--;
}
}
nums[left]=pivot;
return left;
}
/**
* 中位数(float)
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
public static float median(float []nums){
if(nums.length==0)
return 0;
int start=0;
int end=nums.length-1;
int index=partition(nums, start, end);
if(nums.length%2==0){
while(index!=nums.length/2-1){
if(index>nums.length/2-1){
index=partition(nums, start, index-1);
}else{
index=partition(nums, index+1, end);
}
}
}else{
while(index!=nums.length/2){
if(index>nums.length/2){
index=partition(nums, start, index-1);
}else{
index=partition(nums, index+1, end);
}
}
}
return nums[index];
}
private static int partition(float nums[], int start, int end){
int left=start;
int right=end;
float pivot=nums[left];
while(left
while(left=pivot){
right--;
}
if(left
nums[left]=nums[right];
left++;
}
while(left
left++;
}
if(left
nums[right]=nums[left];
right--;
}
}
nums[left]=pivot;
return left;
}
/**
* 众数(int)
* 众数:在一个数组中出现次数最多的数
* 如果存在多个众数，则一起返回
* @param arr
* @return
*/
public static List getModalNums(int[] arr) {
int n = arr.length;
if (n == 0) {
return new ArrayList();
}
if (n == 1) {
return Arrays.asList(arr[0]);
}
Map freqMap = new HashMap<>();
for (int i = 0; i < n; i++) { // 统计数组中每个数出现的频率
Integer v = freqMap.get(arr[i]);
// v == null 说明 freqMap 中还没有这个 arr[i] 这个键
freqMap.put(arr[i], v == null ? 1 : v + 1);
}
// 将 freqMap 中所有的键值对(键为数，值为数出现的频率)放入一个 ArrayList
List> entries = new ArrayList<>(freqMap.entrySet());
// 对 entries 按出现频率从大到小排序
Collections.sort(entries, new Comparator>() {
@Override
public int compare(Map.Entry e1, Map.Entry e2) {
return e2.getValue() - e1.getValue();
}
});
List modalNums = new ArrayList<>();
modalNums.add(entries.get(0).getKey()); // 排序后第一个 entry 的键肯定是一个众数
int size = entries.size();
for (int i = 1; i < size; i++) {
// 如果之后的 entry 与第一个 entry 的 value 相等，那么这个 entry 的键也是众数
if (entries.get(i).getValue().equals(entries.get(0).getValue())) {
modalNums.add(entries.get(i).getKey());
} else {
break;
}
}
return modalNums;
}
/**
* 众数(float)
* 众数:在一个数组中出现次数最多的数
* 如果存在多个众数，则一起返回
* @param arr
* @return
*/
public static List getModalNums(float[] arr) {
int n = arr.length;
if (n == 0) {
return new ArrayList();
}
if (n == 1) {
return Arrays.asList(arr[0]);
}
Map freqMap = new HashMap<>();
for (int i = 0; i < n; i++) { // 统计数组中每个数出现的频率
Integer v = freqMap.get(arr[i]);
// v == null 说明 freqMap 中还没有这个 arr[i] 这个键
freqMap.put(arr[i], v == null ? 1 : v + 1);
}
// 将 freqMap 中所有的键值对(键为数，值为数出现的频率)放入一个 ArrayList
List> entries = new ArrayList<>(freqMap.entrySet());
// 对 entries 按出现频率从大到小排序
Collections.sort(entries, new Comparator>() {
@Override
public int compare(Map.Entry e1, Map.Entry e2) {
return e2.getValue() - e1.getValue();
}
});
List modalNums = new ArrayList<>();
modalNums.add(entries.get(0).getKey()); // 排序后第一个 entry 的键肯定是一个众数
int size = entries.size();
for (int i = 1; i < size; i++) {
// 如果之后的 entry 与第一个 entry 的 value 相等，那么这个 entry 的键也是众数
if (entries.get(i).getValue().equals(entries.get(0).getValue())) {
modalNums.add(entries.get(i).getKey());
} else {
break;
}
}
return modalNums;
}
}
以上这篇java 计算中位数的实现方法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持聚米学院。

最近工作需要 要求把python的代码写成java版本，python中有一个np.median()求中位数的方法，java决定手写一个
先说说什么是中位数：
中位数就是中间的那个数，
如果一个集合是奇数个，那么中位数就是按大小排列后，最中间那个数，
如果一个集合是偶数个，那么中位数就是按大小排列后，最中间那2个数的平均数。
比如：
1，2，3，4，5 那中位数就是3
1，2，3，4，5，6 那中位数就是 (3+4)/2 = 3.5
知道逻辑后方法就很简单了 下面是代码
public static void main(String[] args) {
Listtotal = new ArrayList();
total.add(4);
total.add(2);
total.add(3);
total.add(1);
total.add(5);
total.add(6);
double a = median(total);
System.out.println(a);
}
private static double median(Listtotal) {
double j = 0;
//集合排序
Collections.sort(total);
int size = total.size();
if(size % 2 == 1){
j = total.get((size-1)/2);
}else {
//加0.0是为了把int转成double类型，否则除以2会算错
j = (total.get(size/2-1) + total.get(size/2) + 0.0)/2;
}
return j;
}
1. 方法内先判断集合是奇数还是偶数，如果是奇数那么就是第n+1/2个数 ，也就是下标为n-1/2的值，
如果是偶数 就是第n/2和n/2+1的数的平均值 也就是下标为n/2-1和n/2的平均值
2. 该方法传入的是list集合 如果为数组 可以先用Arrays.aslist()方法转换后传入
补充知识：Java计算中位数、方差、标准差、众数
我就废话不多说了，大家还是直接看代码吧~
import java.text.DecimalFormat;
import java.util.*;
/**
* 数学算法(数学算法(方差、标准差、中位数、众数))
* @author
*
*/
public class MathAlgorithm {
private final static double dmax = 999;// Double.MAX_VALUE;//Double类型的最大值，太大的double值，相乘会达到无穷大
private final static double dmin = Double.MIN_VALUE;// Double类型的最小值
private final static int n = 100;// 假设求取100个doubl数的方差和标准差
public static void main(String[] args) {
Random random = new Random();
double[] x = new double[n];
for (int i = 0; i < n; i++) {// 随机生成n个double数
x[i] = Double.valueOf(Math.floor(random.nextDouble() * (dmax - dmin)));
System.out.println(x[i]);
}
// 设置doubl字符串输出格式，不以科学计数法输出
DecimalFormat df = new DecimalFormat("#,##0.00");// 格式化设置
// 计算方差
double dV = getVariance(x);
System.out.println("方差=" + df.format(dV));
// 计算标准差
double dS = getStandardDiviation(x);
System.out.println("标准差=" + df.format(dS));
int[] intArr={5,10,15,8,6};
System.out.println(Arrays.toString(intArr)+" 中位数:"+median(intArr));
int[] intArr2={5,10,15,8,6,7};
System.out.println(Arrays.toString(intArr2)+" 中位数:"+median(intArr2));
int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 1, 2, 2, 3, 4, 5};
ListmodalNums = getModalNums(arr);
System.out.println("众数："+modalNums);
float[] arr2 = {0.1f, 1.1f, 2.1f, 3.1f, 4.1f, 5.1f, 6.1f, 7.1f, 8.1f, 9.1f, 10.1f, 1.1f, 1.1f, 2.1f, 2.1f, 3.1f, 4.1f, 5.1f};
ListmodalNums2 = getModalNums(arr2);
System.out.println("众数："+modalNums2);
}
/**
* 方差s^2=[(x1-x)^2 +...(xn-x)^2]/n
* @param x
* @return
*/
public static double getVariance(double[] x) {
int m = x.length;
double sum = 0;
for (int i = 0; i < m; i++) {// 求和
sum += x[i];
}
double dAve = sum / m;// 求平均值
double dVar = 0;
for (int i = 0; i < m; i++) {// 求方差
dVar += (x[i] - dAve) * (x[i] - dAve);
}
return dVar / m;
}
/**
* 标准差σ=sqrt(s^2)
* @param x
* @return
*/
public static double getStandardDiviation(double[] x) {
int m = x.length;
double sum = 0;
for (int i = 0; i < m; i++) {// 求和
sum += x[i];
}
double dAve = sum / m;// 求平均值
double dVar = 0;
for (int i = 0; i < m; i++) {// 求方差
dVar += (x[i] - dAve) * (x[i] - dAve);
}
return Math.sqrt(dVar / m);
}
/**
* 中位数(int)
* @param nums: A list of integers.
* @return: An integer denotes the middle number of the array.
*/
public static int median(int []nums){
if(nums.length==0)
return 0;
int start=0;
int end=nums.length-1;
int index=partition(nums, start, end);
if(nums.length%2==0){
while(index!=nums.length/2-1){
if(index>nums.length/2-1){
index=partition(nums, start, index-1);
}else{
index=partition(nums, index+1, end);
}
}
}else{
while(index!=nums.length/2){
if(index>nums.length/2){
index=partition(nums, start, index-1);
}else{
index=partition(nums, index+1, end);
}
}
}
return nums[index];
}
private static int partition(int nums[], int start, int end){
int left=start;
int right=end;
int pivot=nums[left];
while(left=pivot){
right--;
}
if(leftnums.length/2-1){
index=partition(nums, start, index-1);
}else{
index=partition(nums, index+1, end);
}
}
}else{
while(index!=nums.length/2){
if(index>nums.length/2){
index=partition(nums, start, index-1);
}else{
index=partition(nums, index+1, end);
}
}
}
return nums[index];
}
private static int partition(float nums[], int start, int end){
int left=start;
int right=end;
float pivot=nums[left];
while(left=pivot){
right--;
}
if(leftgetModalNums(int[] arr) {
int n = arr.length;
if (n == 0) {
return new ArrayList();
}
if (n == 1) {
return Arrays.asList(arr[0]);
}
MapfreqMap = new HashMap<>();
for (int i = 0; i < n; i++) { // 统计数组中每个数出现的频率
Integer v = freqMap.get(arr[i]);
// v == null 说明 freqMap 中还没有这个 arr[i] 这个键
freqMap.put(arr[i], v == null ? 1 : v + 1);
}
// 将 freqMap 中所有的键值对(键为数，值为数出现的频率)放入一个 ArrayList
List> entries = new ArrayList<>(freqMap.entrySet());
// 对 entries 按出现频率从大到小排序
Collections.sort(entries, new Comparator>() {
@Override
public int compare(Map.Entrye1, Map.Entrye2) {
return e2.getValue() - e1.getValue();
}
});
ListmodalNums = new ArrayList<>();
modalNums.add(entries.get(0).getKey()); // 排序后第一个 entry 的键肯定是一个众数
int size = entries.size();
for (int i = 1; i < size; i++) {
// 如果之后的 entry 与第一个 entry 的 value 相等，那么这个 entry 的键也是众数
if (entries.get(i).getValue().equals(entries.get(0).getValue())) {
modalNums.add(entries.get(i).getKey());
} else {
break;
}
}
return modalNums;
}
/**
* 众数(float)
* 众数:在一个数组中出现次数最多的数
* 如果存在多个众数，则一起返回
* @param arr
* @return
*/
public static ListgetModalNums(float[] arr) {
int n = arr.length;
if (n == 0) {
return new ArrayList();
}
if (n == 1) {
return Arrays.asList(arr[0]);
}
MapfreqMap = new HashMap<>();
for (int i = 0; i < n; i++) { // 统计数组中每个数出现的频率
Integer v = freqMap.get(arr[i]);
// v == null 说明 freqMap 中还没有这个 arr[i] 这个键
freqMap.put(arr[i], v == null ? 1 : v + 1);
}
// 将 freqMap 中所有的键值对(键为数，值为数出现的频率)放入一个 ArrayList
List> entries = new ArrayList<>(freqMap.entrySet());
// 对 entries 按出现频率从大到小排序
Collections.sort(entries, new Comparator>() {
@Override
public int compare(Map.Entrye1, Map.Entrye2) {
return e2.getValue() - e1.getValue();
}
});
ListmodalNums = new ArrayList<>();
modalNums.add(entries.get(0).getKey()); // 排序后第一个 entry 的键肯定是一个众数
int size = entries.size();
for (int i = 1; i < size; i++) {
// 如果之后的 entry 与第一个 entry 的 value 相等，那么这个 entry 的键也是众数
if (entries.get(i).getValue().equals(entries.get(0).getValue())) {
modalNums.add(entries.get(i).getKey());
} else {
break;
}
}
return modalNums;
}
}
以上这篇java 计算中位数的实现方法就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持脚本之家。