1.一维数组

1.1数组的定义

数组是一个具有相同数据类型，且按一定次序排列的一组变量的集合体。即用一个变量名表示一批数据。Java为数组在内存中分配的是一段连续的空间，这段空间中存储数据的个数是固定的。

1.1.1数组元素

构成一个数组的每一个数据称为数组元素。

1.1.2数组下标

下标是数组元素在数组中的位置。在一个数组中，数组下标是用整数表示的，从0开始，依次加1。

1.1.3数组大小

数组中，元素的个数被称作数组的大小，也叫作数组的长度。

1.2数组的使用

1.2.1定义数组

public static void main(String[] args) {
    int arr[];  //或者 int[] arr;
}

1.2.2为数组元素分配内存

    arr = new int[3];

1.2.3数组元素初始化

    arr[0] = 35;
    arr[1] = 26;
    arr[2] = 43;

数组初始化指为数组中的数组元素进行第一次赋值。如果没有对数组变量进行初始化，数组元素也会有相对应得默认初始值，各类型数组元素默认初始值如下：

数组元素类型	默认初始值
byte,short,int,long	0
float,double	0.0
char	'\u0000'
boolean	false
引用数据类型	null

1.2.4使用数组

例：求班级五个同学成绩的平均值

public static void main(String[] args) {
    //第一步：定义数组，数组的名称是score
    int[] score;//或者int score[]
    //第二步：为数组元素分配内存
    score =new int[5];
    //第三步：为数组元素初始化
    Random random =new Random();
    for (int i =0; i < score.length; i++) {
        score[i] = random.nextInt(40) +60;
    }
    //第四步：使用数组元素
    int sum =0;
    for (int i =0; i < score.length; i++) {
        sum += score[i];
    }
    System.out.println(sum / score.length);
}

1.3一维数组的常用算法

1.3.1创建一个成绩的数据，统计最大值，最小值，平均值，求和

public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int []score = new int[5];
        //成绩初始化
        for (int i = 0; i < score.length; i++) {
            System.out.println("请输入第"+(i+1)+"个学生的成绩");
            score[i]= s.nextInt();
        }
        //求最高分，求最低分
        int max  = score[0];
        int min = score[0];
        for (int i = 1; i < score.length; i++) {
            if(max<score[i]){
                max = score[i];
            }
            if(min>score[i]){
                min = score[i];
            }
        }
        System.out.println("最高分为"+max);
        System.out.println("最低分为"+min);
        //总分
        int sum = 0;
        for (int i = 0; i < score.length; i++) {
            sum += score[i];
        }
        System.out.println("班级总分："+sum);
        System.out.println("班级平均分"+sum/score.length);
    }

1.3.2冒泡排序

1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个。
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这样，最后的元素就会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

例：输入5个人的身高，用冒泡排序进行升序排列

public static void main(String[] args) {
    //储存五个人的身高
    int height[] =new int[5];
    Scanner scanner =new Scanner(System.in);
    //循环输入五个人的身高
    for (int i =0; i < height.length; i++) {
        System.out.println("请输入" + (i+1) +"个人的身高：");
        height[i] = scanner.nextInt();
    }
    //定义临时变量
    int temp;
    //进行冒泡排序
    for (int i =0; i < height.length; i++) {
        for (int j =0; j < height.length -1 - i; j++) {
            if (height[j]>height[j+1]){
                temp = height[j];
                height[j] = height[j+1];
                height[j+1] = temp;
            }
        }
    }
    //将排序后的结果进行输出
    System.out.println("5个人的身高从低到高依次是：");
    for (int i =0; i < height.length; i++) {
        System.out.print(height[i] +" ");
    }
}

1.3.3选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

例：对80000个80000以内的随机数进行选择排序

