前言

數(shù)組(Array)是一種線性表數(shù)據(jù)結(jié)構(gòu)，利用一組連續(xù)的內(nèi)存空間，存儲(chǔ)一組具有相同類型的數(shù)據(jù)。

概念介紹

首先我們說(shuō)一下什么是線性表，線性表就是數(shù)據(jù)排成一條線的數(shù)據(jù)結(jié)構(gòu)，每個(gè)線性表最多只有前和后兩個(gè)方向，數(shù)組、鏈表、隊(duì)列、棧等都是線性表結(jié)構(gòu)。那么什么是非線性表呢？二叉樹、堆、圖等數(shù)據(jù)結(jié)構(gòu)就是非線性表，在非線性表中數(shù)據(jù)之間并不是簡(jiǎn)單的前后關(guān)系。

其次，數(shù)組的內(nèi)存空間是連續(xù)的，數(shù)據(jù)類型也是相同的，正是因?yàn)檫@兩個(gè)特性，數(shù)組的隨機(jī)訪問速度非?？?。我們來(lái)看下數(shù)組是怎么進(jìn)行隨機(jī)訪問的，假定我們有一個(gè)長(zhǎng)度為10的int類型的數(shù)組int[] a = new int[10]，計(jì)算機(jī)給該數(shù)組分配的內(nèi)存空間為100~110，其中內(nèi)存塊的首地址base_address=100。當(dāng)計(jì)算機(jī)隨機(jī)訪問數(shù)組中的某個(gè)元素時(shí)，會(huì)先通過尋址公式a[i]_address = base_address + i * data_type_size計(jì)算出該元素的內(nèi)存地址，其中data_type_size代表數(shù)組中每個(gè)元素的大小，我們的數(shù)組是int類型的，所以每個(gè)元素就是4個(gè)字節(jié)。這樣計(jì)算出元素的地址后就立馬找到該元素了。

面試的時(shí)候我們經(jīng)常被問到數(shù)組和鏈表的區(qū)別，有時(shí)候我們會(huì)回答“鏈表適合插入、刪除，時(shí)間復(fù)雜度是O(1);數(shù)組適合查找，查找的時(shí)間復(fù)雜度是O(1)”，其實(shí)這種描述是不準(zhǔn)確的，數(shù)組適合查找這是沒問題的，但是時(shí)間復(fù)雜度不是O(1)，即便是用二分查找對(duì)排好序的數(shù)組進(jìn)行查找，時(shí)間復(fù)雜度也是O(Logn)，所以，正確的表述應(yīng)該是“數(shù)組支持隨機(jī)訪問，根據(jù)下標(biāo)隨機(jī)訪問的時(shí)間復(fù)雜度是O(1)”。

數(shù)組聲明

數(shù)組聲明有兩種方式：

數(shù)據(jù)類型 [] 數(shù)組名稱 = new 數(shù)據(jù)類型[數(shù)組長(zhǎng)度];

數(shù)據(jù)類型 [] 數(shù)組名稱 = {數(shù)組元素1，數(shù)組元素2，......}

數(shù)組實(shí)現(xiàn)

我們知道，一個(gè)數(shù)組需要具備如下功能：

• 插入數(shù)據(jù)
• 查找數(shù)據(jù)
• 刪除數(shù)據(jù)
• 迭代數(shù)據(jù)

下邊，我們實(shí)現(xiàn)一個(gè)自己的數(shù)組結(jié)構(gòu)：

