一、数组涉及的算法

  1. 数组元素的赋值(杨辉三角、回形数等) （杨辉三角在上一节）
  2. 求数值型数组中元素的最大值、最小值、平均数、总和等
  3. 数组的复制、反转、查找(线性查找、二分法查找)
  4. 数组元素的排序算法（冒泡、快速）

二、求数值型数组中元素的最大值、最小值、平均数、总和

  1. package com.atguigu.java;
  3. /*
  4.  * 定义一个int型的一维数组，包含10个元素，分别赋一些随机整数，
  5. 然后求出所有元素的最大值，最小值，和值，平均值，并输出出来。
  6. 要求：所有随机数都是两位数。
  7. [10,99]
  8. 公式：获取[a,b]范围的随机数：(int)(Math.random()*(b - a + 1) + a )
  9. */
  11. public class ArrayTest1 {
  13.     public static void main(String[] args) {
  14.         int [] arr = new int[10];
  16.         for(int i = 0;i < arr.length;i++){
  17.             arr[i] = (int)(Math.random()*(99 - 10 + 1) + 10);
  18.             System.out.print(arr[i] + " ");
  19.         }
  20.         System.out.println();
  22.         //求数组元素的最大值
  23.         int maxValue = arr[0];
  24.         for(int i = 1;i < arr.length;i++){
  25.             if(maxValue < arr[i]){
  26.                 maxValue = arr[i];
  27.             }
  28.         }
  29.         System.out.println(maxValue);
  31.         //求数组元素的最小值
  32.         int minValue = arr[0];
  33.         for(int i = 1;i < arr.length;i++){
  34.             if(minValue > arr[i]){
  35.                 minValue = arr[i];
  36.             }
  37.         }
  38.         System.out.println(minValue);
  40.         //求数组元素的总和
  41.         int sum = 0;
  42.         for(int i = 0;i < arr.length;i++){
  43.             sum += arr[i];
  44.         }
  45.         System.out.println(sum);
  47.         //求数组元素的平均值
  48.         double aver = sum / arr.length;
  49.         System.out.println(aver);
  50.     }
  51. }

三、数组的复制、反转、查找(线性查找、二分法查找)

new一次有一个地址（堆中开辟一个空间）

3.1 练习

使用简单数组

  1. 创建一个名为ArrayTest的类，在main()方法中声明array1和array2两个变量，他们是int[]类型的数组。

  2. 使用大括号{}，把array1初始化为8个素数：2,3,5,7,11,13,17,19。

  3. 显示array1的内容。

  4. 赋值array2变量等于array1，修改array2中的偶索引元素，使其等于索引值，(如array[0]=0,array[2]=2)。打印出array1。

  5. 思考：array1和array2是什么关系？array1和array2地址值相同，都指向堆空间中唯一的数组实体

  6. 拓展：修改题目，实现array2对array1数组的复制

  1. package com.atguigu.exer;
  3. import java.lang.reflect.Array;
  5. /*
  6.  * 使用简单数组
  7. (1)创建一个名为ArrayTest的类，在main()方法中声明array1和array2两个变量，
  8. 他们是int[]类型的数组。
  9. (2)使用大括号{}，把array1初始化为8个素数：2,3,5,7,11,13,17,19。
  10. (3)显示array1的内容。
  11. (4)赋值array2变量等于array1，修改array2中的偶索引元素，使其等于索引值
  12. (如array[0]=0,array[2]=2)。打印出array1。
  13. 思考：array1和array2是什么关系？array1和array2地址值相同，都指向堆空间中唯一的数组实体
  14. 拓展：修改题目，实现array2对array1数组的复制
  15. */
  16. public class ArrayExer2 {
  18.     public static void main(String[] args) {
  19.         //声明
  20.         int[] array1,array2 = null;//arr在栈中，存储的是地址值
  22.         array1 = new int[]{2,3,5,11,13,17,19};
  24.         //显示array1的内容
  25.         for(int i = 0;i < array1.length;i++){
  26.             System.out.println(array1[i] + "\t");
  27.         }    
  29.         //赋值array2变量等于array1
  30.         //不能称作数组的复制。他们指向的地址一样,并没有开辟新的内存空间，只是把array1的地址值给array2
  31.             array2 = array1;
  34.         //修改array2中偶索引元素，使其等于索引值(如array[0] = 0,array[2] = 2)
  35.         for(int i = 0;i < array2.length;i++){
  36.             if(i % 2 == 0){
  37.                 array2[i] = i;
  38.             }    
  39.         }
  41.         System.out.println();
  42.         //打印出aray1
  43.         for(int i = 0;i < array1.length;i++){
  44.             System.out.println(array1[i]);
  45.         }
  46.     }
  47. }

