1.1.        数组

概念
同一种类型数据的集合。其实数组就是一个容器。
数组的好处
可以自动给数组中的元素从0开始编号，方便操作这些元素。
数组的定义

格式1：
元素类型[] 数组名 = new 元素类型[元素个数或数组长度];
示例：int[] arr = new int[5];
      int arr[] =new int[5];
格式2：
元素类型[] 数组名 = new 元素类型[]{元素，元素，……};
int[] arr = new int[]{3,5,1,7};
int[] arr = {3,5,1,7};

注意：给数组分配空间时，必须指定数组能够存储的元素个数来确定数组大小。创建数组之后不能修改数组的大小。可以使用length 属性获取数组的大小，遍历数组。
1.1.1.        数组初始化

初始化方式1：不使用运算符new
int[] arr = { 1, 2, 3, 4, 5 };
int[] arr2 = new int[] { 1, 2, 3, 4, 5 };
初始化方式2：               
int[] arr3=new int[3];
arr3[0]=1;
arr3[1]=5;
arr3[2]=6;

如果数组初始化中不使用运算符new。需要注意：下列写法是错误的。
int[] arr;
arr={1,2,3,4,5};
此时初始化数组，必须将声明，创建，初始化都放在一条语句中个，分开会产生语法错误。
所以只能如下写：
int[] arr={1,2,3,4,5};

1.1.2.        数组遍历
public static void main(String[] args) {
                int[] x = { 1, 2, 3 };
                for (int i = 0; i < 3; i++) {
                        System.out.println(x[i]);
                       
                }
        }
数组中有一个属性可以获取到数组中元素的个数,也就是数组的长度. 数组名.length
public static void main(String[] args) {
                int[] x = { 1, 2, 3 };
                for (int i = 0; i < x.length; i++) {
                        System.out.println(x[y]);
                }
        }

1.1.3.        数组的常见异常
一数组角标越界异常:，注意：数组的角标从0开始。
public static void main(String[] args) {
                int[] x = { 1, 2, 3 };
                System.out.println(x[3]);
                //java.lang.ArrayIndexOutOfBoundsException
}



二 空指针异常:
public static void main(String[] args) {
                int[] x = { 1, 2, 3 };
                x = null;
                System.out.println(x[1]);
                // java.lang.NullPointerException
        }

数组的特点:
数组长度是固定的。
1.1.4.        数组的常见操作
1:定义一个遍历数组的函数
2:定义一个求数组和的功能函数
3:定义一个获取数组最大值的功能函数
4:定义一个获取数组最大值角标的功能函数
5:定义一个返回指定数在指定数组中包含的角标的功能函数
6:定义一个可以用于排序int数组的函数
        1:冒泡
        2:选择
7：定义一个可以将整数数组进行反序的功能函数。
8:二分查找(必须是有序的 )
基本操作：
1、获取最值(最大值，最小值)
2、排序（选择排序，冒泡排序）  //6,2,8,-1,5,9,7
3、折半查找(二分查找)
1.1.4.1.        获取最值
1获取最大值,
2获取最小值,
3使用0进行比较的问题（元素全是负数）。定义第三方变量的问题。
public static int getMax(int[] arr) {
                int max = 0;
                for (int x = 0; x < arr.length; x++) {
                        if (max < arr[x]) {
                                max = arr[x];
                        }
                }
                return max;
}

public static void main(String[] args) {
                int[] x = new int[] { 2, 5, 6, 20, 100 };
                int max=getMax(x);
                System.out.println(max);
}
注意：如果数组中有负数（元素全是负数），还可以吗？
所以：初始化为0，正整数没问题如果是负数。那么就初始化为元素的任意一个元素
public static int getMax(int[] arr) {
                int max = arr[0];
                for (int x = 0; x < arr.length; x++) {
                        if (max < arr[x]) {
                                max = arr[x];
                        }
                }
                return max;
        }
