JAVA源码走读(二)二分查找与Arrays类

简介: 给数组赋值:通过fill方法。 对数组排序:通过sort方法,按升序。比较数组:通过equals方法比较数组中元素值是否相等。查找数组元素:通过binarySearch方法能对排序好的数组进行二分查找法操作。

给数组赋值:通过fill方法。

对数组排序:通过sort方法,按升序。
比较数组:通过equals方法比较数组中元素值是否相等。
查找数组元素:通过binarySearch方法能对排序好的数组进行二分查找法操作。

使用如下:

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

 

源码解析:package test;

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

今日太晚,明日再干~

目录
相关文章
|
2天前
|
Java
Java的原子变量类
Java的原子变量类
15 8
|
1天前
|
Java 开发者
在Java多线程编程中,创建线程的方法有两种:继承Thread类和实现Runnable接口
【10月更文挑战第20天】在Java多线程编程中,创建线程的方法有两种:继承Thread类和实现Runnable接口。本文揭示了这两种方式的微妙差异和潜在陷阱,帮助你更好地理解和选择适合项目需求的线程创建方式。
7 3
|
1天前
|
Java
在Java多线程编程中,实现Runnable接口通常优于继承Thread类
【10月更文挑战第20天】在Java多线程编程中,实现Runnable接口通常优于继承Thread类。原因包括:1) Java只支持单继承,实现接口不受此限制;2) Runnable接口便于代码复用和线程池管理;3) 分离任务与线程,提高灵活性。因此,实现Runnable接口是更佳选择。
8 2
|
1天前
|
Java
Java中多线程编程的基本概念和创建线程的两种主要方式:继承Thread类和实现Runnable接口
【10月更文挑战第20天】《JAVA多线程深度解析:线程的创建之路》介绍了Java中多线程编程的基本概念和创建线程的两种主要方式:继承Thread类和实现Runnable接口。文章详细讲解了每种方式的实现方法、优缺点及适用场景,帮助读者更好地理解和掌握多线程编程技术,为复杂任务的高效处理奠定基础。
8 2
|
2天前
|
存储 Java API
详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
【10月更文挑战第19天】深入剖析Java Map:不仅是高效存储键值对的数据结构,更是展现设计艺术的典范。本文从基本概念、设计艺术和使用技巧三个方面,详细解析HashMap、TreeMap、LinkedHashMap等实现类,帮助您更好地理解和应用Java Map。
14 3
|
1天前
|
Java 程序员 测试技术
Java|让 JUnit4 测试类自动注入 logger 和被测 Service
本文介绍如何通过自定义 IDEA 的 JUnit4 Test Class 模板,实现生成测试类时自动注入 logger 和被测 Service。
15 5
|
1天前
|
Java 开发者
Java多线程初学者指南:介绍通过继承Thread类与实现Runnable接口两种方式创建线程的方法及其优缺点
【10月更文挑战第20天】Java多线程初学者指南:介绍通过继承Thread类与实现Runnable接口两种方式创建线程的方法及其优缺点,重点解析为何实现Runnable接口更具灵活性、资源共享及易于管理的优势。
8 1
|
3月前
|
Java 开发者
奇迹时刻!探索 Java 多线程的奇幻之旅:Thread 类和 Runnable 接口的惊人对决
【8月更文挑战第13天】Java的多线程特性能显著提升程序性能与响应性。本文通过示例代码详细解析了两种核心实现方式:Thread类与Runnable接口。Thread类适用于简单场景,直接定义线程行为;Runnable接口则更适合复杂的项目结构,尤其在需要继承其他类时,能保持代码的清晰与模块化。理解两者差异有助于开发者在实际应用中做出合理选择,构建高效稳定的多线程程序。
54 7
|
3月前
|
Oracle 安全 Java
JDK8到JDK28版本升级的新特性问题之在Java 15及以后的版本中,密封类和密封接口是怎么工作的
JDK8到JDK28版本升级的新特性问题之在Java 15及以后的版本中,密封类和密封接口是怎么工作的
|
3月前
|
安全 Java
【Java集合类面试三】、Map接口有哪些实现类?
这篇文章介绍了Java中Map接口的几种常用实现类:HashMap、LinkedHashMap、TreeMap和ConcurrentHashMap,以及它们适用的不同场景和线程安全性。