集册 Java实例教程 计算数组的中值。

计算数组的中值。

欢马劈雪     最近更新时间:2020-01-02 10:19:05

429
提示:您可在线编辑运行本教程的实例 - 运行实例,去试试!
计算数组的中位数。


//package com.nowjava;/**来 自 时   代    Java - nowjava.com**/


public class Main {

    public static void main(String[] argv) throws Exception {

        double[] v = new double[] { 34.45, 35.45, 36.67, 37.78, 37.0000,

                37.1234, 67.2344, 68.34534, 69.87700 };

        System.out.println(median(v));

    }


    /**

     * Computes the median of an array.

     * If the array contains an even number of elements,

     * then the mean of the lower and upper medians is returned.

     */

    public static double median(double[] v) {

        if (v.length == 3) {

            return median3(copy(v));

        } else if (v.length == 5) {

            return median5(copy(v));

        } else if (v.length == 7) {

            return median7(copy(v));

        } else if (v.length % 2 == 1) { // odd

            return quickSelect(copy(v), false);

        } else { // even// from 时 代 J a v a - N o w J a v a . c o m

            double[] tmp = copy(v);

            double lowerMedian = quickSelect(tmp, false);

            double upperMedian = quickSelect(tmp, true);

            return (lowerMedian + upperMedian) / 2.0;

        }

    }


    /**

     * Computes the median of an array.

     * If the array contains an even number of elements,

     * the lower median is returned.

     */

    public static int median(int[] v) {

        if (v.length == 3) {

            return median3(copy(v));

        } else if (v.length == 5) {

            return median5(copy(v));

        } else if (v.length == 7) {

            return median7(copy(v));

        } else {

            return quickSelect(copy(v));

        }

    }


    private static double median3(double[] v) {

        sortInPlace(v, 0, 1);

        sortInPlace(v, 1, 2);

        sortInPlace(v, 0, 1);

        return v[1];

    }


    private static int median3(int[] v) {

        sortInPlace(v, 0, 1);

        sortInPlace(v, 1, 2);

        sortInPlace(v, 0, 1);

        return v[1];

    }


    /**

     * Returns a copy of the array.

     */

    //a call to array.clone() may also work although this is a primitive type. I haven't checked

    //it even may be faster

    public static int[] copy(int[] array) {

        int[] result;

        result = new int[array.length];

        System.arraycopy(array, 0, result, 0, array.length);

        return result;

    }


    /**

     * Returns a copy of the array.

     */

    //a call to array.clone() may also work although this is a primitive type. I haven't checked

    //it even may be faster

    public static long[] copy(long[] array) {

        long[] result;

        result = new long[array.length];

        System.arraycopy(array, 0, result, 0, array.length);

        return result;

    }


    /**

     * Returns a copy of the array.

     */

    //a call to array.clone() may also work although this is a primitive type. I haven't checked

    //it even may be faster

    public static float[] copy(float[] array) {

        float[] result;

        result = new float[array.length];

        System.arraycopy(array, 0, result, 0, array.length);

        return result;

    }


    /**

     * Returns a copy of the array.

     */

    //a call to array.clone() may also work although this is a primitive type. I haven't checked

    //it even may be faster

    public static double[] copy(double[] array) {

        double[] result;

        result = new double[array.length];

        System.arraycopy(array, 0, result, 0, array.length);

        return result;

    }


    /**

     * Returns a copy of the array.

     */

    public static double[][] copy(double[][] v) {

        double[][] ans = new double[v.length][];

        for (int k = 0; k < v.length; k++)

            ans[k] = copy(v[k]);

        return (ans);

    }


    /**

     * Returns a copy of the array.

     */

    public static int[][] copy(int[][] v) {

        int[][] ans = new int[v.length][];

        for (int k = 0; k < v.length; k++)

            ans[k] = copy(v[k]);

        return (ans);

    }


    private static double median5(double[] v) {

        sortInPlace(v, 0, 1);

        sortInPlace(v, 3, 4);

        sortInPlace(v, 0, 3);

        sortInPlace(v, 1, 4);

        sortInPlace(v, 1, 2);

        sortInPlace(v, 2, 3);

        sortInPlace(v, 1, 2);

        return v[2];

    }