数值的赋值

3.2 数组的复制、反转、查找(线性查找、二分法查找)

  1. package com.atguigu.java;
  3. /*算法的考查：数值的复制、反转、查找(线性查找、二分查找)*/
  4. public class ArrayTest2 {
  6.     public static void main(String[] args) {
  8.         String[] arr = new String[]{"JJ","DD","MM","AA","BB"};
  10.         //数组的复制(区别于数组变量的赋值：arr1 = arr)
  11.         String[] arr1 = new String[arr.length];
  12.         for(int i =0;i < arr1.length;i++){
  13.             arr1[i] = arr[i];
  14.         }
  16.         //数组的反转
  17.         //方法一：
  18.         for(int i = 0;i < arr.length / 2;i++){
  19.             String temp = arr[i];
  20.             arr[i] = arr[arr.length - 1 -i];
  21.             arr[arr.length - 1 -i] = temp;
  22.         }
  24.         //方法二：
  25.         for(int i = 0,j = arr.length - 1;i < j;i++,j--){
  26.             String temp = arr[i];
  27.             arr[i] = arr[j];
  28.             arr[j] = temp;
  29.         }
  31.         //遍历
  32.         for(int i = 0;i <arr.length;i++){
  33.             System.out.print(arr[i] + "\t");
  34.         }
  36.         //查找(或搜索)
  37.         //线性查找：
  38.         String dest = "BB";
  40.         boolean isFlag = true;
  42.         for(int i = 0;i < arr.length;i++){
  44.             if(dest.equals(arr[i])){//equals值
  45.                 System.out.println("指定元素：位置为： " + i);
  46.                 isFlag = false;
  47.                 break;
  48.             }
  49.         }
  51.         if(isFlag){
  52.             System.out.println("很遗憾，没有找到哦");
  53.         }
  55.         //二分法查找
  56.         //前提：所查找的数组必须有序。
  57.         int[] arr2 = new int[]{-98,-32,2,5,42,66,88};
  59.         int dest1 = -34;
  60.         int head = 0;//初始的首索引
  61.         int end = arr2.length;//初始的末索引
  62.         boolean isFlag1 = true;
  64.         while(head <= end){
  66.             int middle = (head + end)/2;
  68.             if(dest1 == arr2[middle]){
  69.                 System.out.println("找到了指定元素，位置为：" + middle);
  70.                 isFlag1 = false;
  71.                 break;//找到跳出循环
  72.             }else if(arr2[middle] > dest1){
  73.                 end = middle -1;
  74.             }else{//arr2[middle] < dest1
  75.                 head = middle + 1;
  76.             }            
  77.         }
  79.         if(isFlag1){
  80.             System.out.println("很遗憾，没有找到哦");
  81.         }        
  82.     }
  83. }

四、数组元素的排序算法

4.1 冒泡排序（会写代码）

  1. package com.atguigu.java;
  3. public class BubbleSortTest {
  5.     public static void main(String[] args) {
  6.         //在队中开辟空间，并赋值
  7.         int[] arr = new int[]{43,86,12,0,95,};
  9.         //冒泡排序 
  10.         for(int i = 0;i < arr.length - 1;i++){
  11.             for(int j = 0;j < arr.length - 1 - i;j++){
  12.                 if(arr[j] > arr[j+1] ){
  13.                     int temp = arr[j];
  14.                     arr[j] = arr[j+1];
  15.                     arr[j+1] = temp;
  16.                 }
  17.             }
  18.         }
  19.     }
  20. }