public class MyArray { // 定義一個(gè)數(shù)組 private int[] intArray; // 定義數(shù)組的實(shí)際有效長(zhǎng)度 private int elems; // 定義數(shù)組的最大長(zhǎng)度 private int length; // 默認(rèn)構(gòu)造一個(gè)長(zhǎng)度為50的數(shù)組 public MyArray() { elems = 0; length = 50; intArray = new int[length]; } // 構(gòu)造函數(shù)，初始化一個(gè)長(zhǎng)度為length 的數(shù)組 public MyArray(int length) { elems = 0; this.length = length; intArray = new int[length]; } // 獲取數(shù)組的有效長(zhǎng)度 public int getSize() { return elems; } /** * 遍歷顯示元素 */ public void display() { for (int i = 0; i < elems; i++) { System.out.print(intArray[i] + " "); } System.out.println(); } /** * 添加元素 * * @param value,假設(shè)操作人是不會(huì)添加重復(fù)元素的，如果有重復(fù)元素對(duì)于后面的操作都會(huì)有影響。 * @return 添加成功返回true,添加的元素超過范圍了返回false */ public boolean add(int value) { if (elems == length) { return false; } else { intArray[elems] = value; elems++; } return true; } /** * 根據(jù)下標(biāo)獲取元素 * * @param i * @return 查找下標(biāo)值在數(shù)組下標(biāo)有效范圍內(nèi)，返回下標(biāo)所表示的元素 查找下標(biāo)超出數(shù)組下標(biāo)有效值，提示訪問下標(biāo)越界 */public int get(int i) {if (i < 0 || i > elems) {System.out.println("訪問下標(biāo)越界");}return intArray[i];}/** * 查找元素 * * @param searchValue * @return 查找的元素如果存在則返回下標(biāo)值，如果不存在，返回 -1 */public int find(int searchValue) {int i;for (i = 0; i < elems; i++) {if (intArray[i] == searchValue) {break;}}if (i == elems) {return -1;}return i;}/** * 刪除元素 * * @param value * @return 如果要?jiǎng)h除的值不存在，直接返回 false;否則返回true，刪除成功 */public boolean delete(int value) {int k = find(value);if (k == -1) {return false;} else {if (k == elems - 1) {elems--;} else {for (int i = k; i < elems - 1; i++) {intArray[i] = intArray[i + 1];}elems--;}return true;}}/** * 修改數(shù)據(jù) * * @param oldValue原值 * @param newValue新值 * @return 修改成功返回true，修改失敗返回false */public boolean modify(int oldValue, int newValue) {int i = find(oldValue);if (i == -1) {System.out.println("需要修改的數(shù)據(jù)不存在");return false;} else {intArray[i] = newValue;return true;}}}

插入數(shù)據(jù)

前面我們說(shuō)了，數(shù)組的插入和刪除操作效率特別低，這是因?yàn)閮?nèi)存空間是連續(xù)的，為了保證內(nèi)存空間的連續(xù)性，在插入和刪除時(shí)會(huì)做很多搬移數(shù)據(jù)的操作。比如，我們有一個(gè)長(zhǎng)度為n的數(shù)組，現(xiàn)在要將一個(gè)數(shù)據(jù)插入到數(shù)組的第k個(gè)位置，為了把這個(gè)位置騰出來(lái)給新來(lái)的數(shù)據(jù)，我們需要將第k~n這部分的元素順序的往后挪一位，如下代碼所示：

public static int[] insertVal(int[] arr, int insertIndex, int insertVal){ if(insertIndex < 0 || insertIndex > arr.length){ throw new IllegalArgumentException("插入位置錯(cuò)誤"); } int[] tmpArr = Arrays.copyOf(arr, arr.length + 1); // 將insertIndex后邊的元素一次挪動(dòng)一位，給新元素騰空，從最后一個(gè)元素開始挪 for (int i = tmpArr.length - 1; i > insertIndex; i--) { tmpArr[i] = tmpArr[i - 1]; } tmpArr[insertIndex] = insertVal; return tmpArr;}

如果在數(shù)組的末尾插入元素，那就不需要移動(dòng)數(shù)據(jù)了，這時(shí)的時(shí)間復(fù)雜度為O(1)。但如果在數(shù)組的開頭插入元素，那所有的數(shù)據(jù)都需要依次往后移動(dòng)一位，所以最壞時(shí)間復(fù)雜度是O(n)。因?yàn)槲覀冊(cè)诿總€(gè)位置插入元素的概率是一樣的，所以平均情況時(shí)間復(fù)雜度為 (1+2+…n)/n=O(n)。如果數(shù)組中的數(shù)據(jù)是有序的，我們?cè)谀硞€(gè)位置插入一個(gè)新的元素時(shí)，就必須按照剛才的方法搬移k之后的數(shù)據(jù)。但是，如果數(shù)組中存儲(chǔ)的數(shù)據(jù)并沒有任何規(guī)律，數(shù)組只是被當(dāng)作一個(gè)存儲(chǔ)數(shù)據(jù)的集合。在這種情況下，如果要將某個(gè)數(shù)組插入到第k個(gè)位置，為了避免大規(guī)模的數(shù)據(jù)搬移，我們還有一個(gè)簡(jiǎn)單的辦法就是，直接將第k位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第k個(gè)位置。如下代碼所示：

