1：什么是數(shù)組坛梁？
2：Java中數(shù)組的聲明及數(shù)組的遍歷
3：數(shù)組天生的優(yōu)勢——索引
4：動態(tài)數(shù)組
5：封裝自己的數(shù)組類——增加元素
6：封裝自己的數(shù)組類——刪除元素
7：封裝自己的數(shù)組類——修改元素，查詢元素
8：簡單的時間復(fù)雜度分析
9：均攤復(fù)雜度與復(fù)雜度震蕩

1：什么是數(shù)組诅妹？

數(shù)組是我們在學(xué)習(xí)任何一種編程語言最早接觸到的數(shù)據(jù)結(jié)構(gòu)罚勾。它是一種相同數(shù)據(jù)類型的元素存儲的集合毅人；數(shù)組中各個元素的存儲是有先后順序的吭狡，并且它們在內(nèi)存中也會按照這樣的順序連續(xù)存放在一起。

2：Java中數(shù)組的聲明及數(shù)組的遍歷

Java中數(shù)組的聲明

Java語言當(dāng)中丈莺，數(shù)組常規(guī)的聲明方式有三種划煮。

// 第一種
int [] students = new int [50];
// 第二種
int [] scores = new int [3]{99,88,79};
// 第三種
String [] hobby = {"拳擊","健身","跑步"}

無論是哪一種聲明方式，都可以看出數(shù)組的聲明直接或間接地指定了數(shù)組的大小缔俄，只有在聲明數(shù)組時弛秋，告訴計算機(jī)數(shù)組的大小，計算機(jī)才可以在指定的內(nèi)存中為你聲明的數(shù)組開辟一串連續(xù)的空間俐载。我們可以想象一連串小格子一個挨著一個緊密地拼湊在一起,每一個小格子都裝著一個數(shù)據(jù)蟹略，而裝著數(shù)據(jù)的小格子又對應(yīng)計算機(jī)內(nèi)存上的一個地址，每個小格子所對應(yīng)的地址是連續(xù)的......

Java中數(shù)組的遍歷

除了while循環(huán)遏佣，for循環(huán)等基本的遍歷方式挖炬，數(shù)組還支持一種特殊的遍歷：foreach.舉一個簡單的例子：

// 聲明數(shù)組：
int [] scores = new int[50];
// 普通for循環(huán)
for(int i=0;i<scores.length;i++){
      System.out.println(score);
}
// foreach遍歷
for(int score:scores){
      System.out.println(score);
}

因為數(shù)組在內(nèi)存中連續(xù)排布，所以數(shù)組本身就具有可遍歷的能力状婶。

3：數(shù)組天生的優(yōu)勢——索引

數(shù)組最大的優(yōu)勢就是通過索引可以快速查詢一個元素意敛。因為數(shù)組在內(nèi)存中開辟了一段空間馅巷，這一段連續(xù)的空間就是用來存儲數(shù)組元素的，所以當(dāng)我們想獲取某一個數(shù)組索引的元素時草姻，計算機(jī)只要通過這個索引就可以在開辟的內(nèi)存空間中钓猬，找到存放這個元素的地址，繼而通過內(nèi)存地址就可以快速查詢到這個元素撩独。我們將索引查詢的時間復(fù)雜度定義為O(1)敞曹。在后文有關(guān)于時間復(fù)雜度的介紹。當(dāng)數(shù)組的索引變得有一定的語意時综膀，數(shù)組的應(yīng)用就更加方便了异雁，例如：int [] students = new int [50]; 如果索引代表的是班級里學(xué)生們的學(xué)號，如：students[21] 代表的是學(xué)號為21號的學(xué)生僧须，那么這種索引就變得非常有意義纲刀。但并非所有有語意的數(shù)組索引都適用，例如一個公司有10名員工担平，現(xiàn)在需要將員工信息存儲于一個emp[]數(shù)組當(dāng)中示绊，如果將員工的身份證號作為索引去創(chuàng)建一個數(shù)組，那么顯然是不合理的暂论。雖然索引變得有意義面褐，但是計算機(jī)為了存儲10名員工的信息就要在內(nèi)存上開辟身份證號長度的內(nèi)存去存儲，實在是大大浪費(fèi)了空間取胎。索引最好建立在有語意的前提下展哭，但是一定要合理。

