如何计算数组的中位数？

Question

我正在尝试计算由文本字段接收到的输入填充的数组的总数、平均值和中位数。我已经设法计算出总数和平均值，但我无法让中位数起作用。我认为在执行此操作之前需要对数组进行排序，但我不确定如何执行此操作。这是问题所在，还是我没有找到另一个问题？这是我的代码：

 import java.applet.Applet;
import java.awt.Graphics;
import java.awt.*;
import java.awt.event.*;

public class whileloopq extends Applet implements ActionListener
{
    Label label;
    TextField input;
    int num;
    int index;
    int[] numArray = new int[20];
    int sum;
    int total;
    double avg;
    int median;

    public void init ()
    {
        label = new Label("Enter numbers");
        input = new TextField(5);
        add(label);
        add(input);
        input.addActionListener(this);
        index = 0;
    }

    public void actionPerformed (ActionEvent ev)
    {
        int num = Integer.parseInt(input.getText());
        numArray[index] = num;
        index++;
        if (index == 20)
        input.setEnabled(false);
            input.setText("");
        sum = 0;
        for (int i = 0; i < numArray.length; i++)
        {
            sum += numArray[i];
        }
        total = sum;
        avg = total / index;

        median = numArray[numArray.length/2];

        repaint();

    }

    public void paint (Graphics graf)
    {

        graf.drawString("Total   = " + Integer.toString(total), 25, 85);
        graf.drawString("Average = " + Double.toString(avg), 25, 100);
        graf.drawString("Median = " + Integer.toString(median), 25, 115);

    }
}

原文由 Will 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

Java 中的 Arrays 类有一个静态排序函数，您可以使用 Arrays.sort(numArray) 调用它。

 Arrays.sort(numArray);
double median;
if (numArray.length % 2 == 0)
    median = ((double)numArray[numArray.length/2] + (double)numArray[numArray.length/2 - 1])/2;
else
    median = (double) numArray[numArray.length/2];

原文由 lynnyi 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

对数组进行排序是不必要且低效的。 QuickSort ( QuickSelect ) 算法有一个变体，它的平均运行时间为 O(n)；如果你先排序，你就会下降到 O(n log n)。它实际上是在列表中找到第 n 个最小的项目；对于中位数，您只需使用 n = 列表长度的一半。我们称它为 quickNth (list, n)。

这个概念是要找到第 n 个最小的，选择一个“枢轴”值。 （具体如何选择并不重要；如果您知道数据将完全随机，则可以选择列表中的第一项。）

将原始列表拆分为三个较小的列表：

• 一个值小于枢轴的值。
• 一个值等于主元。
• 还有一个值大于枢轴的值。

然后你有三种情况：

1. “较小”列表有 >= n 个项目。在那种情况下，您知道第 n 个最小的在该列表中。返回 quickNth(smaller, n)。
2. 较小的列表有 < n 个项目，但较小列表和相等列表的长度之和有 >= n 个项目。在这种情况下，第 n 个等于“等于”列表中的任何一项；你完成了。
3. n 大于较小列表和相等列表的长度之和。在这种情况下，您基本上可以跳过这两个，并相应地调整 n。返回 quickNth（更大，n - 长度（更小）- 长度（等于））。

完毕。

如果您不确定数据是否完全随机，则需要更仔细地选择基准。取列表中第一个值、列表中最后一个值以及两者之间的中间值的中值效果很好。

如果您对枢轴的选择很不走运，并且总是选择最小或最大值作为枢轴，则这需要 O(n^2) 时间；那很糟。但是，如果您使用合适的算法选择枢轴，那也 不太 可能。

示例代码：

 import java.util.*;

public class Utility {
   /****************
   * @param coll an ArrayList of Comparable objects
   * @return the median of coll
   *****************/

   public static <T extends Number> double median(ArrayList<T> coll, Comparator<T> comp) {
      double result;
      int n = coll.size()/2;

      if (coll.size() % 2 == 0)  // even number of items; find the middle two and average them
         result = (nth(coll, n-1, comp).doubleValue() + nth(coll, n, comp).doubleValue()) / 2.0;
      else                      // odd number of items; return the one in the middle
         result = nth(coll, n, comp).doubleValue();

      return result;
   } // median(coll)



   /*****************
   * @param coll a collection of Comparable objects
   * @param n  the position of the desired object, using the ordering defined on the list elements
   * @return the nth smallest object
   *******************/

   public static <T> T nth(ArrayList<T> coll, int n, Comparator<T> comp) {
      T result, pivot;
      ArrayList<T> underPivot = new ArrayList<>(), overPivot = new ArrayList<>(), equalPivot = new ArrayList<>();

      // choosing a pivot is a whole topic in itself.
      // this implementation uses the simple strategy of grabbing something from the middle of the ArrayList.

      pivot = coll.get(n/2);

      // split coll into 3 lists based on comparison with the pivot

      for (T obj : coll) {
         int order = comp.compare(obj, pivot);

         if (order < 0)        // obj < pivot
            underPivot.add(obj);
         else if (order > 0)   // obj > pivot
            overPivot.add(obj);
         else                  // obj = pivot
            equalPivot.add(obj);
      } // for each obj in coll

      // recurse on the appropriate list

      if (n < underPivot.size())
         result = nth(underPivot, n, comp);
      else if (n < underPivot.size() + equalPivot.size()) // equal to pivot; just return it
         result = pivot;
      else  // everything in underPivot and equalPivot is too small.  Adjust n accordingly in the recursion.
         result = nth(overPivot, n - underPivot.size() - equalPivot.size(), comp);

      return result;
   } // nth(coll, n)



   public static void main (String[] args) {
      Comparator<Integer> comp = Comparator.naturalOrder();
      Random rnd = new Random();

      for (int size = 1; size <= 10; size++) {
         ArrayList<Integer> coll = new ArrayList<>(size);
         for (int i = 0; i < size; i++)
            coll.add(rnd.nextInt(100));

         System.out.println("Median of " + coll.toString() + " is " + median(coll, comp));
      } // for a range of possible input sizes
   } // main(args)
} // Utility

原文由 Bruce Feist 发布，翻译遵循 CC BY-SA 4.0 许可协议