public static int[] insertVal(int[] arr, int insertIndex, int insertVal){ if(insertIndex < 0 || insertIndex > arr.length){ throw new IllegalArgumentException("插入位置錯(cuò)誤"); } int[] tmpArr = Arrays.copyOf(arr, arr.length + 1); if(insertIndex == arr.length){ // 插入到最后 tmpArr[insertIndex] = insertVal; } else { tmpArr[arr.length] = arr[insertIndex]; tmpArr[insertIndex] = insertVal; } return tmpArr;}

利用這種方式，在特定場(chǎng)景下，在第k個(gè)位置插入一個(gè)元素的時(shí)間復(fù)雜度就會(huì)降為O(1)，快速排序算法就是這么干的。

刪除數(shù)據(jù)

和上面的插入數(shù)據(jù)一樣，如果我們要?jiǎng)h除第k個(gè)位置的數(shù)據(jù)，為了保證內(nèi)存的連續(xù)性，第k之后的數(shù)據(jù)都要往前挪一位，和插入類似，如果刪除數(shù)組末尾的數(shù)據(jù)，則最好情況時(shí)間復(fù)雜度為O(1)；如果刪除開頭的數(shù)據(jù)，則最壞情況時(shí)間復(fù)雜度為O(n)；平均情況時(shí)間復(fù)雜度也為 O(n)。如下代碼所示：

public static int[] delete(int[] arr, int index) {// 判斷是否合法 if (index >= arr.length || index < 0) { throw new IllegalArgumentException("位置錯(cuò)誤"); } int[] res = new int[arr.length - 1]; for (int i = 0; i < res.length; i++) { if (i < index) { res[i] = arr[i]; } else { res[i] = arr[i + 1]; } }return res;}

實(shí)際上，在某些特殊場(chǎng)景下，我們可以將多次刪除操作合并執(zhí)行，例如數(shù)組a[8]中存儲(chǔ)了8個(gè)元素：a，b，c，d，e，f，g，h?，F(xiàn)在，我們要依次刪除 a，b，c三個(gè)元素。為了避免 d，e，f，g，h 這幾個(gè)數(shù)據(jù)會(huì)被搬移三次，我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)。每次的刪除操作并不是真正地搬移數(shù)據(jù)，只是記錄數(shù)據(jù)已經(jīng)被刪除。當(dāng)數(shù)組沒有更多空間存儲(chǔ)數(shù)據(jù)時(shí)，我們?cè)儆|發(fā)執(zhí)行一次真正的刪除操作，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移。

以上其實(shí)就是JVM的標(biāo)記清除算法的實(shí)現(xiàn)原理(大多數(shù)主流虛擬機(jī)采用可達(dá)性分析算法來(lái)判斷對(duì)象是否存活，在標(biāo)記階段，會(huì)遍歷所有 GC ROOTS(根對(duì)象)，將所有GC ROOTS可達(dá)的對(duì)象標(biāo)記為存活。只有當(dāng)標(biāo)記工作完成后，清理工作才會(huì)開始。不足：1.效率問題：標(biāo)記和清理效率都不高，但是當(dāng)知道只有少量垃圾產(chǎn)生時(shí)會(huì)很高效。2.空間問題：會(huì)產(chǎn)生不連續(xù)的內(nèi)存空間碎片。)

數(shù)組越界問題

在C語(yǔ)言中，只要不是訪問受限的內(nèi)存，所有的內(nèi)存空間都是可以自由訪問的。所以在C語(yǔ)言中即便數(shù)據(jù)訪問越界，程序依然是可以執(zhí)行的，只是這時(shí)候程序會(huì)出現(xiàn)莫名其妙的執(zhí)行結(jié)果，數(shù)組越界在C語(yǔ)言中是一種未決行為，并沒有規(guī)定數(shù)組訪問越界時(shí)編譯器應(yīng)該如何處理。因?yàn)?#xff0c;訪問數(shù)組的本質(zhì)就是訪問一段連續(xù)內(nèi)存，只要數(shù)組通過偏移計(jì)算得到的內(nèi)存地址是可用的，那么程序就可能不會(huì)報(bào)任何錯(cuò)誤。但是高級(jí)語(yǔ)言，如java語(yǔ)言是自帶檢查機(jī)制的，如果訪問數(shù)據(jù)越界會(huì)報(bào)java.lang.ArrayIndexOutOfBoundsException錯(cuò)誤。

容器類與數(shù)組的使用場(chǎng)景