4：動態(tài)數(shù)組

什么是動態(tài)數(shù)組闻蛀？

了解Java的人一定知道匪傍，Java Collecion里面，ArrayList的底層實現(xiàn)原理就是動態(tài)數(shù)組觉痛，那么動態(tài)數(shù)組的含義是什么呢役衡？在上文我們說過，如果想要聲明定義一個數(shù)組薪棒，都需要直接或間接地告訴計算機(jī)我們要聲明的數(shù)組的大小手蝎，只有計算機(jī)知道數(shù)組的大小后，才可以為我們的數(shù)組分配具體的內(nèi)存空間俐芯。但是這樣一來棵介，數(shù)組就變得不是那么靈活了，當(dāng)數(shù)組元素已滿吧史，我們就無法繼續(xù)添加元素了邮辽。如果我們開辟了1000個元素空間的數(shù)組，但是僅僅存儲10個元素，那這種情況也是不合理的逆巍，我們希望數(shù)組能夠通過自己的存儲元素的實際數(shù)量去調(diào)節(jié)自己的容量大小及塘，這就需要數(shù)組具備動態(tài)的能力。Java 提供的數(shù)組不具備動態(tài)能力锐极，所以笙僚，我們需要自己封裝一個我們自己的數(shù)組，這個數(shù)組需要具備動態(tài)調(diào)節(jié)自身容量大小的能力灵再，即：動態(tài)數(shù)組肋层。

動態(tài)數(shù)組的原理

現(xiàn)有一個數(shù)組：int [] data = new int[5];

arr.png

newArr.png

image.png

再將原數(shù)組的引用 arr指向 新的數(shù)組汪榔。

image.png

public void resize(int newCapacity){
        E [] newData = (E[]) new Object[newCapacity];
        for(int i=0;i<size;i++){
                newData[i] = data[i];
        } 
        data= newData;
}

動態(tài)數(shù)組擴(kuò)容或者縮容的過程封裝成了一個方法：resize.在方法中蒲拉，使用了泛型，用來代表所有類型的數(shù)組痴腌。

5：封裝自己的數(shù)組類——增加元素

現(xiàn)在我們要實現(xiàn)添加元素的方法雌团，這個方法可以在指定的合法的索引位置進(jìn)行元素的添加。例如：在索引index=1處添加元素88

• 原數(shù)組：

  
  
  image.png

• 在索引 index=1處添加元素 88

  
  
  image.png

過程轉(zhuǎn)換為代碼：

public void add(int index,E e){
        if(index<0 || index>size)
            throw new IllegalArgumentException("Index is Illegal");

        if(size == data.length)
            resize(2*data.length);

        for(int i=this.size-1;i>=index;i--){
            data[i+1] = data[i];
        }
        data[index] = e;
        size++;
    }

6：封裝自己的數(shù)組類——刪除元素

舉例：刪除索引為index=1處的元素88.

• 原數(shù)組

  
  
  image.png

• 在索引 index=1處刪除元素 88

  
  
  image.png