public static void main(String[] args) {
    //选择排序
    int []arr =new int[80000];
    Random random =new Random();
    for (int i =0; i < arr.length; i++){
        arr[i] =random.nextInt(80000);
    }
    for (int i =0; i < arr.length-1; i++) {
        //每次循环都会找出最小的数
        int minIndex = i;//记录最小的下表
        int min = arr[i];//记录最小数
        for (int j = i+1; j < arr.length; j++) {
            if (arr[j]<min){
                //如果当前数比最小数小，则更新最小数
                min = arr[j];//更新最小数
                minIndex = j;//更新最小数的下标
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIndex];//将最小数放到最前面
        arr[minIndex] = temp;
    }
    System.out.println(Arrays.toString(arr));
}

1.3.4插入排序

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序。

例：对80000个80000以内的随机数进行插入排序

public static void main(String[] args) {
    //插入排序
    int[] arr =new int[80000];
    for (int i =0; i <80000; i++) {
        arr[i] =(int)(Math.random()*80000);
    }
    for (int i =1; i < arr.length; i++) {
        int j = i;
        while (j >0){
            if (arr[j] < arr[j-1]){
                int temp;
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                j--;
            }else {
                break;
            }
        }
    }
    System.out.println(Arrays.toString(arr));
}

1.3.5快速排序

(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

例：对80000个80000以内的随机数进行快速排序

public static void main(String[] args) {
        //快速排序
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++){
            arr[i] = (int)(Math.random() * 80000);
        }
        //打印开始排序时的时间
        long s = System.currentTimeMillis();
        quickSort(arr,0,arr.length-1);
        //打印排序结束时的时间
        long e = System.currentTimeMillis();
        System.out.println(e - s);
    }
    private static void quickSort(int[] arr, int first, int last) {
        if (first >= last){
            return;
        }
        int low = first;
        int high = last;
        //如果mid_value = arr[last]的话，下面的两个内部while循环就要换一下顺序
        int mid_value = arr[first];
        while (low < high){
            while (low < high && arr[high] >= mid_value){
                high -= 1;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] < mid_value){
                low += 1;
            }
            arr[high] = arr[low];
        }
        arr[high] = mid_value;
        //递归对左右两边的数据排序
        quickSort(arr, first, low-1);
        quickSort(arr, low+1, last);
    }

1.3.6二分查找

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

例：

public static void main(String[] args) {
        int num[] = {3,9,12,48,67};
        int index = binarySearch(num,9);
        System.out.println(index);
    }
    private static int binarySearch(int[] srcArray, int des) {
        //定义初始最小、最大索引
        int start = 0;
        int end = srcArray.length - 1;
        //确保不会出现重复查找，越界
        while (start <= end){
            //计算出中间索引值
            int middle = (end + start)>>>1;//防止溢出
            if (des == srcArray[middle]){
                return middle;
                //判断下限
            }else if (des < srcArray[middle]){
                end = middle - 1;
                //判断上限
            }else {
                start = middle + 1;
            }
        }
        //若没有，则返回-1
        return -1;
    }

1.4Arrays类的应用

JDK中提供了一个专门用于操作数组的工具类，即Arrays类，位于java.util包中。该类提供了一系列的方法来操作数组，如排序，比较，查询等。Arrays类常用方法如下表：

方法	返回类型	说明
equals(array1,array2)	boolean	比较两个数组是否相等
sort(array)	void	对数组array的元素进行排序
toString(array)	String	将一个数组array转换成一个字符串
fill(array,val)	void	把数组array的所有元素都赋值成val
copyOf(array,length)	与array数据类型一致	把数组array复制成一个长度为length的新数组
binarySearch(array,val)	int	查询元素值val在数组array中的下标

1.4.1 比较两个数组是否相等equals()

public static void main(String[] args) {
        //比较两个数组是否相等（equals）
        int[] arr1 = {10,50,40,30};
        int[] arr2 = {10,50,40,30};
        int[] arr3 = {60,50,85};
        System.out.println(Arrays.equals(arr1,arr2));//判断arr1和arr2的长度及元素是否相等
        System.out.println(Arrays.equals(arr1,arr3));//判断arr1和arr3的长度及元素是否相等
}

1.4.2 对数组元素进行升序排序sort()

public static void main(String[] args) {
        //对数组元素进行升序排列(sort)
        int[][] score = new int[][] {{67,75},{78,93,82},{72,71}};
        for (int i = 0; i < score.length; i++) {
            String str = (i+1) + "班";
            Arrays.sort(score[i]);
            System.out.println(str + "排序后:");
            for (int j = 0; j < score[i].length; j++) {
                System.out.println(score[i][j]);
            }
        }
}

1.4.3 将数组转换成字符串toString()

public static void main(String[] args) {
        //将数组转换成字符串(toString)
        int[] arr = new int[]{10,50,40,30};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
}

1.4.4 将数组所有元素赋值为相同的值fill(array,vall)

public static void main(String[] args) {
        //将数组所有元素赋值为相同的值(fill(array,vall))
        int[] arr =new int[]{10,50,40,30};
        Arrays.fill(arr,40);
        System.out.println(Arrays.toString(arr));
}

1.4.5 将数组赋值成一个长度为设定值的新数组copy()

public static void main(String[] args) {
        //将数组赋值成一个长度为设定值的新函数(copy)
        int[] arr1 = new int[]{10,50,40,30};

        //将arr1复制成长度为3的新数组arr2
        int[] arr2 = Arrays.copyOf(arr1,3);
        System.out.println(Arrays.toString(arr2));

        //将arr1复制成长度为3的新数组arr2
        int[] arr3 = Arrays.copyOf(arr1,4);
        System.out.println(Arrays.toString(arr3));

        //将arr1复制成长度为3的新数组arr3
        int[] arr4 = Arrays.copyOf(arr1,6);
        System.out.println(Arrays.toString(arr4));
}

