数组小知识

  1. 数组的优缺点和创建
    1. 数组的优点:
    2. 数组的创建
  2. Arrays包:
    1. Arraycopy
    2. sort方法
      1. legacyMergeSort
      2. ComparableTimSort.sort
      3. equals

数组的优缺点和创建

数组的优点:

  • 在java中,一切都是对象,数组也不例外,new一个数组时会在堆上创建一块内存空间,数组的优点就在于其地址是连续的,因此随机读取的时候特别快。

  • 数组可以持有基本数据类型,在没有泛型之前容器是不能存放基本数据类型,现在有了泛型和自动包装,容器也可以持有了。

缺点:

  • 数组的长度是固定的,在new数组的时候就得给定并且不能修改,如果扩容的得需要借助System.arrayCopy()来完成。

  • 不能实例化具有参数类型的数组,比如:Fruit<Banana> banana=new Fruit<Banana>[10]; //Illigal因为擦除会移除参数类型信息,而数组必须知道他们所持有的确切类型,已强制保证安全。

数组的创建

数组分为一维数组和多维数组,java中的多维数组归根到底还是由一维数组组成的,先看下一维数组的创建:

  • 基本数据类型的数组:

    1. int[] array=new int[3] ; 这种情况下数组中的值默认为0,对于char为’’, boolean全为false.

    2. 创建时直接赋值: int[] array={1,2,3};

    3. 如果一个方法需要返回一个int数组时,return new int[]{1,2,3};

  • 对象类型的数组:

    1. 与基本类型不同的一点是数组里存放的是其他对象引用 。 Fruit[] f=new Fruit[4];

      这时数组里面存放的是4个指向Fruit对象的引用.默认全部为null

  • 多维数组的创建:

    有一维数组类似:

    1. int[][] a=new int[2][3];

    2. int[][] a={(1,2,3),(3,4,5)}; //要将()改为{},我这边的模版会报错。

    不同点是构成多维数组的每一个向量都可以具有任意的长度。初始化数组时只需给定数组的长度给定即可,比如 int[][] a=new int[2][];

    通过多维数组在堆中的存储情况即可得知原因:

    img

    其实就是相当于初始话最外层的一维数组,一维数组内的数据又指向其他数组,因此每一维的数组长度可以是任意的,初始化时也可只初始化数组的第一个参数。

Arrays包:

Arrays包位于java.util里面,常用的有sort,binarySearch,quals,fill等静态方法,在介绍这些方法前,先看一个用途非常广泛的System.arraycopy()方法:

Arraycopy

public static native void arraycopy(Object src,  int  srcPos,Object dest,
 int destPos,int length);

src: 源数组

srcPos: 从源数组的哪个位置开始复制

dest: 目标数组

destPos:从目标数组的哪里复制

length: 复制多长。

可以看到src和dest都是Object类型,因此基本类型和对象数组都可以搞定。

int[] src={1,2,3,4};
int[] dest=new int[4];
System.arraycopy(src,0,dest,1,3);
System.out.println(Arrays.toString(dest));
-----------------------------------------------
[0, 1, 2, 3]
Fruit[] fruit={new Fruit(1),new Fruit(2),new Fruit(3),new Fruit(4)};
Fruit[] dest=new Fruit[4];
System.arraycopy(fruit,0,dest,1,3);
System.out.println("原数组"+Arrays.toString(fruit));
System.out.println("拷贝后的数组"+Arrays.toString(dest));
-----------------------------------------------------------------
原数组[Fruit@45ee12a7, Fruit@330bedb4, Fruit@2503dbd3, Fruit@4b67cf4d]
拷贝后的数组[null, Fruit@45ee12a7, Fruit@330bedb4, Fruit@2503dbd3]

可以看到拷贝后只是复制了原对象的引用,只是一个浅拷贝。

另外该方法不支持自动包装,因此复制和被复制的数组类型必须一样。

int[] src={1,2,3,4};
Integer[] dest=new Integer[4];
System.arraycopy(src,0,dest,1,3);
------------------------------------------------------------
Exception in thread "main" java.lang.ArrayStoreException
    at java.lang.System.arraycopy(Native Method)
    at StringTest.main(StringTest.java:27)