• 刪除后的數(shù)組
  

  image.png
  
  可以看到士聪，在本例中锦援，刪除元素88后，我們使用size這樣一個變量去維護(hù)實際數(shù)組元素的數(shù)量剥悟，實際元素的數(shù)量已經(jīng)變?yōu)?了灵寺，但是原本索引為 index=4 處的元素仍然還在，以用戶的角度來看区岗，用戶是無法訪問data[size] 這樣的一個元素的略板，所以最后的這個元素的存在已經(jīng)沒有意義了，理應(yīng)被GC回收躏尉。這樣的元素蚯根，被稱為："Loitering Objects"后众，它們存在并沒有意義胀糜，理應(yīng)被Java的GC回收機(jī)制回收，所以我們需要手動對其進(jìn)行回收工作（非必需）蒂誉，data[size] = null 就可以讓Java的GC進(jìn)行回收教藻。刪除元素的代碼為：

 public E remove(int index){
        if(index<0 || index>=this.size)
            throw new IllegalArgumentException("Index is Illegal");

        E ret = data[index];
        for(int i=index+1;i<=this.size-1;i++){
            data[i-1] = data[i];
        }
        size--;
        // data[size] 為loitering Object 最好將其賦值為null 讓jvm GC自動進(jìn)行垃圾回收
        data[size] = null;

        // &&data.length/2!=0的原因：防止出現(xiàn)當(dāng) data.length = 1 且當(dāng)前無元素即size=0時
        if(this.size == data.length/4 && data.length/2!=0)
            resize(data.length/2);

        return ret;
    }

對于代碼:

 if(this.size == data.length/4 && data.length/2!=0)
            resize(data.length/2);

在后面的文章中，有詳細(xì)的解釋右锨。

7：封裝自己的數(shù)組類——修改元素括堤，查詢元素

• 修改元素

 public void set(int index,E e){
        if(index<0 || index>=this.size)
            throw new IllegalArgumentException("Index is Illegal");

        data[index] = e;
    }

• 查詢元素

 // 查：get
    public E get(int index){
        if(index<0 || index>=this.size)
            throw new IllegalArgumentException("Index is Illegal");

        return data[index];
    }

    // 查：contains
    public boolean contains(E e){
        for(int i=0;i<size;i++){
            if(data[i].equals(e)){
                return true;
            }
        }
        return false;
    }

    // 查：find
    public int find(E e){
        for(int i=0;i<size;i++){
            if(data[i].equals(e)){
                return i;
            }
        }
        return -1;
    }

8：簡單的時間復(fù)雜度分析

時間復(fù)雜度分析

常見的時間復(fù)雜度有：O(1),O(n),O(n logn),O(n^2),等等，其中O( ) 描述的是算法的運(yùn)行時間和輸入數(shù)據(jù)的關(guān)系。拿數(shù)組的索引舉例悄窃，數(shù)組的索引就是一個O(1) 級別的算法讥电，因為知道索引獲取元素的過程和數(shù)據(jù)的數(shù)量級沒有關(guān)系，也就是說無論數(shù)組開辟了10的空間還是開辟了100萬的內(nèi)存空間轧抗，索引任一下標(biāo)的時間都是一個常量恩敌。再例如程序：

public static int sum(int[]nums){
        int sum = 0;
        for(int num:nums){
              sum+=num;
        }
        return sum;
}

上面的程序就是一個O(n) 級別的算法，程序是計算nums數(shù)組所有元素的和横媚，計算出結(jié)果需要將nums數(shù)組從頭至尾遍歷一邊纠炮，而遍歷這個過程則與nums元素的數(shù)量n呈線性關(guān)系，隨著元素個數(shù)n越來越大灯蝴，遍歷需要的時間就越來越長。當(dāng)然，這個時間復(fù)雜度分析其實也忽略了很多常數(shù)及一些細(xì)節(jié)异逐，包括使用的語言不同汉嗽，程序消耗的時間也是有差異的，所以O( )時間復(fù)雜度分析分析的只是一種趨勢问潭。

簡單的時間復(fù)雜度分析與比對