現(xiàn)在很多的編程語(yǔ)言中都提供了容器類，如java語(yǔ)言中的ArrayList，那么在進(jìn)行開發(fā)的時(shí)候，什么時(shí)候用容器類，什么時(shí)候用數(shù)組呢？還是以java中的ArrayList為例，這也是我用的最多的容器類，它最大的優(yōu)勢(shì)就是使用方便，已經(jīng)封裝了一系列的操作，而且不用手動(dòng)為其擴(kuò)容，ArrayList支持動(dòng)態(tài)擴(kuò)容。

數(shù)組定義的時(shí)候需要預(yù)先指定大小，進(jìn)而分配連續(xù)的存儲(chǔ)空間。如果我們定義的數(shù)組大小是10，這時(shí)候來(lái)了第11個(gè)數(shù)組元素，我們需要重新分配一塊更大的存儲(chǔ)空間，將原來(lái)的數(shù)組復(fù)制過去(java中已經(jīng)封裝了工具類System.arraycopy和Arrays.copyOf)，然后將新的數(shù)據(jù)插入。如果使用ArrayList，我們就不需要關(guān)心底層的擴(kuò)容邏輯，ArrayList已經(jīng)幫我們實(shí)現(xiàn)好了，每次空間不夠的時(shí)候，它就會(huì)將空間自動(dòng)擴(kuò)容為1.5倍大小，如下為ArrayList中擴(kuò)容的代碼：

/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = **Arrays.copyOf**(elementData, newCapacity);}

由以上ArrayList的源碼可以看出，其實(shí)其內(nèi)部在擴(kuò)容時(shí)也是封裝了數(shù)組的拷貝Arrays.copyOf。oldCapacity >> 1右移一位操作，如果該數(shù)為正，則高位補(bǔ)0，若為負(fù)數(shù)，則高位補(bǔ)1，說(shuō)白了就是除以2。由此可以看出新的列表是老的列表的1.5倍。

不過因?yàn)閿U(kuò)容涉及到內(nèi)存申請(qǐng)和數(shù)據(jù)搬移，是比較耗時(shí)的，所以，如果我們事先能確定需要存儲(chǔ)的數(shù)據(jù)大小，最好在創(chuàng)建ArrayList的時(shí)候就事先指定數(shù)據(jù)大小。以下代碼為ArrayList的兩種創(chuàng)建方式：

/** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};............/** * Constructs an empty list with the specified initial capacity. * * @param initialCapacity the initial capacity of the list * @throws IllegalArgumentException if the specified initial capacity * is negative */public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}/** * Constructs an empty list with an initial capacity of ten. */public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

可以看出，如果不指定大小，ArrayList默認(rèn)就是一個(gè)空的對(duì)象。在添加元素時(shí)，該對(duì)象會(huì)將大小設(shè)置為10，下面為ArrayList的源碼：

/** * Default initial capacity. */private static final int **DEFAULT_CAPACITY** = 10;............private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return **Math.max(DEFAULT_CAPACITY, minCapacity);** } return minCapacity;}

言歸正傳，我們接著說(shuō)數(shù)組，ArrayList這一類的集合類已經(jīng)這么強(qiáng)大了，我們還要數(shù)組干什么呢？

其實(shí)很多時(shí)候，用數(shù)組比用ArrayList這一類的集合類更合適：

• 1. 比如int、long這一類的基礎(chǔ)數(shù)據(jù)類型，如果用ArrayList存儲(chǔ)，則需要進(jìn)行裝箱操作，將其封裝為Integer、Long類，裝箱拆箱操作時(shí)需要時(shí)間的，有一定性能消耗。所以這時(shí)候就可以選擇數(shù)組。
• 2. 如果事先知道數(shù)據(jù)大小，并且集合類中的大部分方法用不到，操作非常簡(jiǎn)單的話就可以用數(shù)組。
• 3. 在表示多維數(shù)組時(shí)，用數(shù)組會(huì)更加直觀，如果用集合類，則需要進(jìn)行嵌套。

當(dāng)然，其實(shí)很多時(shí)候我們沒必要過于追求性能，損耗一丟丟的性能，大部分情況下對(duì)系統(tǒng)整體性能沒有什么影響，集合類已經(jīng)幫我們實(shí)現(xiàn)了很多的操作，用起來(lái)是非常方便的。但是如果是做底層開發(fā)，性能就必須做到極致，這時(shí)候優(yōu)先選擇數(shù)組。

二維數(shù)組

