java - 使用选择排序查找数组的中位数

Question

我正在尝试从 Java 中的未排序数组中查找中位数。首先，我需要使用选择排序技术对数组进行排序，并且我无法使用任何 Java 库方法进行排序(因此没有 Arrays.sort(array))。另外，我也无法对整个数组进行排序。我只能对所需数量的元素进行排序以找到数组的中位数。我想对于偶数数组，它只是元素的一半加一(然后找到最后两个元素的平均值)，而对于奇数数组，它只是元素的一半(最后一个是中位数)。

所以我不确定如何在正确的时间停止选择排序并从部分排序数组的最后一个或两个元素中找到中位数。以下是我到目前为止所拥有的。

import java.util.Arrays;

public class EfficientMedian
{
    public static void median(int[] values)
    {
        int i, j, temp;
        double median;

        //selection sort below
        for (i = 0; i < values.length - 1; i++)
        {
            for (j = i + 1; j < values.length; j++)
            {
                if (values[i] > values[j])
                {
                    temp = values[i];
                    values[i] = values[j];
                    values[j] = temp;
                }
            }
        }
        if (values.length % 2 == 0) //if the array is even
        {
            median = values[values.length/2]; //just a placeholder
        }
        else //if the array is odd
        {
            median = values[values.length/2];
        }
        System.out.println(Arrays.toString(values));
        System.out.println(median);
    }
    public static void main(String[] args)
    {
        int[] array1 = {567, 2, 600, 6, 601}, array2 = {45, 300, 46, 49};
        median(array1);
        median(array2);
    }
}

Answer 1

您的第一个循环选择要排序的元素。如果只需要中位数，则只需对values.length/2元素进行排序即可。所以你应该编辑这个:

for (i = 0; i < values.length - 1; i++)
    {
        ...
    }

至

for (i = 0; i < values.length/2; i++)
    {
        ...
    }

仅供引用，在“数组长度为奇数”的情况下，约定是对中间两个值进行平均。