摘要：知識體系梳理流程圖一維數組數組概述數組是指一組數據的集合，數組中的每個數據被稱作元素。定義打印數組元素方法按照給定的格式打印題目分析通過觀察發現，要實現按照指定格式，打印數組元素操作。按照這種方式，數組循環多圈以后，就完成了數組元素的排序。

數組是指一組數據的集合，數組中的每個數據被稱作元素。在數組中可以存放任意類型的元素，但同一個數組里存放的元素類型必須一致。

數組的好處

可以自動給數組中的元素從0開始編號，方便操作這些元素。

在java中，可以使用以下2種格式來定義一維數組。

定義的格式1

在定義數組時只指定數組的長度，由系統自動為元素賦初值的方式稱作動態初始化。

元素類型[] 數組名 = new 元素類型[元素個數或者數組長度];
int[] arr = new int[3];

上述語句就相當于在內存中定義了3個int類型的變量，第一個變量的名稱為arr[0]，第二個變量的名稱為arr[1]，以此類推，第三個變量的名稱為arr[2]，這些變量的初始值都是0。為了更好地理解數組的這種定義方式，可以將上面的一句代碼分成兩句來寫，具體如下:

int[] arr; // 聲明一個int[]類型的變量
arr = new int[3]; // 創建一個長度為3的數組

定義的格式2

在定義數組的同時就為數組的每個元素賦值稱為靜態初始化。

元素類型[] 數組名 = new 元素類型[]{元素1, 元素2, 元素3, ......};

  int[] arr = new int[]{3, 5, 1} or
  int[] arr = {3, 5, 1};

需要注意，以下寫法是錯誤的：int[] arr = new int[4]{3, 5, 1}; 因為編譯器會認為數組限定的元素個數[4]與實際存儲的元素{3, 5, 1}個數有可能不一致，存在一定的安全隱患。

內存結構簡介

Java程序在運行時，需要在內存中的分配空間。為了提高運算效率，有對空間進行了不同區域的劃分，因為每一片區域都有特定的處理數據方式和內存管理方式。

JVM對內存劃分5個區域

寄存器

本地方法區

方法區

運行時存放class文件

棧內存

用于存取局部變量，當局部變量的作用域一旦結束，所占的內存空間就會自動釋放。

堆內存

數組和對象，通過new創建的實例都存放在堆內存中；

每一個實體都有內存地址值；

堆內存中每一個變量都有默認的初始化值，根據元素類型的不同，默認初始化的值也是不一樣的，具體如下表所示：

實體不在使用時，會在不確定的時間內被垃圾回收器回收

數組內存結構

內存圖

通過上面內存圖來詳細的說明數組在創建過程中內存的分配情況。

第一行代碼 int[] arr; 聲明一個變量arr, 該變量的數據類型為int[]，即一個int類型的數組。變量arr會在棧內存中占用一塊內存單元，它沒有被分配初始化值。

第二行代碼 arr = new int[3];會在堆內存中分配一塊內存單元，數組首地址為0x7852e922，數組中每一個元素初始化值為0，并將首地址賦值給變量arr，在程序運行的過程中可以使用變量arr來引用數組。

length屬性獲取數組的長度

我們可以通過數組名.length的方式來獲取數組的長度，即數組中元素的個數

通過索引訪問數組中的元素

數組中的每一個元素都有一個索引(也可稱為角標)，想要訪問數組中的元素可以通過arr[索引]形式，值得注意的是：數組中最小的索引是0，最大的索引是數組的長度-1。

public class ArrayDemo{    
   public static void main(String[] args){        
   int[] arr = new int[3]; //創建一個長度為3的數組
   System.out.println("arr[0] = " + arr[0]); // 訪問數組中第一個元素
   System.out.println("arr[1] = " + arr[1]); // 訪問數組中第二個元素
   System.out.println("arr[2] = " + arr[2]); // 訪問數組中第三個元素
   System.out.println("數組的長度length = " + arr.length); // 獲取數組的長度
   }
  }

運行結果如下圖：

從打印結果可以看出，數組中的三個元素初始值都為0，這是因為當數組被成功創建后，數組中元素會被自動賦予一個默認值，根據元素類型的不同，默認初始化的值也是不一樣的。

