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

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++)
    {
        ...
    }

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