注意：定义变量的时候初始化为0, 其实也是可以的。让变量作为角标就行了。
public static int getMax(int[] arr) {
                int max = 0;
                for (int x = 0; x < arr.length; x++) {
                        if (arr[max] < arr[x]) {
                                max = x;
                        }
                }
                return arr[max];
        }

1.1.4.2.        数组的排序
想要对一个数组排序例如int[] arr={4,5,2,1,7}，按照从小到大的顺序（升序）排列。
1、冒泡排序（bubble sort）
   冒泡排序，每次两个相邻的值进行比较，内层循环结束，最后出现最大值
2、选择排序（selection sort）
选择排序先找到数组中最小的数，然后将它放在数组的最前边，然后在剩下的数组找到最小数，将它放在第一个数的后边，以此类推，知道该数组仅剩一个数为止。


/*
        冒泡排序，每次两个相邻的值进行比较，内层循环结束，最后出现最大值。
        内层循环 arr.length-1 避免角标越界
                 arr.length-x 减少参与比较的数，因为这些数，已经是最大值，排在最后，没有必要参与比较。
*/
        public static void bubbleSort(int[] arr){
                for(int x=0;x<arr.length;x++){
                        for(int y=0;y<arr.length-1-x;y++){
                                if(arr[y]>arr[y+1]){
                                        int temp=0;
                                        temp=arr[y+1];
                                        arr[y+1]=arr[y];
                                        arr[y]=temp;
                                }
                        }
                }
        }

/*
        选择排序。内循环结束 0角标位出现最小值。只要外层循环的值比内层循环值大，就互换位置。
        0角标位的元素，和0角标位以后的每个元素进行比较，只要比他们大就互换，位置，这样可以保证0角标位置值最小。
        然后，再进行1角标位置和1角标后的每个元素进行比较。
        依次类推，
*/
        public static void selectSort(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[y];
                                        arr[y]=arr[x];
                                        arr[x]=temp;
                                }
                        }
                }
        }

1.1.4.3.        数组折半查找（二分查找）
数组的二分查找效率较高，但是要排序。
数组折半查找必须对于有序数组。
定义变量min 和max分别表示数组的头角标和尾角标第一次比较是min是0，max是数组.length-1。并且定义变量mid记录数组的中间元素的角标。mid=（min+max）/2;
重复的比较需要使用循环，使用while即可，控制循环的条件是min<=max 即可。
注意：为什么要用等号（=）如果数组中只有一个元素，这个查找就会漏掉这个元素。
练习：
对数组中的元素进行查找，获取该元素第一次在数组中出现的位置。
public static int getIndex(int[] arr, int key) {
                for (int x = 0; x < arr.length; x++) {
                        if (arr[x] == key) {
                                return x;
                        }
                }
                return -1;
}
折半查找
通过定义变量，记录着头角标min，尾角标max，和中间角标mid，
初始化的变量为min = 0; max = arr.length - 1; mid = (max + min) / 2;
只要头角标小于等于尾角标，意味着还有数字可查。就可以一直进行循环判断和查找。
根据想要查找的key 进行判断，如果该数大于arr[mid] 那么意味着先要查找的数在mid角标的右边，需要重新计算头角标，从mid+1 开始。尾角标不变。
如果        key<arr[mid] 意味着想要查找的数在mid的左边，需要重新计算尾角标。
这样循环。通过if  else if 语句，如果if else if 都不满足，就是既不大于，又不小于，那么就是等于。说明查找的数正对应mid。直接return 就可以了。

要考虑没有查找到。通过返回-1 来表示没有找到查找的数。        

public static int halfSearch(int[] arr, int key) {

                int max, min, mid;
                min = 0;
                max = arr.length - 1;

                while (min <= max) {
                        mid = (max + min) / 2;
                        if (key > arr[mid])
                                min = mid + 1;
                        else if (key < arr[mid])
                                max = mid - 1;
                        else
                                return mid;
                }
                return -1;
        }