為數組中的元素賦值

如果在使用數組時，不想使用這些默認初始值，也可以顯式地為這些元素賦值。

public class ArrayDemo{    
    public static void main(String[] args){        
        int[] arr = new int[4]; //創建一個長度為4的int類型數組
        arr[0] = 3; // 為第一個元素賦值為3
        arr[1] =  5; // 為第二個元素賦值為5
         System.out.println("arr[0] = " + arr[0]); // 訪問數組中第一個元素
        System.out.println("arr[1] = " + arr[1]); // 訪問數組中第二個元素
        System.out.println("arr[2] = " + arr[2]); // 訪問數組中第三個元素
        System.out.println("arr[3] = " + arr[3]); // 訪問數組中第三個元素
        System.out.println("數組的長度length = " + arr.length); // 獲取數組的長度
    }
}

運行結果如下圖:

在上述代碼中，定義一個長度為4的int類型數組，此時數組中每個元素都為默認初始值0。通過賦值語句將數組中的元素arr[0]和arr[1]分別賦值為3和5，而元素arr[2]和arr[3]沒有賦值，其值仍為0，因此打印結果中四個元素的值依次為3、5、0、0。

數組遍歷
在操作數組時，經常需要依次訪問數組中的每個元素，這種操作稱作數組的遍歷。接下來通過一個案例來學習如何使用for循環來遍歷數組。如下所示。ArrayDemo02.java

public class ArrayDemo02{
   public static void main(String[] args){
       int[] arr = new int[]{3, 6, 9, 5, 1}; // 創建一個數組
       // 使用for循環遍歷數組中每一個元素
       for(int index = 0; index < arr.length; index++){
           // 通過索引（角標）來訪問數組中的元素
           System.out.print("arr["+ index +"]" + arr[index] + ", ");
       }
   }
}

運行結果如下圖所示：

上述代碼中，定義一個長度為5的數組arr，數組的角標為0~4。由于for循環中定義的變量index的值在循環過程中為0~4，因此可以作為索引，依次去訪問數組中的元素，并將元素的值打印出來。

數組索引越界異常
每個數組的索引都有一個范圍，即0~length-1。在訪問數組的元素時，索引不能超出這個范圍，否則程序會報ArrayIndexOutOfBoundsException，如下所示。ArrayDemo03.java

public class ArrayDemo03{
    public static void main(String[] args){
        int[] arr = new int[]{3, 6, 9, 5, 1};
        System.out.println(arr[5]);         
    }
}

運行結果如下：

上圖運行結果中所提示的錯誤信息是數組角標越界異常ArrayIndexOutOfBoundsException，出現這個異常的原因是數組的長度為5，其索引范圍為0~4。

空指針異常
在使用變量引用一個數組時，變量必須指向一個有效的數組對象，如果該變量的值為null，則意味著沒有指向任何數組，此時通過該變量訪問數組中的元素會出現空指針異常NullPointerException。接下來通過一個案例來演示這種異常，如下所示。ArrayDemo04.java

public class ArrayDemo04{
  public static void main(String[] args){        
      int[] arr = new int[3]; // 創建一個長度為3的int類型數組
      arr[0] = 23; // 給數組中的第一個元素賦值為23
      System.out.println("arr[0] = " + arr[0]); // 訪問數組中第一個元素
      arr = null; // 將變量arr置位null
      System.out.println("arr[0] = " + arr[0]); // 訪問數組中第一個元素
  }
}

運行的結果如下圖：

通過上圖所示的運行結果可以看出，代碼中將變量arr置為null，再次次訪問數組時就出現了空指針異常NullPointerException。

獲取最值
在操作數組時，經常需要獲取數組中元素的最值(最大值或者最小值)。

    // int[] arr = {5,1,12,4,6,8,0,3};
    // 第一種寫法
    public static int getMax(int[] arr){
        if(arr == null)
            return -1;
         // 定義一個變量記錄最大的值，默認數組中第一個元素
        int maxElement = arr[0];
        for(int index = 1; index < arr.length; index++){
            // 如果arr[index]大于maxElement
            if(arr[index] > maxElement)
                maxElement = arr[index]; //條件成立, 將arr[index]賦值給maxElement
        }
        return maxElement;
    }
    
    // 第二種寫法
    public static int getMax_2(int[] arr){
        if(arr == null)
            return -1;
        // 定義一個變量記錄索引值，默認數組中第一個索引0
        int maxIndex = 0;
        for(int index = 1; index < arr.length; index++){
            // 如果arr[index]大于arr[maxElement]
            if(arr[index] > arr[maxIndex])
                maxIndex = index;//條件成立, 將index賦值給maxIndex
        }        
        return arr[maxIndex];
    }

