數(shù)組基本語法

定義：數(shù)組是相同類型的數(shù)據(jù)按順序組成的一種引用數(shù)據(jù)類型
作用：用于將相同數(shù)據(jù)類型的多項(xiàng)數(shù)據(jù)存儲在連續(xù)的存儲單元中

• 數(shù)組聲明
  語法：數(shù)組類型[] 數(shù)組名; 或數(shù)組類型 數(shù)組名[];
  例如：int[] myIntArray; int myIntArray[];
  數(shù)組名：是數(shù)組空間的引用，它指向了數(shù)組空間的首地址(第一個(gè)元素)

• 數(shù)組創(chuàng)建
  語法一：先聲明后創(chuàng)建

  數(shù)組類型[] 數(shù)組名;
  數(shù)組名 = new 數(shù)據(jù)類型[數(shù)組長度];
  例如：int[] arr; arr = new int[10]; //創(chuàng)建一個(gè)10個(gè)元素的數(shù)組對象，并把對象的引用賦給arr

  語法二：聲明的同時(shí)創(chuàng)建數(shù)組

  數(shù)組類型[] 數(shù)組名 = new 數(shù)據(jù)類型[數(shù)組長度];
  例如：int[] arr = new int[10];
  注意：創(chuàng)建數(shù)組時(shí)數(shù)組長度必須指定

• 數(shù)組元素初始值
  數(shù)組會被分配連續(xù)的內(nèi)存空間，且針對不同數(shù)據(jù)類型會賦予數(shù)組每個(gè)元素一個(gè)固定的初始值(默認(rèn)值)。

• 數(shù)組的初始化
  聲明數(shù)組的同時(shí)給數(shù)組賦值，叫做數(shù)組的初始化。數(shù)組的長度就是初始化時(shí)所給數(shù)組元素的個(gè)數(shù)。
  初始化方式：
  int[] arr = {1,2,3,4,5}; //靜態(tài)初始化，初始化長度為5的整型數(shù)組
  int[] arr = new int[]{1,2,3,4,5}; //用new聲明的同時(shí)初始化

• 數(shù)組元素的引用
  語法：數(shù)組名[下標(biāo)]; //下標(biāo)從0開始
  

  數(shù)組長度：屬性length表示數(shù)組的長度，如 a.length;

• 數(shù)組下標(biāo)越界
  數(shù)組下標(biāo)范圍為[0 - arr.length - 1]， 一旦操作不在這個(gè)范圍的下標(biāo)元素，則會拋出異常，異常為ArrayIndexOutOfBoundsException，表示數(shù)組下標(biāo)越界。

• 數(shù)組的訪問與賦值
  對于數(shù)組而言，使用循環(huán)遍歷即可依次訪問或者修改數(shù)組的每個(gè)元素

    //創(chuàng)建數(shù)組
    int[] intArray = new int[5];
    //循環(huán)為數(shù)組賦值
    for (int i = 0; i < intArray.length; i++) {
        intArray[i]  = i + 1;
    }
    //循環(huán)輸出數(shù)組中的元素：1 2 3 4 5
    for (int i = 0; i < intArray.length; i++) {
        System.out.print(intArray[i] + " ");
    }

數(shù)組基本算法

1. 數(shù)組求和
數(shù)組求和非遞歸方式實(shí)現(xiàn)

    // 初始化數(shù)組
    int[] intArray = { 1, 2, 3, 4, 5, 6 };
    int sum = 0;
    // 求和
    for(int i = 0; i < intArray.length; i++) {
        sum += intArray[i];
    }
    System.out.println("數(shù)組的和為：" + sum);

數(shù)組求和遞歸方式實(shí)現(xiàn)：
Sum( arr[0...n-1] ) = arr[0] + Sum( arr[1...n-1] ) --> 將問題轉(zhuǎn)換為更小的同一問題
Sum( arr[1...n-1] ) = arr[1] + Sum( arr[2...n-1] ) -->
遞歸邏輯：規(guī)律就是當(dāng)前數(shù)組的和等于第一個(gè)元素 + 從下一個(gè)索引開始新的數(shù)組的和
依此類推：
Sum( arr[n-1...n-1] ) = arr[n-1] + Sum( arr[] ) -->最基本的問題，遞歸出口

    public static int sum(int[] arr){
        return sum(arr, 0);
    }
    //計(jì)算arr[l...n)這個(gè)區(qū)間內(nèi)所有數(shù)字的和
    private static int sum(int[] arr, int l){
        if(l == arr.length){
            return 0;
        }
        //遞歸調(diào)用
        return arr[l] + sum(arr, l + 1);
    }
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7,8,9,10};
        System.out.println(sum(nums)); //55
    }