1.1.        数组

概念
同一种类型数据的集合。其实数组就是一个容器。
数组的好处
可以自动给数组中的元素从0开始编号，方便操作这些元素。
数组的定义

格式1：
元素类型[] 数组名 = new 元素类型[元素个数或数组长度];
示例：int[] arr = new int[5];
      int arr[] =new int[5];
格式2：
元素类型[] 数组名 = new 元素类型[]{元素，元素，……};
int[] arr = new int[]{3,5,1,7};
int[] arr = {3,5,1,7};

注意：给数组分配空间时，必须指定数组能够存储的元素个数来确定数组大小。创建数组之后不能修改数组的大小。可以使用length 属性获取数组的大小，遍历数组。
1.1.1.        数组初始化

初始化方式1：不使用运算符new
int[] arr = { 1, 2, 3, 4, 5 };
int[] arr2 = new int[] { 1, 2, 3, 4, 5 };
初始化方式2：               
int[] arr3=new int[3];
arr3[0]=1;
arr3[1]=5;
arr3[2]=6;

如果数组初始化中不使用运算符new。需要注意：下列写法是错误的。
int[] arr;
arr={1,2,3,4,5};
此时初始化数组，必须将声明，创建，初始化都放在一条语句中个，分开会产生语法错误。
所以只能如下写：
int[] arr={1,2,3,4,5};

1.1.2.        数组遍历
public static void main(String[] args) {
                int[] x = { 1, 2, 3 };
                for (int i = 0; i < 3; i++) {
                        System.out.println(x[i]);
                       
                }
        }
数组中有一个属性可以获取到数组中元素的个数,也就是数组的长度. 数组名.length
public static void main(String[] args) {
                int[] x = { 1, 2, 3 };
                for (int i = 0; i < x.length; i++) {
                        System.out.println(x[y]);
                }
        }

1.1.3.        数组的常见异常
一数组角标越界异常:，注意：数组的角标从0开始。
public static void main(String[] args) {
                int[] x = { 1, 2, 3 };
                System.out.println(x[3]);
                //java.lang.ArrayIndexOutOfBoundsException
}



二 空指针异常:
public static void main(String[] args) {
                int[] x = { 1, 2, 3 };
                x = null;
                System.out.println(x[1]);
                // java.lang.NullPointerException
        }

数组的特点:
数组长度是固定的。
1.1.4.        数组的常见操作
1:定义一个遍历数组的函数
2:定义一个求数组和的功能函数
3:定义一个获取数组最大值的功能函数
4:定义一个获取数组最大值角标的功能函数
5:定义一个返回指定数在指定数组中包含的角标的功能函数
6:定义一个可以用于排序int数组的函数
        1:冒泡
        2:选择
7：定义一个可以将整数数组进行反序的功能函数。
8:二分查找(必须是有序的 )
基本操作：
1、获取最值(最大值，最小值)
2、排序（选择排序，冒泡排序）  //6,2,8,-1,5,9,7
3、折半查找(二分查找)
1.1.4.1.        获取最值
1获取最大值,
2获取最小值,
3使用0进行比较的问题（元素全是负数）。定义第三方变量的问题。
public static int getMax(int[] arr) {
                int max = 0;
                for (int x = 0; x < arr.length; x++) {
                        if (max < arr[x]) {
                                max = arr[x];
                        }
                }
                return max;
}

public static void main(String[] args) {
                int[] x = new int[] { 2, 5, 6, 20, 100 };
                int max=getMax(x);
                System.out.println(max);
}
注意：如果数组中有负数（元素全是负数），还可以吗？
所以：初始化为0，正整数没问题如果是负数。那么就初始化为元素的任意一个元素
public static int getMax(int[] arr) {
                int max = arr[0];
                for (int x = 0; x < arr.length; x++) {
                        if (max < arr[x]) {
                                max = arr[x];
                        }
                }
                return max;
        }
