JAVA源码走读（二）二分查找与Arrays类

        int[] array = new int[5];
        //填充数组
        Arrays.fill(array, 5);
        System.out.println("填充数组：Arrays.fill(array, 5)：");
        test.output(array);
         
        //将数组的第2和第3个元素赋值为8
        Arrays.fill(array, 2, 4, 8);
        System.out.println("将数组的第2和第3个元素赋值为8：Arrays.fill(array, 2, 4, 8)：");
        test.output(array);
         
        int[] array1 = {7,8,3,2,12,6,3,5,4};
        //对数组的第2个到第6个进行排序进行排序
        Arrays.sort(array1,2,7);
        System.out.println("对数组的第2个到第6个元素进行排序进行排序：Arrays.sort(array,2,7)：");
        test.output(array1);
         
        //对整个数组进行排序
        Arrays.sort(array1);
        System.out.println("对整个数组进行排序：Arrays.sort(array1)：");
        test.output(array1);
         
        //比较数组元素是否相等
        System.out.println("比较数组元素是否相等:Arrays.equals(array, array1):"+"\n"+Arrays.equals(array, array1));
        int[] array2 = array1.clone();
        System.out.println("克隆后数组元素是否相等:Arrays.equals(array1, array2):"+"\n"+Arrays.equals(array1, array2));
         
        //使用二分搜索算法查找指定元素所在的下标（必须是排序好的，否则结果不正确）
        Arrays.sort(array1);
        System.out.println("元素3在array1中的位置：Arrays.binarySearch(array1, 3)："+"\n"+Arrays.binarySearch(array1, 3));
        //如果不存在就返回负数
        System.out.println("元素9在array1中的位置：Arrays.binarySearch(array1, 9)："+"\n"+Arrays.binarySearch(array1, 9));


        int aaa[] = {5,4,7,3,8,1};
        sort(aaa,0,aaa.length - 1);
        for(int i = 0 ;i<aaa.length;i++){
            System.out.println(aaa[i]);
        }

import java.util.Arrays;

public class test {
    
    private static final int QUICKSORT_THRESHOLD = 286;

    private static final int MAX_RUN_COUNT = 67;

    private static final int MAX_RUN_LENGTH = 33;

    private static final int INSERTION_SORT_THRESHOLD = 47;

    public static void main(String[] args){
        int aaa[] = {5,4,7,3,8,1};
        sort(aaa,0,aaa.length - 1);
        for(int i = 0 ;i<aaa.length;i++){
            System.out.println(aaa[i]);
        }
    }
    
      public static void sort(int[] a, int left, int right) {
            // Use Quicksort on small arrays
            if (right - left < QUICKSORT_THRESHOLD) {
                sort(a, left, right, true);
                return;
            }

            /*
             * Index run[i] is the start of i-th run
             * (ascending or descending sequence).
             */
            int[] run = new int[MAX_RUN_COUNT + 1];
            int count = 0; run[0] = left;

            // Check if the array is nearly sorted
            for (int k = left; k < right; run[count] = k) {
                if (a[k] < a[k + 1]) { // ascending
                    while (++k <= right && a[k - 1] <= a[k]);
                } else if (a[k] > a[k + 1]) { // descending
                    while (++k <= right && a[k - 1] >= a[k]);
                    for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                        int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                    }
                } else { // equal
                    for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                        if (--m == 0) {
                            sort(a, left, right, true);
                            return;
                        }
                    }
                }

