1. 屬性

（1）一個數(shù)組就是一系列的插槽，每一個插槽都包含一個元素（值或?qū)ο螅?/p>

（2）每個插槽都有一個固定的索引输硝，這些索引是連續(xù)的整數(shù)

（3）一個數(shù)組的長度就是插槽的個數(shù)，長度是在創(chuàng)建這個數(shù)組的時候就固定的

（4）使用索引可以有效地訪問每個插槽父泳，每次訪問的時間是 O(1)

（5）排序數(shù)組：如果數(shù)組中的元素按照升序排列凶掰，即每個元素小于或等于其右側(cè)的元素，這個數(shù)組就是被排序好的數(shù)組

對于數(shù)字寄摆，x is less than y谅辣，意味著 x 在數(shù)值上小于 y

對于字符串，x is less than y婶恼，意味著 x 在字典上位于 y 前面桑阶，比如 bat 小于 bath，又都小于 bay

compareable 接口

comparable 接口中必須被實現(xiàn)的方法是 compareTo 方法

2. 數(shù)組中的方法

comparable 接口中的 compareTo 方法

如果一個類實現(xiàn)了 comparable 接口勾邦，那它必須實現(xiàn)其中的 compareTo 方法蚣录，String 和 Integer 中自帶的 compareTo 方法，就是實現(xiàn)自這個類

二分法查找元素索引

a 為需要查找元素的數(shù)組眷篇，key 為想要查找的值

（1）如果數(shù)組中含有這個值萎河，那么直接返回其索引

（2）如果數(shù)組中不含有這個值，那么這個值的索引為 “ - （元素應(yīng)該插入的位置 + 1） ”蕉饼，

? ? ? int arr [] =newint[]{1,3,4,5,8,9};

? ? ? Arrays.sort(arr);

? ? ? int index1 = Arrays.binarySearch(arr,6);

????????????6 不在數(shù)組中虐杯，取代 8 稱為新的索引為 4 的元素，所以昧港，返回值為 -(4 + 1) 即為 -5

? ? ? int index2 = Arrays.binarySearch(arr,4);

? ? ? ? ? ? 4 在數(shù)組中擎椰，返回 4 的索引 2

? ? ? int index3 = Arrays.binarySearch(arr,0);

? ? ? ? ? ? 0 不在數(shù)組中，取代 1 稱為新的索引為 0 的元素创肥，所以达舒，返回值為 -(0 + 1) 即為 -1

? ? ? int index4 = Arrays.binarySearch(arr,10);

? ? ? ? ? ? 10 不在數(shù)組中，應(yīng)插在 9? 之后叹侄，成為索引為 6 的元素巩搏，所以，返回值為 -(6 + 1) 即為 -7

注意：還有一種 4 參數(shù)的二分法查找索引法

binarySearch(Object[] a, int fromIdex, int toIndex, Object Key)

a 為需要查找元素的數(shù)組圈膏，fromIndex 為查找起始的索引（包含在內(nèi)）塔猾，toIndex 為查找結(jié)束的索引（不包含在內(nèi)），Key 為需要查找的元素

（1）如果范圍中包含該元素稽坤，直接返回其索引

（2）如果范圍中不包含該元素丈甸，返回值為 “ - （元素應(yīng)該插入的位置 + 1） ”

????????int arr [] =newint[]{1,3,4,5,8,9};

? ? ? ? Arrays.sort(arr);

? ? ? ? int index5 = Arrays.binarySearch(arr,1, 4, 6);

? ? ? ? ? ? ? 6 不在范圍中，應(yīng)插在 5 后面尿褪，成為新的 4 索引元素睦擂，所以，返回值為 -（4 + 1）杖玲，即為 -5

? ? ? int index6 = Arrays.binarySearch(arr,1, 4, 4);

? ? ? ? ? ? ? 4 在范圍中顿仇，返回其索引 2

? ? ? int index7 = Arrays.binarySearch(arr,1, 4 ,2);

? ? ? ? ? ? ? 2 不在范圍中，應(yīng)插在 3 前面摆马，成為新的 1 索引元素臼闻，所以，返回值為 -（1 + 1）囤采，即為 -2

? ? ? int index8 = Arrays.binarySearch(arr,1, 3, 10);

? ? ? ? ? ? ? 10 不在范圍中述呐，應(yīng)插在 4 后面，成為新的 3 索引元素蕉毯，所以乓搬，返回值為 -（3 + 1），即為 -4

? ? ? int index9 = Arrays.binarySearch(arr,1, 3, 0);

? ? ? ? ? ? ? 0 不在范圍中代虾，應(yīng)插在 3 前面进肯，成為新的 1 索引元素，所以棉磨，返回值為 -（1 + 1）江掩，即為 -2

注意：由于在查找時，使用的是二分法乘瓤，是從中間開始查找环形，所以如果出現(xiàn)相同元素，不同索引時馅扣，查找該元素時斟赚，會返回更接近中間的索引值