O(1)看疗，O(n)，O(n^2) 這三種級別的算法 哪一種更優(yōu)秀呢睦授？首先两芳，O(1)級別的算法肯定是最優(yōu)的，但是也有一定的弊端去枷。拿數(shù)組的索引來說怖辆，數(shù)組之所以能夠快速索引，就是因為它是一種以空間來換取時間的數(shù)據(jù)結(jié)構(gòu)删顶。如果數(shù)據(jù)的數(shù)量級是千萬級的竖螃，那么數(shù)組就要在內(nèi)存中開辟千萬級的內(nèi)存空間來支持索引，這顯然是不現(xiàn)實逗余。那么O(n)級別的算法一定要比O(n^2)級別的算法更優(yōu)嗎特咆？其實也是不一定的，如T1 = 2000n+10000 這是一個O(n)級別的算法录粱，T2 = n*n 這是一個O(n^2)級別的算法腻格。當(dāng)n取值很小如100時，很顯然 T2的時間要小于T1,但是隨著n的取值越來越大啥繁，O(n)算法的優(yōu)勢就會越來越大菜职。所以從整體上來看O(1)算法最優(yōu)，O(n)算法要優(yōu)于O(n^2)級別的算法旗闽，實際上也確實如此酬核，O(n)算法不僅僅是優(yōu)于O(n^2)蜜另，在海量級的數(shù)據(jù)下，這兩種算法的差異是巨大的嫡意。

分析動態(tài)數(shù)組的時間復(fù)雜度

1. 添加操作
   除了add(int index,E e)方法举瑰，為了方便一些功能 我增加了方法addLast(E e)以及 addFirst(E e)。先不考慮resize操作帶來的影響蔬螟。

• addLast(E e)
  O(1)
• addFirst(E e)
  O(n)
• add(int index,E e)
  當(dāng)index=0時嘶居，相當(dāng)于向數(shù)組的頭添加一個元素，所有的元素都需要向后挪動一個位置促煮，所以是O(n)的時間復(fù)雜度邮屁，當(dāng)index取值為size時，則相當(dāng)于addLast操作菠齿，即向數(shù)組的末尾添加一個元素佑吝，是O(1)的時間復(fù)雜度。index的取值在0~size 的概率是相等的绳匀，這里面涉及到概率論的問題芋忿，平均而言，add(int index,E e) 的時間復(fù)雜度為：O(n/2) 疾棵。也就是說addLast (E e) 直接就可以將增加的元素添加到數(shù)組的末尾戈钢，addFirst (E e)操作，數(shù)組挪動了n個元素是尔，add(int index,E e) 操作平均來講殉了，數(shù)組需要挪動n/2個元素，它消耗的時間也同數(shù)組的個數(shù)n 呈線性關(guān)系拟枚，所以可以將add(int index,E e) 看作一個O(n)時間復(fù)雜度的操作（僅僅代表該方法的時間復(fù)雜度同元素個數(shù)呈線性關(guān)系）薪铜。

整體來看 動態(tài)數(shù)組的添加元素方法：add是一個O(n)級別時間復(fù)雜度的算法。

2. 刪除操作
   除了remove(int index)方法恩溅，為了方便一些功能隔箍，我也增加了方法removeFirst() 以及removeLast()方法。同樣脚乡，也不考慮resize()方法對刪除操作帶來的影響蜒滩。

• removeFirst()
  O(n)
• removeLast()
  O(1)
• remove(int index)
  對于remove(int index)方法時間復(fù)雜度的分析和add(int index,E e)方法的分析過程類似，index的取值在 0~n的概率是相等的奶稠，平均上來看俯艰，remove(int index)方法會使數(shù)組移動n/2個元素，也就是說remove(int index)操作的時間與數(shù)組元素的個數(shù)n呈線性關(guān)系窒典，remove(int index)也是一個O(n)級別時間復(fù)雜度的算法蟆炊。

整體上來看，刪除操作remove為 O(n)的時間復(fù)雜度瀑志。

3. 修改操作

• set(int index,E e)
  修改操作只有一個方法即：set(int index,E e)。因為其利用了數(shù)組快速索引的特性，所以修改操作為O(1)的時間復(fù)雜度劈猪。

4. 查詢操作

• get(int index)
  O(1)
• contains(E e)

public boolean contains(E e){
        for(int i=0;i<size;i++){
            if(data[i].equals(e))
                return true;
        }
        return false;
}