1.4.6查询元素在数组中的下标binary(Object[],Object key)

public static void main(String[] args) {
        //查询元素在数组中的下标(binary(Object[],Object key))
        int[] arr = new int[]{10,50,40,30};
        Arrays.sort(arr);//排序后：10,30,40,50
        int index =Arrays.binarySearch(arr,40);
        System.out.println(index);
        index =Arrays.binarySearch(arr,0);
        System.out.println(index);
        index =Arrays.binarySearch(arr,45);
        System.out.println(index);
        index =Arrays.binarySearch(arr,90);
        System.out.println(index);
}

2.二维数组

2.1二维数组的结构

例：分别计算每个人班级学生的总成绩

public static void main(String[] args) {
        int[][] score = {
                {65,75},
                {78,82,93},
                {71,72}
        };
        //定义保存总成绩的变量total
        int total;
        //遍历二维数组，计算每个班的总成绩
        for (int i = 0; i < score.length; i++) {
            String str = (i+1) + "班";
            total = 0;
            for (int j = 0; j < score[i].length; j++) {
                total += score[i][j];
            }
            System.out.println(str + "总成绩" + total);
        }
    }

3.利用数组解决的问题

3.1 从键盘输入班级学员的数量，然后输入每一位学员的成绩，最后将成绩按从大到小进行排序输出，并计算平均值。

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入学员人数：");
        int sum = 0;
        int i =scanner.nextInt();
        int score[] = new int[i];//定义数组
        //数组初始化
        for (i = 0; i < score.length; i++) {
            System.out.println("请输入第" + (i+1) + "个学员的成绩：");
            score[i] = scanner.nextInt();
        }
        //对数组元素进行排序
        for (int j = 0; j < score.length-1; j++) {
            for (int k = 0; k < score.length-j-1; k++) {
                if (score[k]<score[k+1]){
                    int temp = score[k];
                    score[k] = score[k+1];
                    score[k+1] = temp;
                }
            }
        }

        System.out.println((i+1) + "个人的成绩从大到小依次是：");
        for (int j = 0; j < score.length; j++) {
            System.out.print(score[j] + " ");
        }
        System.out.println();

        //计算总成绩
        for (int j = 0; j < score.length; j++) {
            sum += score[j];
        }
        System.out.println("该班级的总成绩为：" + sum);
}

3.2 定义如下数组 int[] array1=new int[]{34,45,56} ，编程实现向数组中再增加一个数字67。

public static void main(String[] args) {
        int array1[] =new int[]{34,45,56};
        int array2[] = Arrays.copyOf(array1,4);
        array2[3] = 67;
        System.out.println(Arrays.toString(array2));
}

3.3 将二维 int 类型的数组中每一行中最小的值取出，放到新的数组中。

public static void main(String[] args) {
        int arr1[][] ={
                {5,6,1,3},
                {9,2,7,4},
                {0,10,8}
        };
        int arr2[] = new int[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            Arrays.sort(arr1[i]);
            arr2[i] = arr1[i][0];
        }
        System.out.println(Arrays.toString(arr2));
}

3.4 将二维 int 类型的数组中每一列中最小的值取出，放到新的数组中。

public static void main(String[] args) {
        //定义二维数组arr1
        int arr1[][] ={
                {5,6,1,4},
                {9,2},
                {7,0,4,32},
                {6,15}
        };
        //获取二维数组的最大行数
        int max=0;
        for (int i = 0; i < arr1.length; i++) {
            if (max < arr1[i].length){
                max = arr1[i].length;
            }
        }
        //进行行列转换获得数组arr2
        int arr2[][]=new int[max][arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1[i].length; j++) {
                arr2[j][i]=arr1[i][j];
            }
        }
        //对每一行进行升序排列，并将每一行最小且不为0的值赋给一维数组arr3
        int arr3[] = new int[arr2.length];
        for (int i = 0; i < arr2.length; i++) {
            Arrays.sort(arr2[i]);
            for (int j = 0; j < arr2[i].length; j++) {
                if (arr2[i][j] != 0){
                    arr3[i] = arr2[i][j];
                    break;
                }
            }
        }
        //将arr1中原本为0的且为其列最小的元素赋给arr3
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1[i].length; j++) {
                if (arr1[i][j] == 0){
                    if (arr3[j] > 0)
                    arr3[j] = 0;
                }
            }
        }
        System.out.println(Arrays.toString(arr3));
}