復(fù)制數(shù)組生成新長度的數(shù)組

original 為原數(shù)組，newLength 為新數(shù)組的長度

int[] original = new int[] {1,2,3,4,5}

int[] newArray = Arrays.copyOf(original,5)

則 newArray 為 1差油，2拗军，3，4蓄喇，5

int[] newArray = Arrays.copyOf(original,3)

則 newArray 為 1发侵，2，3

int newArray = Arrays.copyOf(original,10)

則 newArray 為 1妆偏，2刃鳄，3，4钱骂，5叔锐，0挪鹏，0，0愉烙，0讨盒，0

不生成新數(shù)組，排序數(shù)組

前者中 a 為需要排序的整數(shù)數(shù)組步责，排序后的數(shù)組元素升序排列

結(jié)果是 0返顺，1，2蔓肯，3遂鹊，4，5蔗包，6妓笙，7昌渤，8物咳，9

注意：還有一種進階版排序 sort(int[] a, int fromIndex, int toIndex)

只對 fromIndex 起始索引到 toIndex 結(jié)束索引中間的元素進行排序幔睬，包括起始索引，不包括結(jié)束索引

結(jié)果是 7旧噪，8吨娜，9，2淘钟，3宦赠，4，1米母，0勾扭，6，5

后者是對泛型進行特定順序排序铁瞒，既可為升序妙色，也可為降序

繼承 comparator 接口，并重寫里面的類慧耍，使小于返回正數(shù)身辨，大于返回負(fù)數(shù)

通過新的自定義比較器，實現(xiàn)反向排序數(shù)組芍碧，結(jié)果為 9煌珊，8，7泌豆，6定庵，5，4，3蔬浙，2猪落，1，0

3. 插入 insertion

將插入索引后的元素敛滋，依次先后平移一個索引

我們假設(shè) n = right - left + 1 為數(shù)組的長度

其中许布，第 1 步是將索引從 ins 到 right - 1 的元素復(fù)制到 ins + 1 到 right兴革，其 copy 的最多次數(shù)為 n - 1 - 0 次绎晃，最少次數(shù)為 0 次，其平均次數(shù)為? $\frac{n - 1}{2}$ 次杂曲，第 2 步是將插入元素復(fù)制到插入索引處庶艾，復(fù)制了 1 次

總共平均復(fù)制 $\frac{n-1}{2}+1= \frac{n}{2}+\frac{1}{2} \approx \frac{n}{2}$ 次，時間復(fù)雜度為 O(n)

4. 刪除 deletion

刪除指定索引位置的元素擎勘，將后面的元素依次向前移動

同理咱揍，第 1 步平均復(fù)制 $\frac{n-1}{2}$ 次，第二步無需復(fù)制棚饵，總共平均復(fù)制 $\frac{n-1}{2}=\frac{n}{2}-\frac{1}{2} \approx \frac{n}{2}$ 次煤裙，時間復(fù)雜度為 O(n)

5. 搜索 searching

（1）線性：

線性搜索算法

我們假設(shè) n = right - left + 1 為數(shù)組的長度

最快查找，即第一次就查找成功噪漾，需要查找 1 次

最慢查找硼砰，即最后依次才查找成功，或是遍歷整個數(shù)組后沒查找到欣硼，返回了 null题翰，需要查找 n 次

平均查找次數(shù)? $\frac{n+1}{2}$ $\approx \frac{n}{2}$ 次，時間復(fù)雜度為 O(n)

（2）二分法：

首先诈胜，二分法查找法必須應(yīng)用在排序好的數(shù)組之上?

二分法搜索算法

由于其多次查找增長時間不是線性的豹障，所以不能用求平均值方法來計算

其最大查找次數(shù)為 $floor(\log_2 n) +1$ $\approx \log_2 n$ 次時間，時間復(fù)雜度為 O(logn)

總結(jié)：

數(shù)組查找算法的復(fù)雜度

6. 融合 merging

給定兩個排序好的數(shù)組焦匈，創(chuàng)建第三條排序好的數(shù)組包含前兩個數(shù)組中的所有元素

思路：比較兩個數(shù)組最左邊的元素血公，哪個元素較小，就放進第三個數(shù)組中

數(shù)組排序方法

通過計算復(fù)制次數(shù)來確定時間復(fù)雜度：假設(shè) n1 和 n2 分別是 a1 和 a2 的長度缓熟，a1 和 a2 中的每一個元素都復(fù)制了一次累魔，復(fù)制到 a3 中，所以荚虚，復(fù)制的次數(shù)是 n = n1 + n2

時間復(fù)雜度為 O(n)

通過計算比較次數(shù)來確定時間復(fù)雜度：?

融合的數(shù)組為 0 1 2 3 4

? ? ? ? ? ? ? ? ? ? ? ?5 6 7 8 9 10

這是需要比較次數(shù)最少的情況薛夜，需要比較 5 次，融合部分融合后的長度是 10