對(duì)于 m * n 的數(shù)組，m表示這個(gè)二維數(shù)組有多少個(gè)一維數(shù)組，表示每一個(gè)一維數(shù)組的元素有多少個(gè)。元素 a[i][j] (i

• address = base_address + ( i * n + j) * type_size

二維數(shù)組在進(jìn)行內(nèi)存分配時(shí)，必須知道其一維數(shù)組的大小，首先給一個(gè)地址值給數(shù)組a，然后開始為二位數(shù)組的一維數(shù)組部分進(jìn)行分配空間，如果在定義二維數(shù)組時(shí)，并沒有告訴其二維數(shù)組部分的大小，如：數(shù)據(jù)類型[][] 數(shù)組名 = new 數(shù)據(jù)類型[m][]這時(shí)候就無(wú)法為其一維數(shù)組分配靜態(tài)的內(nèi)存空間，這時(shí)候打印其地址值都是null,但是可以動(dòng)態(tài)的分配空間。

下標(biāo)之謎

現(xiàn)在我們思考一個(gè)問題，數(shù)組的下標(biāo)為什么從0開始，按照人的思維邏輯，從1開始應(yīng)該是更合理才是？

從數(shù)組存儲(chǔ)數(shù)據(jù)的內(nèi)存模型上來(lái)看，“下標(biāo)”最確切的定義應(yīng)該是“偏移(offset)”，也就是元素距離數(shù)組首地址的偏移量。a[0]也就是偏移量為0的位置，也就是首地址，a[k]表示偏移k個(gè)元素類型長(zhǎng)度的位置，所以a[k]的內(nèi)存地址計(jì)算公式為：

a[k]_address = base_address + k * type_size

但是，如果數(shù)組從1開始計(jì)數(shù)呢，那計(jì)算a[k]的內(nèi)存地址公式就變?yōu)?#xff1a;

a[k]_address = base_address + (k-1)*type_size

對(duì)比以上兩個(gè)計(jì)算公式，我們會(huì)發(fā)現(xiàn)，如果數(shù)組下標(biāo)從1開始，每次隨機(jī)訪問數(shù)組元素時(shí)都多了一次減法運(yùn)算，對(duì)于CPU來(lái)說(shuō)，就多了一次減法指令。數(shù)組值得稱贊的地方就是通過下標(biāo)隨機(jī)訪問元素的速度，而通過下標(biāo)隨機(jī)訪問數(shù)組元素又是非?；A(chǔ)的編程操作，效率的優(yōu)化自然要做到極致。為了減少一次減法操作，數(shù)組選擇從0開始編號(hào)也就是理所當(dāng)然了。當(dāng)然還有一方面原因，就是C語(yǔ)言中的數(shù)組下標(biāo)從0開始，其他語(yǔ)言都是在C語(yǔ)言之后出現(xiàn)的，為了減少學(xué)習(xí)學(xué)習(xí)成本，盡量模仿C語(yǔ)言中的語(yǔ)法因此也繼續(xù)用0開始做下標(biāo)。

數(shù)組常用操作

排序

• 直接排序

public static void sort(int[] arr) { for (int x = 0; x < arr.length - 1; x++) { for (int y = x + 1; y < arr.length; y++) { if (arr[x] > arr[y]) { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } } }}

• 冒泡排序

public static void sort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { boolean f = true;// 每一輪都定義一個(gè)開關(guān) // 每次內(nèi)循環(huán)的比較，從0索引開始，每次都在遞減。注意內(nèi)循環(huán)的次數(shù)應(yīng)該是(arr.length - 1 - i)。 for (int j = 0; j < arr.length - 1 - i; j++) { // 比較的索引是j和j+1 if (arr[j] > arr[j + 1]) { int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; f = false;// 發(fā)生交換，修改開關(guān)的狀態(tài) } } // 此輪結(jié)束，查看開關(guān)的狀態(tài) if (f) { // 開關(guān)狀態(tài)沒變，說(shuō)明已經(jīng)完成了排序 // 所以，不用繼續(xù)下一輪了。 break; } }}

• 比較排序(選擇排序)

public static void sort(int[] arr) { // 外層循環(huán)控制的是比較的輪數(shù):元素的個(gè)數(shù)-1 for (int i = 0; i < arr.length - 1; i++) { // 內(nèi)層控制的是兩兩比較的次數(shù) for (int j = i + 1; j < arr.length; j++) { if (arr[i] > arr[j]) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } }}

上面這種選擇排序方式可以優(yōu)化為下面的方式：

public static void sort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int index = i; int value = arr[i]; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < value) { index = j; value = arr[j]; } } // 判斷,是否有必要交換兩個(gè)元素 if (index != i) { int tmp = arr[i]; arr[i] = arr[index]; arr[index] = tmp; } }}

