1.數組基礎

1.什么是數組：

          同一類型數據的集合，就是一個容器。

2.數組的好處：

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

3.格式：  (一旦創建，必須明確長度)

         格式1：

             元素類型   [ ]  數組名  =  new  元素類型  [元素個數即數組的長度]；

             示例：int[] array = new int[5];

         格式2：

             元素類型 [ ]  數組名 =  new 元素類型 [ ]{元素1，元素2…}；

             示例：int[] array = new int[]{1,2,3,4,5};

                       int[] array = {1,2,3,4,5};

數組有默認值：（不用初始化也可以使用，因為數組new int[5]是堆內存中的實例，堆內存中的實例都有默認的初始值）

如int[] array = new int[5];

System.out.PRitln(array[0]);        

結果為0。

常見錯誤：

1.數組下標越界異常

int[] arr = new int[3];System.out.println(arr[3]);

說明：編譯不會報錯，運行時報錯。ArrayIndexOutOfBoundsException

          當訪問數組中不存在的下標時，就會報此異常。

2.空指針異常

int [] arr = new int[3];arr = null;System.ou.println(arr[0]);

說明：同樣編譯不會報錯，運行時報錯。NullPointeException

         空指針異常，當引用型變量沒有任何實體指向時，如果訪問該變量，就會報此異常。

 

2.數組的常見操作

1.遍歷

打印數組中的所有元素

int[] arr = {43,6,645,43,3,2,1,54};for (int i=0; i<arr.length; i++) {    System.out.print("arr["+i+"]:"+arr[i]+";");}

2.獲取最值

獲取最大值

public int getMax(int[] arr){    int max = arr[0];//記錄元素值    for (int i = 1; i<arr.length; i++) {        if(arr[i]>max){            max = arr[i];        }    }    return max;}

 

public static int getMax(int[] arr){    int maxIndex = 0;//記錄元素下標    for (int i = 1; i<arr.length; i++) {        if(arr[i]>arr[maxIndex]){            arr[maxIndex] = arr[i];        }    }    return arr[maxIndex];}

3.排序

java API提供了排序的方法：java.util.Arrays.sort(arr);

1.選擇排序法

原理：

代碼：

public void selectSort(int[] arr){        int temp;        for (int i = 0; i<arr.length-1; i++) {            for (int j = i+1; j<arr.length; j++) {                if(arr[i]>arr[j]){//交換                    temp = arr[i];                    arr[i] = arr[j];                    arr[j] = temp;                }            }        }

}

 

2.冒泡排序法

原理：

代碼：

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

*封裝交換代碼：

//交換數組中兩個元素的位置public static void swap(int[] arr, int a, int b){    int temp = arr[a];    arr[a] = arr[b];    arr[b] = arr[a];}

 

選擇排序性能優化：

如上圖所示，由于數組儲存于堆內存中，重復多余的交換位置會帶來多余的運算，所以想到定義中間變量來記錄每次得到的最小值，再進行對應位置的交換，這樣能減少交換的次數，提高效率。

代碼：

public static void selectSort_2(int[] arr){                for (int i = 0; i<arr.length-1; i++) {            int num = arr[i];            int index = i;            for (int j = i; j<arr.length; j++) {//內循環負責查找余下元素中的最小元素                if(num>arr[j]){                    num = arr[j];//用num記錄最小的元素                    index = j;//用index記錄最小元素的下標                }            }

            if(index!=i){                swap(arr, i, index);//交換最新要要排序的元素和查找到的最小元素位置

            }        }    }

4.查找

1.查找某元素第一次出現的位置

代碼：

public static int getIndex(int[] arr , int num){        for (int i = 0; i<arr.length; i++) {            if(num==arr[i]){                return i;            }        }        return -1;    }

2.二分查找（折半查找）

**適用于有序數組

java API也提供了二分查找 。java.util.Arrays.binarySearch(int[],target);如果存在，返回下標，如果不存在，返回 -插入點-1

代碼： 

1.遞歸法：

public static int find(int arry[], int target, int beginIndex, int endIndex) {    if (beginIndex > endIndex) {        return -1;    }    int middleIndex = (beginIndex + endIndex) / 2;    if (arry[middleIndex] == target) {        return middleIndex;    } else if (arry[middleIndex] < target) {        beginIndex = middleIndex + 1;    } else        endIndex = middleIndex - 1;    return find(arry, target, beginIndex, endIndex);}

2.while循環 

1.

public static int halfSearch(int[] arr, int target){    int min = 0, max = arr.length-1, mid = (min + max)/2;    while(arr[mid]!=target){//        if(target>arr[mid])            min = mid + 1;        else if(target<arr[mid])            max = mid - 1;        if(max<min){            return -1;        }        mid = (min + max)/2;    }    return mid;}

 

2.

public static int halfSearch(int[] arr, int target){    int min = 0, max = arr.length-1, mid;    while(max>=min){        mid = (min + max)/2;        if(target>arr[mid])            min = mid + 1;        else if(target<arr[mid])            max = mid - 1;        else            return mid;            }    return -1;}

 

面試題：給定一個有序的數組，如果往數組中存儲一個元素，并保證這個數組還是有序的，那么這個元素的存儲的角標如何獲取。

答案：直接使用上面的二分查找的函數，把返回-1改成返回min即可。

3.二維數組

格式1：int[][] arr = new int[3][2];

• 定義了名稱為arr的二維數組
• 二維數組中有3個一維數組
• 每一個一維數組有2個元素
• 一維數組的名稱分別是arr[0],arr[1],arr[2]
• 給第一個一維數組1下標位賦值為78的寫法是：arr[0][1]=78;

格式2：int[][] arr = new int[3][];

• 二維數組中有3個一維數組
• 每一個一維數組都是默認初始化值null
• 可以對這3個一維數組分別進行初始化

       arr[0] = new int[3];

       arr[1] = new int[1];

       arr[2] = new int[2];

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

 

考慮如下代碼：

int[][] arr = new int[3][2];System.out.println(arr);//[[I@6dc57a92System.out.println(arr[0]);//[I@3ff23f8bSystem.out.println(arr[0][0]);//0int[][] arr2 = new int[3][];System.out.println(arr2);//[[I@3929df79System.out.println(arr2[0]);//nullSystem.out.println(arr2[0][0]);//NullPointerException

說明：

第一種定義方式：在棧內存中保存一個arr的變量，用來記錄二維數組在堆內存中的地址值。在堆內存中會創建一個二維數組，開辟三個連續的空間用來保存三個一維數組的首地址值。堆內存中還會有三個對應的一維數組的實體，每一個一維數組的每一個元素默認初始化值為0.

第二種定義方式：在棧內存中保存一個arr的變量，用來記錄二維數組在堆內存中的地址值。在堆內存中會創建一個二維數組，開辟三個連續的空間默認初始化值為null。

 

二維數組的長度的獲取：

二維數組的長度用arr.length獲取，得到的是二維數組中一維數組的個數。如：

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

arr.length的值為 3。

arr[0].length獲取的是第一個一維數組的長度。

----------完----------

by_世界是我的床