                /*
                 * The array is not highly structured,
                 * use Quicksort instead of merge sort.
                 */
                if (++count == MAX_RUN_COUNT) {
                    sort(a, left, right, true);
                    return;
                }
            }

            // Check special cases
            if (run[count] == right++) { // The last run contains one element
                run[++count] = right;
            } else if (count == 1) { // The array is already sorted
                return;
            }

            /*
             * Create temporary array, which is used for merging.
             * Implementation note: variable "right" is increased by 1.
             */
            int[] b; byte odd = 0;
            for (int n = 1; (n <<= 1) < count; odd ^= 1);

            if (odd == 0) {
                b = a; a = new int[b.length];
                for (int i = left - 1; ++i < right; a[i] = b[i]);
            } else {
                b = new int[a.length];
            }

            // Merging
            for (int last; count > 1; count = last) {
                for (int k = (last = 0) + 2; k <= count; k += 2) {
                    int hi = run[k], mi = run[k - 1];
                    for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                        if (q >= hi || p < mi && a[p] <= a[q]) {
                            b[i] = a[p++];
                        } else {
                            b[i] = a[q++];
                        }
                    }
                    run[++last] = hi;
                }
                if ((count & 1) != 0) {
                    for (int i = right, lo = run[count - 1]; --i >= lo;
                        b[i] = a[i]
                    );
                    run[++last] = right;
                }
                int[] t = a; a = b; b = t;
            }
        }
      
      /**
         * Sorts the specified range of the array by Dual-Pivot Quicksort.
         *
         * @param a the array to be sorted
         * @param left the index of the first element, inclusive, to be sorted
         * @param right the index of the last element, inclusive, to be sorted
         * @param leftmost indicates if this part is the leftmost in the range
         */
        private static void sort(int[] a, int left, int right, boolean leftmost) {
            int length = right - left + 1;

            // 数组后一个值与前一个值进行循环比较，通过j--进行循环替换，例如：初始值为 5 4 7 3 8 1 ， 4 5 7 3 8 1  ， 4 5 3 7 8 1 ， 4 3 5 7 8 1
            if (length < INSERTION_SORT_THRESHOLD) {
                if (leftmost) {
                    /*
                     * Traditional (without sentinel) insertion sort,
                     * optimized for server VM, is used in case of
                     * the leftmost part.
                     */ 插入排序
　　

                    for (int i = left, j = i; i < right; j = ++i) {
                        int ai = a[i + 1];
                        while (ai < a[j]) {
                            a[j + 1] = a[j];
                            if (j-- == left) {
                                break;
                            }
                        }
                        a[j + 1] = ai;
                    }
                } else {
                    /*
                     * Skip the longest ascending sequence.
                     */
                    do {
                        if (left >= right) {
                            return;
                        }
                    } while (a[++left] >= a[left - 1]);

                    /*
                     * Every element from adjoining part plays the role
                     * of sentinel, therefore this allows us to avoid the
                     * left range check on each iteration. Moreover, we use
                     * the more optimized algorithm, so called pair insertion
                     * sort, which is faster (in the context of Quicksort)
                     * than traditional implementation of insertion sort.
                     */
                    for (int k = left; ++left <= right; k = ++left) {
                        int a1 = a[k], a2 = a[left];

                        if (a1 < a2) {
                            a2 = a1; a1 = a[left];
                        }
                        while (a1 < a[--k]) {
                            a[k + 2] = a[k];
                        }
                        a[++k + 1] = a1;

                        while (a2 < a[--k]) {
                            a[k + 1] = a[k];
                        }
                        a[k + 1] = a2;
                    }
                    int last = a[right];

                    while (last < a[--right]) {
                        a[right + 1] = a[right];
                    }
                    a[right + 1] = last;
                }
                return;
            }

            // Inexpensive approximation of length / 7
            int seventh = (length >> 3) + (length >> 6) + 1;

            /*
             * Sort five evenly spaced elements around (and including) the
             * center element in the range. These elements will be used for
             * pivot selection as described below. The choice for spacing
             * these elements was empirically determined to work well on
             * a wide variety of inputs.
             */
            int e3 = (left + right) >>> 1; // The midpoint
            int e2 = e3 - seventh;
            int e1 = e2 - seventh;
            int e4 = e3 + seventh;
            int e5 = e4 + seventh;

            // Sort these elements using insertion sort
            if (a[e2] < a[e1]) { int t = a[e2]; a[e2] = a[e1]; a[e1] = t; }

            if (a[e3] < a[e2]) { int t = a[e3]; a[e3] = a[e2]; a[e2] = t;
                if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
            }
            if (a[e4] < a[e3]) { int t = a[e4]; a[e4] = a[e3]; a[e3] = t;
                if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
                    if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
                }
            }
            if (a[e5] < a[e4]) { int t = a[e5]; a[e5] = a[e4]; a[e4] = t;
                if (t < a[e3]) { a[e4] = a[e3]; a[e3] = t;
                    if (t < a[e2]) { a[e3] = a[e2]; a[e2] = t;
                        if (t < a[e1]) { a[e2] = a[e1]; a[e1] = t; }
                    }
                }
            }

            // Pointers
            int less  = left;  // The index of the first element of center part
            int great = right; // The index before the first element of right part

            if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) {
                /*
                 * Use the second and fourth of the five sorted elements as pivots.
                 * These values are inexpensive approximations of the first and
                 * second terciles of the array. Note that pivot1 <= pivot2.
                 */
                int pivot1 = a[e2];
                int pivot2 = a[e4];

                /*
                 * The first and the last elements to be sorted are moved to the
                 * locations formerly occupied by the pivots. When partitioning
                 * is complete, the pivots are swapped back into their final
                 * positions, and excluded from subsequent sorting.
                 */
                a[e2] = a[left];
                a[e4] = a[right];

                /*
                 * Skip elements, which are less or greater than pivot values.
                 */
                while (a[++less] < pivot1);
                while (a[--great] > pivot2);

                /*
                 * Partitioning:
                 *
                 *   left part           center part                   right part
                 * +--------------------------------------------------------------+
                 * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
                 * +--------------------------------------------------------------+
                 *               ^                          ^       ^
                 *               |                          |       |
                 *              less                        k     great
                 *
                 * Invariants:
                 *
                 *              all in (left, less)   < pivot1
                 *    pivot1 <= all in [less, k)     <= pivot2
                 *              all in (great, right) > pivot2
                 *
                 * Pointer k is the first index of ?-part.
                 */
                outer:
                for (int k = less - 1; ++k <= great; ) {
                    int ak = a[k];
                    if (ak < pivot1) { // Move a[k] to left part
                        a[k] = a[less];
                        /*
                         * Here and below we use "a[i] = b; i++;" instead
                         * of "a[i++] = b;" due to performance issue.
                         */
                        a[less] = ak;
                        ++less;
                    } else if (ak > pivot2) { // Move a[k] to right part
                        while (a[great] > pivot2) {
                            if (great-- == k) {
                                break outer;
                            }
                        }
                        if (a[great] < pivot1) { // a[great] <= pivot2
                            a[k] = a[less];
                            a[less] = a[great];
                            ++less;
                        } else { // pivot1 <= a[great] <= pivot2
                            a[k] = a[great];
                        }
                        /*
                         * Here and below we use "a[i] = b; i--;" instead
                         * of "a[i--] = b;" due to performance issue.
                         */
                        a[great] = ak;
                        --great;
                    }
                }

                // Swap pivots into their final positions
                a[left]  = a[less  - 1]; a[less  - 1] = pivot1;
                a[right] = a[great + 1]; a[great + 1] = pivot2;

                // Sort left and right parts recursively, excluding known pivots
                sort(a, left, less - 2, leftmost);
                sort(a, great + 2, right, false);

                /*
                 * If center part is too large (comprises > 4/7 of the array),
                 * swap internal pivot values to ends.
                 */
                if (less < e1 && e5 < great) {
                    /*
                     * Skip elements, which are equal to pivot values.
                     */
                    while (a[less] == pivot1) {
                        ++less;
                    }

                    while (a[great] == pivot2) {
                        --great;
                    }

                    /*
                     * Partitioning:
                     *
                     *   left part         center part                  right part
                     * +----------------------------------------------------------+
                     * | == pivot1 |  pivot1 < && < pivot2  |    ?    | == pivot2 |
                     * +----------------------------------------------------------+
                     *              ^                        ^       ^
                     *              |                        |       |
                     *             less                      k     great
                     *
                     * Invariants:
                     *
                     *              all in (*,  less) == pivot1
                     *     pivot1 < all in [less,  k)  < pivot2
                     *              all in (great, *) == pivot2
                     *
                     * Pointer k is the first index of ?-part.
                     */
                    outer:
                    for (int k = less - 1; ++k <= great; ) {
                        int ak = a[k];
                        if (ak == pivot1) { // Move a[k] to left part
                            a[k] = a[less];
                            a[less] = ak;
                            ++less;
                        } else if (ak == pivot2) { // Move a[k] to right part
                            while (a[great] == pivot2) {
                                if (great-- == k) {
                                    break outer;
                                }
                            }
                            if (a[great] == pivot1) { // a[great] < pivot2
                                a[k] = a[less];
                                /*
                                 * Even though a[great] equals to pivot1, the
                                 * assignment a[less] = pivot1 may be incorrect,
                                 * if a[great] and pivot1 are floating-point zeros
                                 * of different signs. Therefore in float and
                                 * double sorting methods we have to use more
                                 * accurate assignment a[less] = a[great].
                                 */
                                a[less] = pivot1;
                                ++less;
                            } else { // pivot1 < a[great] < pivot2
                                a[k] = a[great];
                            }
                            a[great] = ak;
                            --great;
                        }
                    }
                }

                // Sort center part recursively
                sort(a, less, great, false);

            } else { // Partitioning with one pivot
                /*
                 * Use the third of the five sorted elements as pivot.
                 * This value is inexpensive approximation of the median.
                 */
                int pivot = a[e3];

                /*
                 * Partitioning degenerates to the traditional 3-way
                 * (or "Dutch National Flag") schema:
                 *
                 *   left part    center part              right part
                 * +-------------------------------------------------+
                 * |  < pivot  |   == pivot   |     ?    |  > pivot  |
                 * +-------------------------------------------------+
                 *              ^              ^        ^
                 *              |              |        |
                 *             less            k      great
                 *
                 * Invariants:
                 *
                 *   all in (left, less)   < pivot
                 *   all in [less, k)     == pivot
                 *   all in (great, right) > pivot
                 *
                 * Pointer k is the first index of ?-part.
                 */
                for (int k = less; k <= great; ++k) {
                    if (a[k] == pivot) {
                        continue;
                    }
                    int ak = a[k];
                    if (ak < pivot) { // Move a[k] to left part
                        a[k] = a[less];
                        a[less] = ak;
                        ++less;
                    } else { // a[k] > pivot - Move a[k] to right part
                        while (a[great] > pivot) {
                            --great;
                        }
                        if (a[great] < pivot) { // a[great] <= pivot
                            a[k] = a[less];
                            a[less] = a[great];
                            ++less;
                        } else { // a[great] == pivot
                            /*
                             * Even though a[great] equals to pivot, the
                             * assignment a[k] = pivot may be incorrect,
                             * if a[great] and pivot are floating-point
                             * zeros of different signs. Therefore in float
                             * and double sorting methods we have to use
                             * more accurate assignment a[k] = a[great].
                             */
                            a[k] = pivot;
                        }
                        a[great] = ak;
                        --great;
                    }
                }

                /*
                 * Sort left and right parts recursively.
                 * All elements from center part are equal
                 * and, therefore, already sorted.
                 */
                sort(a, left, less - 1, leftmost);
                sort(a, great + 1, right, false);
            }
        }
}