尚硅谷Java第 4、5 章IDEA，數組

第 4 章：IDEA的使用

第 5 章：數組

5.1 數組的概述

數組(Array)：就可以理解為多個數據的組合。

程序中的容器：數組、集合框架（List、Set、Map）。

數組中的概念：

數組名
下標（或索引）
元素
數組的長度

數組存儲的數據的特點：

依次緊密排列的、有序的、可以重復的。
數組的其它特點：
- 一旦初始化，其長度就是確定的、不可更改的。
- 數組的下標是從0開始的

5.2 一維數組

5.2.1 數組的聲明和初始化

代碼示例：

?int[] arr1 = new int[10];String[] arr2 = new String[]{"Tom","Jerry"};

5.2.2 數組的使用

調用數組的指定元素：使用角標、索引、index。
index 從 0 開始。
數組的屬性：length，表示數組的長度。
數組的遍歷。
數組元素的默認初始化值。

5.2.3 一維數組內存分析

虛擬機棧：main() 作為一個棧幀，壓入棧空間中。在 main() 棧幀中，存儲著 arr 變量。arr 記錄著數組實體的首地址值。
堆：數組實體存儲在堆空間中。
Java 虛擬機的內存劃分：

5.3 二維數組

二維數組本質上是元素類型是一維數組的一維數組。

5.4 數組的常用算法

數值型數組的特征值的計算：最大值、最小值、總和、平均值等。
數組元素的賦值。
數組的復制、賦值。
數組的反轉。
數組的擴容、縮容。
數組的查找：
- 線性查找。
- 二分法查找（前提：數組有序）。
數組的排序：
- 冒泡排序（最簡單）。
- 快速排序（最常用）。

5.5 Arrays 工具類的使用

java.util.Arrays 類即為操作數組的工具類，包含了用來操作數組（比如排序和搜索）的各種方法。
toString() 、 sort()、 binarySearch()。

5.6 數組中的常見異常

下標越界異常：ArrayIndexOutOfBoundsException
空指針異常：NullPointerException

5.7、企業真題

數組有沒有 length()這個方法? String 有沒有 length()這個方法？答：數組沒有 length()，有 length 屬性。 String 有 length()。

有數組 int[] arr，用 Java 代碼將數組元素順序顛倒？答：可以使用兩個指針，一個指向數組的第一個元素，另一個指向數組的最后一個元素，交換它們的值，然后繼續向中間靠攏，直到兩個指針相遇。