這樣可以減少很多數(shù)據(jù)交換次數(shù)。

• 插入排序

public static void sort(int[] a) { for (int i = 1; i < a.length; i++) { for (int j = i; j > 0; j--) { if (a[j] < a[j - 1]) { int temp = a[j - 1]; a[j - 1] = a[j]; a[j] = temp; } else break; } }}

• 快速排序

快速排序的基本思路如下：

• 假設(shè)我們對(duì)數(shù)組{7, 1, 3, 5, 13, 9, 3, 6, 11}進(jìn)行快速排序。
• 首先在這個(gè)序列中找一個(gè)數(shù)作為基準(zhǔn)數(shù)，為了方便可以取第一個(gè)數(shù)。
• 遍歷數(shù)組，將小于基準(zhǔn)數(shù)的放置于基準(zhǔn)數(shù)左邊，大于基準(zhǔn)數(shù)的放置于基準(zhǔn)數(shù)右邊。
• 此時(shí)得到類似于這種排序的數(shù)組{3, 1, 3, 5, 6, 7, 9, 13, 11}。
• 在初始狀態(tài)下7是第一個(gè)位置，現(xiàn)在需要把7挪到中間的某個(gè)位置k，也即k位置是兩邊數(shù)的分界點(diǎn)。
• 那如何做到把小于和大于基準(zhǔn)數(shù)7的值分別放置于兩邊呢，我們采用雙指針法，從數(shù)組的兩端分別進(jìn)行比對(duì)。
• 先從最右位置往左開始找直到找到一個(gè)小于基準(zhǔn)數(shù)的值，記錄下該值的位置(記作 i)。
• 再?gòu)淖钭笪恢猛艺抑钡秸业揭粋€(gè)大于基準(zhǔn)數(shù)的值，記錄下該值的位置(記作 j)。
• 如果位置i
• 如果執(zhí)行到i==j，表示本次比對(duì)已經(jīng)結(jié)束，將最后i的位置的值與基準(zhǔn)數(shù)做交換，此時(shí)基準(zhǔn)數(shù)就找到了臨界點(diǎn)的位置k，位置k兩邊的數(shù)組都比當(dāng)前位置k上的基準(zhǔn)值或都更小或都更大。
• 上一次的基準(zhǔn)值7已經(jīng)把數(shù)組分為了兩半，基準(zhǔn)值7算是已歸位(找到排序后的位置)。
• 通過相同的排序思想，分別對(duì)7兩邊的數(shù)組進(jìn)行快速排序，左邊對(duì)[left, k-1]子數(shù)組排序，右邊則是[k+1, right]子數(shù)組排序。
• 利用遞歸算法，對(duì)分治后的子數(shù)組進(jìn)行排序。

快速排序的優(yōu)勢(shì)

快速排序之所以比較快，是因?yàn)橄啾让芭菖判?#xff0c;每次的交換都是跳躍式的，每次設(shè)置一個(gè)基準(zhǔn)值，將小于基準(zhǔn)值的都交換到左邊，大于基準(zhǔn)值的都交換到右邊，

這樣不會(huì)像冒泡一樣每次都只交換相鄰的兩個(gè)數(shù)，因此比較和交換的此數(shù)都變少了，速度自然更高。當(dāng)然，也有可能出現(xiàn)最壞的情況，就是仍可能相鄰的兩個(gè)數(shù)進(jìn)行交換。

快速排序基于分治思想，它的時(shí)間平均復(fù)雜度很容易計(jì)算得到為O(nlogn)。

實(shí)現(xiàn)代碼如下：

public static void quickSort(int[] array) { int len; if (array == null || (len = array.length) == 0 || len == 1) { return; } sort(array, 0, len - 1);}// 遞歸實(shí)現(xiàn)快速排序public static void sort(int[] array, int left, int right) { if (left > right) { return; } // base中存放基準(zhǔn)數(shù) int base = array[left]; int i = left, j = right; while (i != j) { // 順序很重要，先從右邊開始往左找，直到找到比base值小的數(shù) while (array[j] >= base && i < j) { j--; } // 再?gòu)淖笸疫呎?#xff0c;直到找到比base值大的數(shù) while (array[i] <= base && i < j) { i++; } // 上面的循環(huán)結(jié)束表示找到了位置或者(i>=j)了，交換兩個(gè)數(shù)在數(shù)組中的位置 if (i < j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } // 將基準(zhǔn)數(shù)放到中間的位置(基準(zhǔn)數(shù)歸位) array[left] = array[i]; array[i] = base; // 遞歸，繼續(xù)向基準(zhǔn)的左右兩邊執(zhí)行和上面同樣的操作 // i的索引處為上面已確定好的基準(zhǔn)值的位置，無(wú)需再處理 sort(array, left, i - 1); sort(array, i + 1, right);}