contains方法為查看數(shù)組中是否包含某個元素昧甘，因為contains方法需要將數(shù)組整體進(jìn)行一次遍歷，所以contains方法為O(n)的時間復(fù)雜度战得。

• find(E e)

  public int find(E e){
        for(int i=0;i<size;i++){
            if(data[i].equals(e))
                return i;
        }
        return -1;
    }

find方法為查看是否數(shù)組中包含某個元素充边，如果包含則返回這個元素所在的索引，如果沒有則返回-1常侦。find方法為O(n)的時間復(fù)雜度浇冰。

5. resize操作
   resize操作的本質(zhì)是將一個數(shù)組的所有元素依次賦值給一個空數(shù)組，它涉及到數(shù)組的遍歷聋亡，所以resize方法為O(n)的時間復(fù)雜度肘习。

9：均攤復(fù)雜度與復(fù)雜度震蕩

以上，我們簡單分析了增刪該查操作的時間復(fù)雜度坡倔，但是除了改查兩種操作不涉及到resize擴(kuò)容或縮容操作外漂佩，添加元素和刪除元素都有resize這種機(jī)制在里面。

均攤復(fù)雜度

以時間復(fù)雜度為O(1)的方法addLast(E e)來舉例罪塔，如果初始化數(shù)組的原始capacity為10投蝉，開始時，數(shù)組內(nèi)沒有任何元素征堪。一直使用addLast(E e)向數(shù)組末尾添加元素瘩缆，在添加10次后，即第十一次再次添加元素則觸發(fā)了一次擴(kuò)容操作佃蚜，擴(kuò)容后的capacity為20即 原來的capacity的2倍咳榜。而在第21次添加元素操作時，又再次觸發(fā)了擴(kuò)容的操作爽锥。

image.png

復(fù)雜度震蕩

還記得這段代碼么？

if(this.size == data.length/4 && data.length/2!=0)
            resize(data.length/2);

這段代碼是remove(int index)方法中凯傲，data.length/2!=0是為了防止出現(xiàn)：數(shù)組無元素犬辰，capacity已經(jīng)縮容到1的這種情況，防止resize縮容到capacity=0,這很顯然是錯誤的冰单。代碼中幌缝，當(dāng)數(shù)組元素的個數(shù)減少到 數(shù)組capacity的四分之一時，觸發(fā)了縮容球凰，且縮容為當(dāng)前capacity的一半狮腿，為什么要這樣寫呢？這種寫法叫做 Lazy 機(jī)制呕诉，它是為了解決復(fù)雜度震蕩的方法缘厢。如果我們將代碼寫成：

if(this.size == data.length/2 && data.length/2!=0)
            resize(data.length/2);

那么就會出現(xiàn)一個問題：

image.png

當(dāng)前數(shù)組的size為5，capacity為5,現(xiàn)在對數(shù)組進(jìn)行這樣的操作：

1. addLast,觸發(fā)擴(kuò)容擴(kuò)容成capacity=10
2. removeLast,觸發(fā)縮容甩挫，又縮容成capacity=5
3. addLast,觸發(fā)擴(kuò)容擴(kuò)容成capacity=10
4. removeLast,觸發(fā)縮容贴硫，又縮容成capacity=5
   ... ...

想必我們已經(jīng)看到問題的所在了，原本為O(1) 時間復(fù)雜度的addLast和removeLast方法硬生生地被玩成了O(n)的算法伊者，出現(xiàn)這個問題的原因就是因為我們在remove操作時英遭，resize太過于著急了（too Eager），所以造成了復(fù)雜度震蕩亦渗。其實解決方法已經(jīng)給出挖诸，就是Lazy機(jī)制。當(dāng)數(shù)組元素的個數(shù)到capacity的一半時法精，不著急去縮容多律，而是等到size==capacity/4時，將capacity的容積縮容為capacity/2搂蜓。這種看似懶惰的機(jī)制狼荞，卻解決了這樣的一個問題。

最后附上 GitHub的代碼鏈接：MyArray
測試代碼：Main