運行結果：maxElement = 12
上述代碼中，定義一個臨時變量maxElement用于記錄最大值，通過for循環遍歷數組中的每一個元素arr[index]與maxElement比較獲取最大值，并賦值給maxElement。
首先假設數組中第一個元素arr[0]為最大值，使用for循環對數組進行遍歷，在遍歷的過程中只要遇到比maxElement還要大的元素，就講該元素賦值給maxElement，變量maxElement就能夠在for循環結束時記錄數組中的最大值。值得注意的是，在for循環中的變量index是從1開始的，這樣寫的原因是程序已經假設數組中第一個元素為最大值，for循環中只需要從數組中第二個元素開始遍歷，從而可以提高程序的運行效率。

定義打印數組元素方法,按照給定的格式打印[11, 33, 44, 22, 55]

題目分析：通過觀察發現，要實現按照指定格式，打印數組元素操作。

通過循環，我們可以完成數組中元素的獲取，數組名[索引]

觀察發現，每個數組元素之間加入了一個逗號”,”進行分隔；并且，整個數組的前后有一對中括號”[]”包裹數組所有元素。

解題步驟

使用輸出語句完成打印 左邊的中括號”[”

使用循環，輸出數組元素值。輸出元素值分為兩種情況，如下：

最后一個數組元素，加上一個右邊的中括號”]”

非最后一個數組元素，加上一個逗號”,”

//按照指定的格式打印數組
public static void toArray(int[] arr){
        System.out.print("[");
        for(int index = 0; index < arr.length; index++){
            if(index == arr.length - 1)
                System.out.print(arr[index] + "]");
            else
                System.out.print(arr[index] + ", ");
        }
    }

數組元素的逆序

圖解

題目分析:通過觀察發現，要實現原數組元素倒序存放操作。即原數組存儲元素為{23,34,45,56,67,78,89}，逆序后為原數組存儲元素變為{89,78,67,56,45,34,23}。

通過圖解發現，想完成數組元素逆序，其實就是把數組中索引為start與end的元素進行互換；

每次互換后，start索引位置后移，end索引位置前移，再進行互換；

直到start位置超越了end位置，互換結束，此時，數組元素逆序完成。

解題步驟

定義兩個索引變量start值為0，變量end值為數組長度減去1（即數組最后一個元素索引）；

使用循環，完成數組索引start位置元素與end位置元素值互換；

在循環換過程中，每次互換結束后，start位置后移1，end位置前移1；