注意：定义变量的时候初始化为0, 其实也是可以的。让变量作为角标就行了。
public static int getMax(int[] arr) {
                int max = 0;
                for (int x = 0; x < arr.length; x++) {
                        if (arr[max] < arr[x]) {
                                max = x;
                        }
                }
                return arr[max];
        }

1.1.4.2.        数组的排序
想要对一个数组排序例如int[] arr={4,5,2,1,7}，按照从小到大的顺序（升序）排列。
1、冒泡排序（bubble sort）
   冒泡排序，每次两个相邻的值进行比较，内层循环结束，最后出现最大值
2、选择排序（selection sort）
选择排序先找到数组中最小的数，然后将它放在数组的最前边，然后在剩下的数组找到最小数，将它放在第一个数的后边，以此类推，知道该数组仅剩一个数为止。


/*
        冒泡排序，每次两个相邻的值进行比较，内层循环结束，最后出现最大值。
        内层循环 arr.length-1 避免角标越界
                 arr.length-x 减少参与比较的数，因为这些数，已经是最大值，排在最后，没有必要参与比较。
*/
        public static void bubbleSort(int[] arr){
                for(int x=0;x<arr.length;x++){
                        for(int y=0;y<arr.length-1-x;y++){
                                if(arr[y]>arr[y+1]){
                                        int temp=0;
                                        temp=arr[y+1];
                                        arr[y+1]=arr[y];
                                        arr[y]=temp;
                                }
                        }
                }
        }

/*
        选择排序。内循环结束 0角标位出现最小值。只要外层循环的值比内层循环值大，就互换位置。
        0角标位的元素，和0角标位以后的每个元素进行比较，只要比他们大就互换，位置，这样可以保证0角标位置值最小。
        然后，再进行1角标位置和1角标后的每个元素进行比较。
        依次类推，
*/
        public static void selectSort(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[y];
                                        arr[y]=arr[x];
                                        arr[x]=temp;
                                }
                        }
                }
        }

1.1.4.3.        数组折半查找（二分查找）
数组的二分查找效率较高，但是要排序。
数组折半查找必须对于有序数组。
定义变量min 和max分别表示数组的头角标和尾角标第一次比较是min是0，max是数组.length-1。并且定义变量mid记录数组的中间元素的角标。mid=（min+max）/2;
重复的比较需要使用循环，使用while即可，控制循环的条件是min<=max 即可。
注意：为什么要用等号（=）如果数组中只有一个元素，这个查找就会漏掉这个元素。
练习：
对数组中的元素进行查找，获取该元素第一次在数组中出现的位置。
public static int getIndex(int[] arr, int key) {
                for (int x = 0; x < arr.length; x++) {
                        if (arr[x] == key) {
                                return x;
                        }
                }
                return -1;
}
折半查找
通过定义变量，记录着头角标min，尾角标max，和中间角标mid，
初始化的变量为min = 0; max = arr.length - 1; mid = (max + min) / 2;
只要头角标小于等于尾角标，意味着还有数字可查。就可以一直进行循环判断和查找。
根据想要查找的key 进行判断，如果该数大于arr[mid] 那么意味着先要查找的数在mid角标的右边，需要重新计算头角标，从mid+1 开始。尾角标不变。
如果        key<arr[mid] 意味着想要查找的数在mid的左边，需要重新计算尾角标。
这样循环。通过if  else if 语句，如果if else if 都不满足，就是既不大于，又不小于，那么就是等于。说明查找的数正对应mid。直接return 就可以了。

要考虑没有查找到。通过返回-1 来表示没有找到查找的数。        

public static int halfSearch(int[] arr, int key) {

                int max, min, mid;
                min = 0;
                max = arr.length - 1;

                while (min <= max) {
                        mid = (max + min) / 2;
                        if (key > arr[mid])
                                min = mid + 1;
                        else if (key < arr[mid])
                                max = mid - 1;
                        else
                                return mid;
                }
                return -1;
        }