如何计算数组的中位数？

Question

我试图计算由TextField接收的输入填充的数组的总数、平均值和中位数。我已经算出了总数和平均数，但中位数无法计算出来。我认为在我可以这样做之前需要对数组进行排序，但我不确定如何这样做。是这个问题，还是还有一个我没有找到的？下面是我的代码：

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);



    }
}

Answer 1

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

这个概念是要找到第N个最小值，选择一个“pivot”值。（具体如何选择并不重要；如果你知道数据是完全随机的，你可以选择列表上的第一个项目。）

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

• 值小于透视的值。
• 一个值等于数据透视的值。
• 和一个值大于透视的值。

然后有三种情况：

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

搞定了。

如果您不确定数据是完全随机的，那么您就需要更复杂地选择数据透视。取列表中第一个值、列表中最后一个值以及两者中间值的中值非常有效。

如果您选择的支点非常不走运，并且总是选择最小或最高的值作为支点，这需要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

Answer 2

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];