在循環換過程中，最先判斷start位置是否超越了end位置，若已超越，則跳出循環

    // 數組元素的逆序
    public static void reverseArray(int[] arr){
        for(int start = 0, end = arr.length - 1; start < end; start++, end--){
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
    }

數組元素選擇排序

圖解

題目分析：通過觀察發現，要實現把數組元素{13,46,22,65,3}進行排序。

提到數組排序，就要進行元素值大小的比較，通過上圖發現，我們想完成排序要經過若干次的比較才能夠完成；

上圖中用每圈要比較的第一個元素與該元素后面的數組元素依次比較到數組的最后一個元素，把小的值放在第一個數組元素中，數組循環一圈后，則把最小元素值互換到了第一個元素中；

3數組再循環一圈后，把第二小的元素值互換到了第二個元素中。按照這種方式，數組循環多圈以后，就完成了數組元素的排序。這種排序方式我們稱為選擇排序。

解題步驟

使用for循環（外層循環），指定數組要循環的圈數（通過圖解可知，數組循環的圈數為數組長度 - 1）；

在每一圈中，通過for循環（內層循環）完成數組要比較的第一個元素與該元素后面的數組元素依次比較到數組的最后一個元素，把小的值放在第一個數組元素中；

在每一圈中，要參與比較的第一個元素由第幾圈循環來決定。如上圖所示

進行第一圈元素比較時，要比較的第一個元素為數組第一個元素，即索引為0的元素；

進行第二圈元素比較時，要比較的第一個元素為數組第二個元素，即索引為1的元素；

依次類推，得出結論：進行第n圈元素比較時，要比較的第一個元素為數組第n個元素，即數組索引為n-1的元素

// 選擇排序
    public static void selectSort(int[] arr){
        // 外層for循環控制數組循環的次數
        for(int i = 0; i < arr.length - 1; i++){
            // 內層for循環用來比較元素值，將較小的值轉換到要比較的第一個元素中
            for(int j = i+1; j < arr.length; j++){
                if(arr[i] > arr[j]){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }
    
    // 這種方式可以減置換的次數，提高程序的性能
    public static void selectSort_2(int[] arr){
        for(int i = 0; i < arr.length - 1; i++){
            // 定義變量index和element分別記錄要比較的第一個元素的索引和值
            int index = i;
            int element = arr[i];
            for(int j = i + 1; j < arr.length; j++){
                // 比較獲取最小值的索引和值
                if(element > arr[j]){
                    index = j;
                    element = arr[j];
                }
            }
            // 當第一個要比較的元素索引不等于最小值的索引置換位置
            if(index != i){
                int temp = arr[i];
                arr[i] = arr[index];
                arr[index] = temp;
            }
        }
    }

數組元素冒泡排序

圖解

題目分析：通過觀察發現，要實現把數組元素{13,46,22,65,3}進行排序

提到數組排序，就要進行元素值大小的比較，通過上圖發現，我們想完成排序要經過若干次的比較才能夠完成；

上圖中相鄰的元素值依次比較，把大的值放后面的元素中，數組循環一圈后，則把最大元素值互換到了最后一個元素中。數組再循環一圈后，把第二大的元素值互換到了倒數第二個元素中。按照這種方式，數組循環多圈以后，就完成了數組元素的排序。這種排序方式我們稱為冒泡排序。

解題步驟

使用for循環（外層循環），指定數組要循環的圈數（通過圖解可知，數組循環的圈數為數組長度 - 1）；

在每一圈中，通過for循環（內層循環）完成相鄰的元素值依次比較，把大的值放后面的元素中；

每圈內層循環的次數，由第幾圈循環來決定。如上圖所示

進行第一圈元素比較時，內層循環次數為數組長度 - 1；

進行第二圈元素比較時，內層循環次數為數組長度 - 2；

依次類推，得出結論：進行第n圈元素比較時，內層循環次數為數組長度 - n

    // 冒泡排序
        public static void bubbleSort(int[] arr){
            // 外層for循環控制數組循環的次數
            for(int i = 0; i < arr.length - 1; i ++){
                // arr.length - 1 為了避免角標越界
                // arr.length - 1 - i 為了比較效率，減少重復比較
                // 內層for循環用來比較元素值，把大的元素置換到后面
                for(int j = 0; j < arr.length - 1 - i; j++){
                    if(arr[j] > arr[j+1]){
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                    }
                }
            }
        }

數組元素普通查找

圖解

題目分析：通過觀察發現，要實現查找指定數值第一次在數組中存儲的位置（索引），返回該位置（索引）

我們可以通過遍歷數組，得到每個數組元素的值；

在遍歷數組過程中，使用當前數組元素值與要查找的數值進行對比

數值相等，返回當前數組元素值的索引；

整個循環結束后，比對結果數值沒有相等的情況，說明該數組中沒有存儲要查找的數值，此時，返回一個索引值-1，來表示沒有查詢到對應的位置。（使用 -1來表示沒有查詢到，是因為數組的索引沒有負數）。

解題步驟

使用for循環，遍歷數組，得到每個數組元素值；

在每次循環中，使用if條件語句進行當前數組元素值與要查找的數值進行對比，若比較結果相等，直接返回當前數組元素的索引值；

若整個循環結束后，比對結果數值沒有相等的情況，說明該數組中沒有存儲要查找的數值，此時，返回一個索引值-1

// 普通查找
    public static int getArrayIndex(int[] arr, int key){
        // 把數組中的元素依次與指定的值比較
        for(int i = 0; i < arr.length - 1; i++){
            // 如果相等，找到了直接返回
            if(key == arr[i])
                return i;
        }
        return -1;
    }

數組元素二分查找(折半查找)

圖解

題目分析：通過觀察發現，要實現查找指定數值在元素有序的數組中存儲的位置（索引），返回該位置（索引）。

我們使用數組最中間位置的元素值與要查找的指定數值進行比較，若相等，返回中間元素值的索引

最中間位置的元素值與要查找的指定數值進行比較，若不相等，則根據比較的結果，縮小查詢范圍為上次數組查詢范圍的一半；再根據新的查詢范圍，更新最中間元素位置，然后使用中間元素值與要查找的指定數值進行比較。

比較結果相等，返回中間元素值的索引

比較結果不相等，繼續縮小查詢范圍為上次數組查詢范圍的一半，更新最中間元素位置，繼續比較，依次類推。

當查詢范圍縮小到小于0個元素時，則指定數值沒有查詢到，返回索引值-1。

解題步驟

定義3個用來記錄索引值的變量，變量min記錄當前范圍最小索引值，初始值為0；變量max記錄當前范圍最大索引值，初始值為數組長度-1；變量mid記錄當前當前范圍最中間元素的索引值，初始值為(min+max) / 2；

使用循環，判斷當前范圍下，最中間元素值與指定查找的數值是否相等

若相等，結束循環，返回當前范圍最中間元素的索引值mid；

若不相等，根據比較結果，縮小查詢范圍為上一次查詢范圍的一般

中間元素值 比 要查詢的數值大，說明要查詢的數值在當前范圍的最小索引位置與中間索引位置之間，此時，更新查詢范圍為:范圍最大索引值 = 上一次中間索引位置 -1；

中間元素值 比 要查詢的數值小，說明要查詢的數值在當前范圍的最大索引位置與中間索引位置之間，此時，更新查詢范圍為:范圍最小索引值 = 上一次中間索引位置 +1；

在新的查詢范圍中，更新中間元素值的位置，再次使用最中間元素值與指定查找的數值是否相等，中間索引值 = (范圍最小索引值 +范圍最大索引值) / 2;

每次查詢范圍縮小一半后，使用if語句判斷，查詢范圍是否小于0個元素，若小于0個元素，則說明指定數值沒有查詢到，返回索引值-1

public static int binarySearch(int[] arr, int key){
        // 定義三個變量分別記錄最小、最大和中間索引
        int min, max , mid;
        min = 0;
        max = arr.length - 1;
        while(min <= max){
            mid = (min + max) >>> 2;
            
            if(arr[mid] < key)
                min = mid + 1; // 在右邊
            else if(arr[mid] > key)
                max = mid - 1; // 在左邊
            else
                return mid;    // 找到了    
        }
        // 沒有找到
        return -(min + 1);
    }

定義的格式1

int[][] arr = new int[3][4];

上面的代碼相當于定義了一個3*4的二維數組，即二維數組的長度為3，二維數組中的每個元素又是一個長度為4的一維數組，接下來通過一個圖來表示這種情況，如下圖所示：

定義的格式2

int[][] arr = new int[3][];

二維數組中有3個一維數組，每個一維數組都有默認的初始化值為null，可以對這個三個一維數組分別進行初始化，接下來通過一個圖來表示這種情況，如下圖所示：

定義的格式3

int[][] arr = {{1,2},{3,4,5,6},{7,8,9}};

定義一個名稱為arr的二維數組，二維數組中有3個一維數組，每一個一維數組中具體元素都已初始化，接下來通過一個圖來表示這種情況，如圖所示

對二維數組中元素的訪問也是通過角標的方式，如需訪問二維數組中第一個元素數組的第二個元素，具體代碼如下：arr[0][1]

獲取arr數組中所有元素的和。使用for的嵌套循環即可。

int sum = 0;
int[][] arr = {{1,2},{3,4,5,6},{7,8,9}};  
for(int i =0; i < arr.length; i++){
for(int j=0; j< arr[i].length; j++){
    sum += arr[i][j];
}
}