直接抛异常。

sort方法

sort方法中定义了所有基本数据类型sort的方法,对任意的对象数组也同样支持,只要该对象实现了Comparable接口或者具有Comparator。

public static void sort(Object[] a, int fromIndex, int toIndex) {
        //检查是否越界
        rangeCheck(a.length, fromIndex, toIndex);
        //用户请求使用归并排序时
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, fromIndex, toIndex);
        else
            //调用TimSort
            ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
    }

看下legacyMergeSort的源码,注释上写着未来要remove掉,心酸。首先copy一份从fromIndex到toIndex的数据,然后调用mergeSort进行排序。底层调用的是arraycopy浅拷贝一份,因此aux中的对象都是指向数组a中对象的引用。

legacyMergeSort

/** To be removed in a future release. */
    private static void legacyMergeSort(Object[] a,
                                        int fromIndex, int toIndex) {
        Object[] aux = copyOfRange(a, fromIndex, toIndex);
        mergeSort(aux, a, fromIndex, toIndex, -fromIndex);
    }

src是源数组,dest是目标数组,low是起始,high是终止位置。off是在src数组中对应low和high的偏移量

 private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;

        // Insertion sort on smallest arrays
        //INSERTIONSORT_THRESHOLD等于7
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

        // Recursively sort halves of dest into src
        int destLow  = low;
        int destHigh = high;
        low  += off;
        high += off;
        int mid = (low + high) >>> 1;
        //交换源数组和目标数组
        mergeSort(dest, src, low, mid, -off);
        mergeSort(dest, src, mid, high, -off);

        // If list is already sorted, just copy from src to dest.  This is an
        // optimization that results in faster sorts for nearly ordered lists.
        if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

        // Merge sorted halves (now in src) into dest
        for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }
    }

int length= high-low获取数组的长度。

private static final int INSERTIONSORT_THRESHOLD = 7;

如果数组的长度小于7时直接使用插入排序,如果值比前面的小,就交换。复杂度是O(n^2).

if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }

拆分数组,分成low,mid mid,high两个,知道数组的长度小于7进行插入排序,然后再进行合并

int destLow  = low;
int destHigh = high;
low  += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);

如果已经排好序了,直接复制。

if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
            System.arraycopy(src, low, dest, destLow, length);
            return;
        }

合并排好序的子数组。

for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
            if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
                dest[i] = src[p++];
            else
                dest[i] = src[q++];
        }

很明显这是一个归并排序,首先因为原来的归并排序需要多次归并,如果每次都创建一个数组明显不太靠谱,因此辅助数组是一个全局数组,归并的时候需要将源数组的元素复制到辅助数组中。

对于上面的问题,sort方法中归并排序是这样解决的,对于较小的数组使用插入排序,判断src[mid-1]和src[mid]的大小,如果前面的最大比后面的小就说明已经排好了。 对于复制数组造成排序速度的问题可以通过交换源数组和辅助数组来解决。

ComparableTimSort.sort

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
        assert a != null && lo >= 0 && lo <= hi && hi <= a.length;

        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a "mini-TimSort" with no merges
        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi);
            binarySort(a, lo, hi, lo + initRunLen);
            return;
        }

        /**
         * March over the array once, left to right, finding natural runs,
         * extending short natural runs to minRun elements, and merging runs
         * to maintain stack invariant.
         */
        ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
        int minRun = minRunLength(nRemaining);
        do {
            // Identify next run
            int runLen = countRunAndMakeAscending(a, lo, hi);

            // If run is short, extend to min(minRun, nRemaining)
            if (runLen < minRun) {
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen);
                runLen = force;
            }

            // Push run onto pending-run stack, and maybe merge
            ts.pushRun(lo, runLen);
            ts.mergeCollapse();

            // Advance to find next run
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);

        // Merge all remaining runs to complete sort
        assert lo == hi;
        ts.mergeForceCollapse();
        assert ts.stackSize == 1;
    }

一步步的来:

当数组的长度为0获1时肯定是排好序的。

int nRemaining  = hi - lo;
if (nRemaining < 2)
   return;

当数组的长度小于32时,先调用countRunAndMakeAscending找到一组连续升序或降序,然后再调用binarySort进行排序。

if (nRemaining < MIN_MERGE) {
     int initRunLen = countRunAndMakeAscending(a, lo, hi);
     binarySort(a, lo, hi, lo + initRunLen);
     return;
}

首先判断a[lo+1]和a[lo]的大小关系,如果大于的话则是递增,小于是递减,递减的时候就while循环依次判断后面的,是就runHi++,因为sort默认是升序的,因此reverse一下,递增的话则同理,最后返回的是调增或递减序列的长度。

private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
        assert lo < hi;
        int runHi = lo + 1;
        if (runHi == hi)
            return 1;

        // Find end of run, and reverse range if descending
        if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
            while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
                runHi++;
            reverseRange(a, lo, runHi);
        } else {                              // Ascending
            while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
                runHi++;
        }

        return runHi - lo;
    }

binarySort方法:前面的countRunAndMakeAscending方法算出来了已经递减的字数组的长度,从start开始通过二分查找与前面排好序的数组比较并返回a[start]在前面数组中对应的位置left。然后得到a中要move的数据的总数。调用arraycopy后移动数组最后将pirot放到a[left]中。

private static void binarySort(Object[] a, int lo, int hi, int start) {
        assert lo <= start && start <= hi;
        if (start == lo)
            start++;
        for ( ; start < hi; start++) {
            Comparable pivot = (Comparable) a[start];

            int left = lo;
            int right = start;
            assert left <= right;
            //二分查找pivot的位置,查不到的话也是返回left
            while (left < right) {
                int mid = (left + right) >>> 1;
                if (pivot.compareTo(a[mid]) < 0)
                    right = mid;
                else
                    left = mid + 1;
            }
            assert left == right;

            int n = start - left;  // The number of elements to move
            //移动数组
            switch (n) {
                //因为没有case2 break,所以先执行case2再执行case1正好交换两次。
                case 2:  a[left + 2] = a[left + 1];
                case 1:  a[left + 1] = a[left];
                         break;
                default: System.arraycopy(a, left, a, left + 1, n);
            }
            //将pivot放到对应的位置。
            a[left] = pivot;
        }
    }

看下如果对没有实现Comparable接口的对象数组强行排序会发生什么?

class Fruit{
    private int val;

    public int getVal(){
        return this.val;
    }
    Fruit(int val){
        this.val=val;
    }
}
public class Test{
  public static void main(String[] args){
     Fruit[] fruit={new Fruit(1),new Fruit(2),new Fruit(3),new Fruit(4)};
     Arrays.sort(fruit);
   }
}
----------------------------------------------------------------------------
Exception in thread "main" java.lang.ClassCastException: Fruit cannot be cast to java.lang.Comparable
    at java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
    at java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
    at java.util.Arrays.sort(Arrays.java:1246)

假设别人给了一个没有实现Comparotor接口的类,或者不喜欢别人的实现方式,sort方法提供了另一个参数,sort(T[] a, Comparator<? super T> c) 只要传一个实现Comparator接口的类即可。

实现原理和上面的基本一样,就是把上面的比较方法compareTo换成compare方法即可。Arrays.sort(Fruit,Collections.reverseOrder());

对于多维数组的比较,就可以自定义一个Comparator来自行选择某一列进行比较。

equals

数组是连续存放在内存中的,因此如果没有重写equals方法,两个不同的数组即使数组里的数据是一样的也会false。

int[] src={1,2,3,4};
int[] des={1,2,3,4};
System.out.println(src==des);
-----------------------------------------------------------------------------------
false

equals方法:如果传入的是基本类型数组就是比较按照基本类型的比较方法,如果传入的是对象数组,则按照对象自己的equals方法比较来判断数组的所有元素是否相等。


本网站发布的一切文章仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。如有侵权请联系邮箱:1194325527@qq.com处理

目录
×

给作者杯卡布奇诺

github