    private static int median5(int[] v) {

        sortInPlace(v, 0, 1);

        sortInPlace(v, 3, 4);

        sortInPlace(v, 0, 3);

        sortInPlace(v, 1, 4);

        sortInPlace(v, 1, 2);

        sortInPlace(v, 2, 3);

        sortInPlace(v, 1, 2);

        return v[2];

    }


    private static double median7(double[] v) {

        sortInPlace(v, 0, 5);

        sortInPlace(v, 0, 3);

        sortInPlace(v, 1, 6);

        sortInPlace(v, 2, 4);

        sortInPlace(v, 0, 1);

        sortInPlace(v, 3, 5);

        sortInPlace(v, 2, 6);

        sortInPlace(v, 2, 3);

        sortInPlace(v, 3, 6);

        sortInPlace(v, 4, 5);

        sortInPlace(v, 1, 4);

        sortInPlace(v, 1, 3);

        sortInPlace(v, 3, 4);

        return v[3];

    }


    private static int median7(int[] v) {

        sortInPlace(v, 0, 5);

        sortInPlace(v, 0, 3);

        sortInPlace(v, 1, 6);

        sortInPlace(v, 2, 4);

        sortInPlace(v, 0, 1);

        sortInPlace(v, 3, 5);

        sortInPlace(v, 2, 6);

        sortInPlace(v, 2, 3);

        sortInPlace(v, 3, 6);

        sortInPlace(v, 4, 5);

        sortInPlace(v, 1, 4);

        sortInPlace(v, 1, 3);

        sortInPlace(v, 3, 4);

        return v[3];

    }


    private static double quickSelect(double[] v, boolean upperMedian) {

        int low = 0, high = v.length - 1;

        final int median = upperMedian ? high / 2 + 1 : high / 2;

        int middle, ll, hh;


        for (;;) {

            if (high <= low) { /* One element only */

                return v[median];

            }


            if (high == low + 1) { /* Two elements only */

                if (v[low] > v[high])

                    swap(v, low, high);

                return v[median];

            }


            /* Find median of low, middle and high items; swap into position low */

            middle = (low + high) / 2;

            if (v[middle] > v[high])

                swap(v, middle, high);

            if (v[low] > v[high])

                swap(v, low, high);

            if (v[middle] > v[low])

                swap(v, middle, low);


            /* Swap low item (now in position middle) into position (low+1) */

            swap(v, middle, low + 1);


            /* Nibble from each end towards middle, swapping items when stuck */

            ll = low + 1;

            hh = high;

            for (;;) {

                do

                    ll++;

                while (v[low] > v[ll]);

                do

                    hh--;

                while (v[hh] > v[low]);


                if (hh < ll)

                    break;


                swap(v, ll, hh);

            }


            /* Swap middle item (in position low) back into correct position */

            swap(v, low, hh);


            /* Re-set active partition */

            if (hh <= median)

                low = ll;

            if (hh >= median)

                high = hh - 1;

        }

    }


    private static int quickSelect(int[] v) {

        int low = 0, high = v.length - 1;

        final int median = high / 2;

        int middle, ll, hh;


        for (;;) {

            if (high <= low) { /* One element only */

                return v[median];

            }


            if (high == low + 1) { /* Two elements only */

                if (v[low] > v[high])

                    swap(v, low, high);

                return v[median];

            }


            /* Find median of low, middle and high items; swap into position low */

            middle = (low + high) / 2;

            if (v[middle] > v[high])

                swap(v, middle, high);

            if (v[low] > v[high])

                swap(v, low, high);

            if (v[middle] > v[low])

                swap(v, middle, low);


            /* Swap low item (now in position middle) into position (low+1) */

            swap(v, middle, low + 1);


            /* Nibble from each end towards middle, swapping items when stuck */

            ll = low + 1;

            hh = high;

            for (;;) {

                do

                    ll++;

                while (v[low] > v[ll]);

                do

                    hh--;

                while (v[hh] > v[low]);


                if (hh < ll)

                    break;


                swap(v, ll, hh);

            }


            
展开阅读全文