2. 數(shù)組最大最小值

    // 初始化數(shù)組
    int[] intArray = { 1, 2, 3, 4, 5, 6 };
    //最大最小值默認(rèn)為第一個(gè)元素
    int max = intArray[0];
    int min = intArray[0];
    for(int i = 0; i < intArray.length; i++) {
        // 總是將最小的元素值賦給min變量
        if (intArray[i] < min) {
            min = intArray[i];
        }
        // 總是將最大的元素值賦給max變量
        if (intArray[i] > max) {
            max = intArray[i];
        }
    }
    System.out.println("數(shù)組的最大值為：" + max); //6
    System.out.

3. 冒泡排序
對一組整數(shù)按照由小到大的順序進(jìn)行排序
原理：比較兩個(gè)相鄰的元素，將值大的元素交換至右端
思路：依次比較相鄰的兩個(gè)數(shù)，將小數(shù)放在前面，大數(shù)放在后面。對于第一趟需要比較到最后兩個(gè)元素，此時(shí)數(shù)組最后一個(gè)數(shù)一定是最大值，第二趟就不需要比較最后一個(gè)數(shù)了，從第一個(gè)數(shù)比較到倒數(shù)第二個(gè)數(shù)，第二趟結(jié)束第二大的數(shù)就確定了，依此類推，每次比較次數(shù)-1，直到最后比較次數(shù)為1，整個(gè)數(shù)組就從小到大排序好了。
結(jié)論：對于N個(gè)元素的數(shù)組要排序完成，總共進(jìn)行N-1趟排序，每i趟的排序次數(shù)為(N-i)次，可以用雙重循環(huán)語句，外層控制循環(huán)多少趟，內(nèi)層控制每一趟的循環(huán)比較次數(shù)。
圖示：

實(shí)現(xiàn)：

//冒泡排序
private static void sort(int[] arr) {
    //外層循環(huán)控制排序趟數(shù)
    for (int i = 0; i < arr.length-1; i++) {
        //內(nèi)層循環(huán)控制每一趟排序多少次
        for (int j = 0; j < arr.length-1-i; j++) {
            //如果按照從小到大的順序，則需要前邊的數(shù)比后邊的數(shù)小
            if(arr[j]>arr[j+1]) {
                //交換值
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
public static void main(String[] args) {
    // 初始化數(shù)組
    int[] arr = { 34, 53, 12, 32, 56, 17 };
    sort(arr); //排序
    //[12, 17, 32, 34, 53, 56]
    System.out.println(Arrays.toString(arr)); //調(diào)用工具類打印數(shù)組
}

4. 選擇排序(簡單選擇排序)
原理：每一趟從待排序的記錄中選出最小的元素，順序放在已排好序的序列最后，直到全部記錄排序完畢。
區(qū)別：冒泡排序是相鄰的兩個(gè)元素進(jìn)行比較和交換，而選擇排序則是選取一個(gè)元素與其他所有元素進(jìn)行比較和交換。
思想：給定數(shù)組：int[] arr={里面n個(gè)數(shù)據(jù)}; 第1趟排序，在待排序數(shù)據(jù)arr[1]～arr[n]中選出最小的數(shù)據(jù)，將它與arr[1]交換；第2趟，在待排序數(shù)據(jù)arr[2]～arr[n]中選出最小的數(shù)據(jù)，將它與arr[2]交換;以此類推，第i趟在待排序數(shù)據(jù)arr[i]～arr[n]中選出最小的數(shù)據(jù)，將它與arr[i]交換，直到全部排序完成。
實(shí)現(xiàn)：

//選擇排序
private static void sort(int[] arr) {
    //外層循環(huán)代表輪數(shù)，代表正在比較第幾小的數(shù)
    for(int i=0; i<arr.length-1;  i++){
        //比較這一個(gè)數(shù)出來，需要比較多少次
        for(int j=i+1; j<arr.length; j++){
            //如果按照從小到大的順序，則需要前邊的數(shù)比后邊的數(shù)小
            if(arr[i]>arr[j]){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}
public static void main(String[] args) {
    // 初始化數(shù)組
    int[] arr = { 34, 53, 12, 32, 56, 17 };
    sort(arr); //排序
    //[12, 17, 32, 34, 53, 56]
    System.out.println(Arrays.toString(arr)); //調(diào)用工具類打印數(shù)組
}

優(yōu)化：上述代碼是每次排序都需要和其他元素進(jìn)行比較并且滿足條件則交換，那么其實(shí)我們只需要找出其他元素中最小的值并記錄它的索引，之后將該索引對應(yīng)的元素與當(dāng)前選擇的元素進(jìn)行比較和交換判斷即可。避免了過多的交換操作。

    private static void sort(int[] arr) {
        for(int i=0; i<arr.length-1;  i++){
            //k用來記錄其他元素中最小值的索引
            int k = i; 
            for(int j=i+1; j<arr.length; j++){
                if(arr[k] > arr[j]){
                    k = j;
                }
            }
            //在內(nèi)層循環(huán)結(jié)束，也就是找到本輪循環(huán)的最小的數(shù)以后，再進(jìn)行交換
            if(k != i){
                int temp = arr[k];
                arr[k] = arr[i];
                arr[i] = temp;
            }
        }
    }