• JDK自帶排序

Arrays.sort(arr);

在JDK1.7之前，JDK中自帶的排序算法是經(jīng)典快排，但是在JDK1.7的時(shí)候，JDK中自帶的數(shù)組排序算法已經(jīng)換成了Dual-Pivot Quicksort(雙軸快速排序算法)，該算法的時(shí)間復(fù)雜度是O(nLogn)。

JDK1.8中的排序算法如下：

/** * 歸并排序中的最大運(yùn)行次數(shù) */private static final int MAX_RUN_COUNT = 67;/** * 歸并排序中運(yùn)行的最大長(zhǎng)度 */private static final int MAX_RUN_LENGTH = 33;/** * 如果要排序的數(shù)組長(zhǎng)度小于此常量，則使用快速排序優(yōu)先于合并排序。 */private static final int QUICKSORT_THRESHOLD = 286;static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) { // 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 // Implementation note: variable "right" is increased by 1. if (run[count] == right++) { // The last run contains one element run[++count] = right; } else if (count == 1) { // The array is already sorted return; } // Determine alternation base for merge byte odd = 0; for (int n = 1; (n <<= 1) < count; odd ^= 1) ; // Use or create temporary array b for merging int[] b; // temp array; alternates with a int ao, bo; // array offsets from 'left' int blen = right - left; // space needed for b if (work == null || workLen < blen || workBase + blen > work.length) { work = new int[blen]; workBase = 0; } if (odd == 0) { System.arraycopy(a, left, work, workBase, blen); b = a; bo = 0; a = work; ao = workBase - left; } else { b = work; ao = 0; bo = workBase - left; } // 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 + ao] <= a[q + ao]) { b[i + bo] = a[p++ + ao]; } else { b[i + bo] = a[q++ + ao]; } } run[++last] = hi; } if ((count & 1) != 0) { for (int i = right, lo = run[count - 1]; --i >= lo; b[i + bo] = a[i + ao]) ; run[++last] = right; } int[] t = a; a = b; b = t; int o = ao; ao = bo; bo = o; }}

有關(guān)Dual-Pivot Quicksort(雙軸快速排序算法)的講解可參考如下幾篇文章：

• https://blog.csdn.net/Holmofy/article/details/71168530
• https://www.jianshu.com/p/6d26d525bb96
• https://rerun.me/2013/06/13/quicksorting-3-way-and-dual-pivot/
• https://www.jianshu.com/p/2c6f79e8ce6e

數(shù)組反轉(zhuǎn)

public static void fanzhuan(int[] a) { for (int i = 0; i < a.length / 2; i++) { int tp = a[i]; a[i] = a[a.length - i - 1]; a[a.length - i - 1] = tp; }}

也可以將數(shù)組轉(zhuǎn)為ArrayList，然后調(diào)用Collections.reverse(arrayList);進(jìn)行反轉(zhuǎn)

查找

最笨的方法，就是從前往后一個(gè)個(gè)的查找，這種方式不到不得以，不要使用，太笨。

• 二分查找

二分查找的實(shí)現(xiàn)思路：

1. 定義查找的范圍，也就是開始索引(如 int start = 0)和結(jié)束索引(如 int end = srr.length - 1)。

2. 判斷 start 是否小于等于 end ，如果 start 大于 end，則結(jié)束查找，直接返回-1代表沒有找到所查找的元素。如果滿足條件，則計(jì)算出 start 和 end 之間的中間索引 middle ，并獲取該中間索引對(duì)應(yīng)的值 middleVal。

• int middle = (start + end)/2.
• int middleVal = arr(middle);

3. 把中間索引對(duì)應(yīng)的值 middleVal 和要查找的元素 key 進(jìn)行比較：

• 如果 middleVal 等于 key，就返回當(dāng)前的中間索引 middle;
• 如果 middleVal 大于 key:
• 對(duì)于升序數(shù)組：end = middle - 1;
• 對(duì)于降序數(shù)組：start = middle + 1;
• 如果 middleVal 小于 key:
• 對(duì)于升序數(shù)組：start = middle + 1;
• 對(duì)于降序數(shù)組：end = middle - 1;

4. 重新執(zhí)行第二步操作。

使用二分查找前，必須對(duì)數(shù)據(jù)進(jìn)行排序，如果未排序，則有可能找不到所查找的元素。如果數(shù)組包含多個(gè)指定值的元素，則不確定返回哪個(gè)位置上的該元素。

public static int binarySearch(int[] arr, int key) { // 在不斷縮小范圍的過程中，可以 // 返回-1則說(shuō)明找不到這個(gè)數(shù) // 定義起始、終點(diǎn)、中間索引，目標(biāo)key值索引 int start = 0; int end = arr.length - 1; // 在數(shù)組中找要找的數(shù)，因?yàn)椴灰欢〞?huì)一下子找到，所以這應(yīng)該是一個(gè)重復(fù)尋找的過程，即會(huì)用到循環(huán) while (start <= end) {// 看出start不斷增大，end不斷縮小；如果當(dāng)start和end相等時(shí)都還找不到，start會(huì)繼續(xù)增加，end繼續(xù)變小，此時(shí)這已經(jīng)不是一個(gè)正常的數(shù)組，結(jié)束循環(huán) int middle = (start + end) / 2; int value = arr[middle]; // 讓中間索引對(duì)應(yīng)的值value與要查找的值key進(jìn)行比較 if (key == value) { // 如果相等，即找到，則返回中間索引，并跳出循環(huán) return middle; } else if (key > value) { // key > value if (arr[0] < arr[1]) { // 升序 start = middle + 1; } else { // 降序 end = middle - 1; } } else { // key < value if (arr[0] < arr[1]) { // 升序：end = middle - 1 end = middle - 1; } else {// 降序：start = middle + 1 start = middle + 1; } } } // while括號(hào) return -1;}

• jdk自帶的二分查找

Arrays.binarySearch(arr, val);

public static int binarySearch(int[] a, int key) { return binarySearch0(a, 0, a.length, key);}......private static int binarySearch0(int[] a, int fromIndex, int toIndex, int key) { int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) >>> 1; int midVal = a[mid]; if (midVal < key) low = mid + 1; else if (midVal > key) high = mid - 1; else return mid; // key found } return -(low + 1); // key not found.}

數(shù)組操作工具類

public class GenericArray { private T[] data; private int size; // 根據(jù)傳入容量，構(gòu)造Array public GenericArray(int capacity) { data = (T[]) new Object[capacity]; size = 0; } // 無(wú)參構(gòu)造方法，默認(rèn)數(shù)組容量為10 public GenericArray() { this(10); } // 獲取數(shù)組容量 public int getCapacity() { return data.length; } // 獲取當(dāng)前元素個(gè)數(shù) public int count() { return size; } // 判斷數(shù)組是否為空 public boolean isEmpty() { return size == 0; } // 修改 index 位置的元素 public void set(int index, T e) { checkIndex(index); data[index] = e; } // 獲取對(duì)應(yīng) index 位置的元素 public T get(int index) { checkIndex(index); return data[index]; } // 查看數(shù)組是否包含元素e public boolean contains(T e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return true; } } return false; } // 獲取對(duì)應(yīng)元素的下標(biāo), 未找到，返回 -1 public int find(T e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return i; } } return -1; } // 在 index 位置，插入元素e, 時(shí)間復(fù)雜度 O(m+n) public void add(int index, T e) { checkIndex(index); // 如果當(dāng)前元素個(gè)數(shù)等于數(shù)組容量，則將數(shù)組擴(kuò)容為原來(lái)的2倍 if (size == data.length) { resize(2 * data.length); } for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = e; size++; } // 向數(shù)組頭插入元素 public void addFirst(T e) { add(0, e); } // 向數(shù)組尾插入元素 public void addLast(T e) { add(size, e); } // 刪除 index 位置的元素，并返回 public T remove(int index) { checkIndexForRemove(index); T ret = data[index]; for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; data[size] = null; // 縮容 if (size == data.length / 4 && data.length / 2 != 0) { resize(data.length / 2); } return ret; } // 刪除第一個(gè)元素 public T removeFirst() { return remove(0); } // 刪除末尾元素 public T removeLast() { return remove(size - 1); } // 從數(shù)組中刪除指定元素 public void removeElement(T e) { int index = find(e); if (index != -1) { remove(index); } } @Override public String toString() { StringBuilder builder = new StringBuilder(); builder.append(String.format("Array size = %d, capacity = %d

總結(jié)

以上是生活随笔為你收集整理的arrays中copyof复制两个数组_数据结构与算法（3）数组的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。