?public static void reverseArray(int[] arr){int left = 0;int right = arr.length - 1;?while (left < right){int temp = arr[left];?arr[left] = arr[right];arr[right] = temp;left++;right--;}}?public static void main(String[] args){int[] arr = {1, 2, 3, 4, 5}; ? ?// 定義一個數組?System.out.println("原數組：" + Arrays.toString(arr)); ? ?// 輸出原數組reverseArray(arr); ? ?// 調用方法將數組元素順序顛倒System.out.println("顛倒后的數組：" + Arrays.toString(arr)); ? ?// 輸出顛倒后的數組}

運行該主函數，輸出結果如下：

?原數組：[1, 2, 3, 4, 5]顛倒后的數組：[5, 4, 3, 2, 1]

為什么數組要從 0 開始編號，而不是 1？答：數組的索引，表示了數組元素距離首地址的偏離量。因為第 1 個元素的地址與首地址相同，所以偏移量就是 0，所以數組要從 0 開始。
數組有什么排序的方式，手寫一下？答：常見的數組排序方式有冒泡排序、選擇排序、插入排序、快速排序、歸并排序等。

冒泡排序：冒泡排序的思路是從第一個元素開始，依次比較相鄰的兩個元素，如果前一個元素比后一個元素大，則交換它們的位置。這樣一輪下來，最大的元素就會被移動到最后一個位置。然后再從第一個元素開始，繼續進行比較和交換，直到所有元素都被排序。
```
?public class BubbleSort{public static void main(String[] args){int[] arr = {3, 9, 1, 8, 2, 5, 7};?bubbleSort(arr);?for(int i = 0; i < arr.length; i++){System.out.print(arr[i] + " ");}}?public static void bubbleSort(int[] arr){int n = arr.length;?for(int i = 0; i < n - 1; i++){for(int j = 0; j < n - i - 1; j++){if(arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}}
```
冒泡排序的時間復雜度為 O(n^2)，空間復雜度為 O(1)。

快速排序：快速排序的思路是選取一個基準元素，將數組分為左右兩部分，左半部分的元素均小于等于基準元素，右半部分的元素均大于等于基準元素。然后對左右兩部分分別進行快速排序，直到整個數組有序。在上面的代碼中，partition 方法用于實現分區，將數組分為左右兩部分。quickSort 方法用于實現快速排序，遞歸調用自身對左右兩部分進行排序。
```
?public class QuickSort{public static void main(String[] args){int[] arr = {5, 2, 9, 3, 7, 6, 1, 8, 4};?quickSort(arr, 0, arr.length - 1);?for (int i : arr){System.out.print(i + " ");}}?public static void quickSort(int[] arr, int left, int right){if (left < right){int pivot = partition(arr, left, right);?quickSort(arr, left, pivot - 1);quickSort(arr, pivot + 1, right);}}?public static int partition(int[] arr, int left, int right){int pivot = arr[left];?while (left < right){while (left < right && arr[right] >= pivot){right--;}?arr[left] = arr[right];?while (left < right && arr[left] <= pivot){left++;}?arr[right] = arr[left];}?arr[left] = pivot;?return left;}}
```
快速排序的時間復雜度為 O(nlogn)，空間復雜度為 O(logn)。
二分算法實現數組的查找？答：二分查找思路： ① 首先確定要查找的數組的范圍，即左右邊界； ② 計算中間位置，即中間索引值； ③ 判斷中間值是否等于要查找的值，如果是，則返回中間索引值； ④ 如果中間值大于要查找的值，則在左半部分繼續查找，即將右邊界設為中間索引值減一； ⑤ 如果中間值小于要查找的值，則在右半部分繼續查找，即將左邊界設為中間索引值加一； ⑥ 重復 ②-⑤ 步驟，直到找到要查找的值或左右邊界重合，此時返回-1 表示未找到。
```
?public class BinarySearch{public static int binarySearch(int[] arr, int key){int low = 0;int high = arr.length - 1;?while (low <= high){int mid = (low + high) / 2;?if (key < arr[mid]){high = mid - 1;}else if (key > arr[mid]){low = mid + 1;}else{return mid;}}?return -1;}?public static void main(String[] args){int[] arr = {1, 3, 5, 7, 9};int key = 3;int index = binarySearch(arr, key);?if (index == -1){System.out.println("找不到指定的元素");}else{System.out.println("指定元素的索引為：" + index);}}}
```
復雜度分析：時間復雜度為 O(log n)，因為每次查找都將查找范圍縮小一半，最壞情況下需要查找 log n 次，其中 n 為數組長度。空間復雜度為 O(1)，因為只需要常數個額外變量存儲查找范圍的左右邊界和中間索引值。
怎么求數組的最大子序列和? 答：以下是一個使用 Java 實現的求解最大子序列和的示例代碼：

這個算法的思路是使用動態規劃的思想。

我們從左到右遍歷整個數組，使用兩個變量 maxSum 和 currentSum 來記錄最大子序列和和當前子序列和。

對于當前遍歷到的元素 nums[i]，我們可以有兩種選擇：將 nums[i] 加入當前子序列中，即 currentSum = currentSum + nums[i]；以 nums[i] 作為新的起點開始一個新的子序列，即 currentSum = nums[i]。

我們需要比較這兩種選擇哪個更優，即選擇 currentSum + nums[i] 或選擇 nums[i] 中的較大值作為當前子序列的和 currentSum。同時，我們需要比較當前子序列的和 currentSum 和最大子序列和 maxSum 哪個更大，即選擇 Math.max(maxSum, currentSum)作為新的最大子序列和 maxSum。

最后，遍歷完成后 maxSum 就是最大子序列和。
```
?public class MaxSubArraySum{public static int maxSubArraySum(int[] nums){int maxSum = nums[0];int currentSum = nums[0];?for (int i = 1; i < nums.length; i++){currentSum = Math.max(currentSum + nums[i], nums[i]);maxSum = Math.max(maxSum, currentSum);}?return maxSum;}?public static void main(String[] args){int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};int maxSum = maxSubArraySum(nums);?System.out.println("最大子序列和為：" + maxSum);}}
```
輸出：
```
?最大子序列和為：6
```
解釋：最大子序列為[4, -1, 2, 1]，和為 6。
Arrays 類的排序方法是什么？如何實現排序的？答： Arrays 類提供了多種排序方法，包括： ① sort(Object[] a)：對數組 a 進行升序排序，元素類型必須實現 Comparable 接口。 ② sort(Object[] a, Comparator c)：對數組 a 進行排序，使用自定義的 Comparator 比較器進行比較。 ③ parallelSort(Object[] a)：對數組 a 進行并行排序，效率更高。

排序的實現原理主要是基于快速排序和歸并排序，具體實現方式根據元素類型和排序方法不同而不同。

在 sort(Object[] a) 方法中，對于實現了 Comparable 接口的元素類型，通過 compareTo() 方法進行比較，并且使用快速排序實現；對于未實現 Comparable 接口的元素類型，則會拋出 ClassCastException 異常。

在 sort(Object[] a, Comparator c) 方法中，通過傳入自定義的 Comparator 比較器進行比較，也使用快速排序實現。在 parallelSort(Object[] a) 方法中，使用 Fork/Join 框架實現并行排序，將數組拆分成多個小數組進行排序，最后再合并起來。