融合的數(shù)組為 0 2 4 6 8

? ? ? ? ? ? ? ? ? ? ? ?1 3 5 7 9 11

這是需要比較次數(shù)最多的情況版述，需要比較 9 次梯澜，融合部分融合后的長度是 10

假設(shè)需要融合部分融合后的長度是 n，至多需要比較 n - 1 次，所以時間復(fù)雜度為 O(n)

等差數(shù)列：

等差數(shù)列的求和方式 1晚伙，2吮龄，3，4咆疗，5漓帚，……，n

一共有 n 個數(shù)午磁，因為是線性排列的尝抖，所以其平均數(shù)是? $\frac{n+1}{2}$ $=\frac{(n-1)+2}{2}$ ，所以和為 $\frac{n(n+1)}{2}$

7. 排序 sorting

現(xiàn)在給出一個沒有排序的數(shù)組迅皇，重新安排其中的元素昧辽，使其達到升序排列

這是一個重要的算法，因為排序后的數(shù)組能更有效地查找元素和與其他數(shù)組融合

下面將介紹能夠?qū)崿F(xiàn)排序的多種算法：

（1）選擇排序 selection sort

思路：找到數(shù)組中的最小元素登颓，將其交換到最左邊的插槽搅荞，重復(fù)此操作，每次忽略最左側(cè)的插槽（因為它已經(jīng)排序好了）

選擇排序法

通過計算比較次數(shù)來分析時間復(fù)雜度：

令 n = right - left + 1 為數(shù)組的長度

第 1 個元素框咙，需要和其他 n - 1 個元素進行比較咕痛，比較過后，將其放在最左側(cè)喇嘱，并在以后的比較中忽略它

第 2 個元素茉贡，需要和其他 n - 2 個元素進行比較，比較過后婉称，將其放在最左側(cè)块仆，并在以后的比較中忽略它

最后一個元素，只和它自己比較 1 次

比較的次數(shù)為 (n - 1) + (n - 2) + (n - 3) + …… + 2 + 1 =? $\frac{n^2 }{2}$ 次

時間復(fù)雜度為 $O(n^2)$

選擇算法的基本實現(xiàn)框架

下面是一個例子：

選擇算法的實現(xiàn)

最終的輸出結(jié)果

注意：對許多問題需要進行分解并解決王暗，對與困難的問題悔据，將其分解為多個簡單的問題，并逐步解決俗壹，最終將其組成最后的答案科汗，在這過程中自然而然就要用到遞歸算法

（2）融合排序 merge sort

思路：將數(shù)組分成兩個相同長度的子數(shù)組

分別將子數(shù)組排序

融合排序好的數(shù)組

融合排序法

融合排序法就是分步解決問題迭代組合答案的典型

通過計算比較次數(shù)來計算時間復(fù)雜度：

令 n = right - left + 1 為數(shù)組的長度

假設(shè)排序一個長度為 m 的數(shù)組所需要的比較次數(shù)為 comps(m)

那么對兩個長度為 $\frac{n}{2}$ 的數(shù)組進行排序的比較次數(shù)為 2comps( $\frac{n}{2}$ )

兩個長度為 $\frac{n}{2}$ 的數(shù)組，融合部分融合后的長度為 n绷雏，則至多需要比較 n - 1 次

因此头滔，一共需要比較的次數(shù)是

comps(n) = 2 comps( $\frac{n}{2}$ ) + n - 1 (if n > 1)

comps(n) = 0 (if n <= 1)

如何計算 comps(n) 呢？

c(n) = 2 c( $\frac{n}{2}$ ) + n - 1 ---------------------------------------------------------------------------------- 1

=> c( $\frac{n}{2}$ ) = 2 c( $\frac{n}{4}$ ) +? $\frac{n}{2}$ ?- 1 ????=> c(n) = 4 c( $\frac{n}{4}$ ) + 2 n - 3 ------------------------------- 2

=> c( $\frac{n}{4}$ ) = 4 c( $\frac{n}{8}$ ) +? $\frac{n}{4}$ - 1 ????=> c(n) = 8 c( $\frac{n}{8}$ ) + 3 n -7 -------------------------------- 3

=> c(n) =? $2^m c(\frac{n}{2^m }) + mn - (2^m - 1)$ ?--------------------------------------------------- m

取特殊值涎显，令? $2^m = n$ 坤检，則 $m = \log_2 n$ ，代入 m 式

=> c(n) = n c(1) + n? $\log_2 n$ ?- n + 1

c(1) = 0 代入上式

=> c(n) = n? $\log_2 n$ ?- n + 1

則時間復(fù)雜度為 $O(\log_2 n)$ 期吓，此外早歇，由于用到了新的數(shù)組，空間復(fù)雜度是 O(n)

數(shù)據(jù)結(jié)構(gòu)-3.數(shù)組數(shù)據(jù)結(jié)構(gòu)