4.2 快速排序（会写代码）

  1. package com.atguigu.java;
  3. /**
  4.  * 快速排序
  5.  * 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，
  6.  * 则分别对这两部分继续进行排序，直到整个序列有序。
  7.  */
  8. public class QuickSort {
  9.     private static void swap(int[] data, int i, int j) {
  10.         int temp = data[i];
  11.         data[i] = data[j];
  12.         data[j] = temp;
  13.     }
  15.     private static void subSort(int[] data, int start, int end) {
  16.         if (start < end) {
  17.             int base = data[start];
  18.             int low = start;
  19.             int high = end + 1;
  20.             while (true) {
  21.                 while (low < end && data[++low] - base <= 0)
  22.                     ;
  23.                 while (high > start && data[--high] - base >= 0)
  24.                     ;
  25.                 if (low < high) {
  26.                     swap(data, low, high);
  27.                 } else {
  28.                     break;
  29.                 }
  30.             }
  31.             swap(data, start, high);
  33.             subSort(data, start, high - 1);//递归调用
  34.             subSort(data, high + 1, end);
  35.         }
  36.     }
  37.     public static void quickSort(int[] data){
  38.         subSort(data,0,data.length-1);
  39.     }
  41.     public static void main(String[] args) {
  42.         int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
  43.         System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
  44.         quickSort(data);
  45.         System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
  46.     }
  47. }

4.3 堆排序（知道思想）

4.4 归并排序（知道思想）

4.5 排序算法性能对比

快以nlog2n的速度归队

五、Arrays工具类的使用

  1. boolean equals(int[] a,int[] b) 判断两个数组是否相等。
  2. String toString(int[] a) 输出数组信息。
  3. void fill(int[] a,int val) 将指定值填充到数组之中。
  4. void sort(int[] a) 对数组进行排序。
  5. int binarySearch(int[] a,int key) 对排序后的数组进行二分法检索指定的值。
  1. package com.atguigu.java;
  2. import java.util.Arrays;
  3. /*
  4.  * java.util.Arrays:操作数组的工具类，里面定义了很多操作数组的方法
  5.  */
  7. public class ArraysTest {
  9.     public static void main(String[] args) {
  11.         //判断两个数组是否相等。
  12.         //1. boolean equals(int[] a,int[] b)
  13.         int[] arr1 = new int[]{1,2,3,4};
  14.         int[] arr2 = new int[]{1,3,2,4};
  15.         boolean isEquals = Arrays.equals(arr1,arr2);
  16.         System.out.println(isEquals);
  18.         //输出数组信息。
  19.         //2. String toString(int[] a)  
  20.         System.out.println(Arrays.toString(arr1));//[1, 2, 3, 4]
  22.         //将指定值填充到数组之中。 把原来数组每个元素都替换成10
  23.         //3. void fill(int[] a,int val)
  24.         Arrays.fill(arr1, 10);
  25.         System.out.println(Arrays.toString(arr1));//[10, 10, 10, 10]
  27.         //对数组进行排序。
  28.         //4. void sort(int[] a)
  29.         Arrays.sort(arr2);
  30.         System.out.println(Arrays.toString(arr2));
  32.         //对排序后的数组进行二分法检索指定的值。
  33.         //5. int binarySearch(int[] a,int key)
  34.         int[] arr3 = new int[]{-98,-32,2,34,66,88,99,210}; 
  35.         int index = Arrays.binarySearch(arr3,210);
  36.         if(index >= 0){
  37.             System.out.println(index);
  38.         }else{
  39.             System.out.println("找不到");
  40.         }    
  41.     }
  42. }

六、 数组使用中的常见异常

  1. package com.atguigu.java;
  2. /*
  3.     1.数组脚标越界异常(ArrayIndexOutOfBoundsException)
  4.     2.空指针异常(NullPointerException)
  5. */
  6. public class ArrayExceptionTest {
  8.     public static void main(String[] args) {
  9.         //1.数组脚标越界异常(ArrayIndexOutOfBoundsException)
  10.         int[] arr = new int[]{1,2,3,4,5};
  12.         /*for(int i = 0;i <= arr.length;i++){
  13.             System.out.println(arr[i]);
  14.         }*/
  16.         //System.out.println(arr[-2]);
  18.         //2.空指针异常(NullPointerException)
  19.         //情况一：
  20.         /*int[] arr1 = new int[]{1,2,3};
  21.         arr1 = null;
  22.         System.out.println(arr1[0]);*/
  24.         //情况二：
  25.         /*int[][] arr2 = new int[4][];
  26.         System.out.println(arr2[0]);//null
  27.         System.out.println(arr2[0][0]);//空指针异常
  28. */        
  29.         //情况三：
  30.         /*String[] arr3 = new String[]{"AA","BB","CC"};
  31.         arr3[0] = null;
  32.         System.out.println(arr3[0].toString());//空指针异常
  33. */    
  34.     }
  35. }