Arrays工具类

Arrays工具类的概述

• Java中提供了一个数组工具类：java.util.Arrays。
• Arrays是一个工具类，其中有一个sort()方法，可以进行排序。sort()方法是一个静态方法，直接使用类名调用就好。

sort方法的使用

public class ArraysTest01 {
    public static void main(String[] args) {
        int[] arr={1,3,2,7,4,9,6};
//        工具类中的方法带部分都是静态的
        Arrays.sort(arr);
//        遍历输出排序后的数组元素
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

冒泡排序

• 每一次循环结束后，都要找出最大数据，放到参与比较的这堆数据的最右边。（冒出最大的那个气泡）
• 核心：拿着左边的数字和右边的数字进行比对，当 “左边 > 右边” 的时候，交换位置。

public class BubbleSort {
    public static void main(String[] args) {
//        这是int类型的数组对象
        int[] arr = {9, 8, 10, 7, 6, 0, 11};
//        经过冒泡排序算法对以上数组中的元素进行排序
//      7条数据，循环6次。以下的代码可以循环6次。（冒泡排序的外层采用这种方式）
        int count = 0;
        int count2 = 0;
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
//                不管是否需要交换位置，总之是要比较一次的
                count++;
                if (arr[j] > arr[j + 1]) {
                    int temp;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    count2++;
                }
            }
        }
        System.out.println("比较的次数：" + count);//21
        System.out.println("元素交换次数：" + count2);//13
//       输出遍历后的结果
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

选择排序

• 每一次从这堆“参与比较的数据当中”找出最小值，拿着这个最小值和“参与比较的这堆最前面的元素”交换位置。
• 选择排序比冒泡排序好在：每一次的位置交换都是有意义的。
• 关键点：选择排序的关键在于，怎么找出一堆数据中最小的元素。
• 冒泡排序和选择排序实际上比较的次数相同，相比较而言，选择排序的在排序过程中的交换位置的次数减少了。

public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 10, 7, 6, 0, 11};
//        选择排序
//        5条数据循环4次（外层循环4次）
        int count = 0;
        int count2 = 0;
        for (int i = 0; i < arr.length - 1; i++) {
//            i正好是“参与比较的这堆数据中”最左边那个元素的下标。
//            i是一个参与比较的这堆数据中的起点下标
//            假设起点i下标位置上的元素是最小的
            int min = i;
            for (int j = i + 1; j < arr.length; j++) {
                count++;
                if (arr[j] < arr[min]) {
                    min = j;//最小元素的下标是j
                }
            }
//            当i和min相等时，表示最初猜测是对的
//            当i和min不相等时，表示最初猜测是错的，有比这个元素更小的元素
//            需要拿着这个更小的元素和最左边的元素进行交换
            if (min != i) {
//                表示存在更小的数据，arr[min]是最小的数据，arr[i]是最左边的数据
                int temp;
                temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
                count2++;
            }

        }
        System.out.println("比较次数：" + count);//21
        System.out.println("元素交换次数：" + count2);//5
//        排序之后的遍历输出
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

数组元素的查找

• 数组元素的查找有两种方式：

  • 第一种方式：一个一个挨着找，直到找到为止。
  • 第二种方式：二分查找（算法），这个效率较高。

• 第一种查找方式的实现

  public class ArraySearch {
      public static void main(String[] args) {
  //        使用第一种查找方式
          int[] arr = {4, 5, 6, 87, 8};
  //        需求：找出87的下标，如果没有返回-1
  //        一个一个挨着找
          for (int i = 0; i < arr.length; i++) {
              if (arr[i] == 87) {
                  System.out.println("87元素的下标是：" + i);
                  return;
              }
          }
  //        程序执行到此处，表示没有87这个元素。
          System.out.println("87这个元素不存在！");//3
      }
  }
  

• 对第一种查找方式中的方法进行封装改良

  public class ArraySearch {
      public static void main(String[] args) {
  //        使用第一种查找方式
          int[] arr = {4, 5, 6, 87, 8};
  //        需求：找出87的下标，如果没有返回-1
  //       对以上程序进行封装。思考：传什么参数？返回什么值？
  //        传什么：第一个参数是数组；第二个参数是被查找的元素。
  //        返回值：返回被查找的这个元素的下标。如果找不到返回-1.
          int index = ArraySearch(arr, 87);
          System.out.println(index == -1 ? "该元素不存在" : "该元素的下标是：" + index);
      }
  
      /**
       * 从数组中检索某个元素的下标
       *
       * @param arr 被检索的数组
       * @param ele 被检索的元素
       * @return 大于等于0的数表示元素的下标，-1表示该元素不存在
       */
      public static int ArraySearch(int[] arr, int ele) {
          for (int i = 0; i < arr.length; i++) {
              if (ele == arr[i]) {
                  return i;
              }
          }
          return -1;
      }
  }
  

二分查找（折半查找）

• 二分法查找建立在排序的基础之上。没有排序的数据是无法查找的。

• 二分法查找效率要高于“一个挨着一个”的这种查找方式。

• 二分法查找原理

  10(0下标) 23 56 89 100 111 222 235 500 600(下标9) arr数组
  目标：找出600的下标
  (0 + 9) / 2 --> 4（中间元素的下标）

  arr[4]这个元素就是中间元素：arr[4]是 100
  100 < 600
  说明被查找的元素在100的右边。
  那么此时开始下标变成：4 + 1

  (5 + 9) / 2 --> 7（中间元素的下标）
  arr[7] 对应的是：235
  235 < 600
  说明被查找的元素在235的右边。

  开始下标又进行了转变：7 + 1
  (8 + 9) / 2 --> 8
  arr[8] --> 500
  500 < 600
  开始元素的下标又发生了变化：8 + 1
  (9 + 9) / 2 --> 9
  arr[9]是600，正好和600相等，此时找到了。

• 二分查找的代码实例演示

  public class ArrayUtil {
      public static void main(String[] args) {
          int[] arr = {100, 200, 230, 235, 600, 1000, 2000, 9999};
  //        找出arr这个数组中200所在的下标
  //        调用方法
          int index = binarySearch(arr, 200);
          System.out.println(index == -1 ? "该元素不存在" : "该元素的下标是：" + index);
      }
  
      /**
       * 从数组中查找目标元素的下标
       *
       * @param arr  被查找的数组（这个数组必须是已经排序过的）
       * @param dest 被查找的目标元素
       * @return 大于等于0的数表示元素的下标，-1表示该元素不存在
       */
      private static int binarySearch(int[] arr, int dest) {
          int begin = 0;//开始下标
          int end = arr.length - 1;//结束下标
          while (begin <= end) {//开始元素的下标只要在结束元素下标的左边就有机会继续循环
              int mid = (begin + end) / 2;//中间的下标
              if (arr[mid] == dest) {
                  return mid;
              } else if (arr[mid] < dest) {
  //            目标在“中间”的右边
  //            开始元素的下标需要发生改变（开始元素的下标需要重新赋值）
                  begin = mid + 1;
  
              } else {
  //            arr[mid] > dest
  //            目标在"中间"的左边
  //            修改结束的元素的下标
                  end = mid - 1;
              }
          }
          return -1;
      }
  }
  

使用Arrays工具类进行排序和二分查找

public class ArrayTest02 {
    public static void main(String[] args) {
        int[] arr = {3, 6, 5, 12, 7, 9, 4, 1};
//        使用Arrays工具类进行排序
        Arrays.sort(arr);
//        打印输出排序后的数组
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
//        使用Arrays工具类进行二分法查找（建立在排序基础之上）
        int index = Arrays.binarySearch(arr, 7);
        System.out.println(index == -1 ? "该元素不存在" : "该元素下标是：" + index);
    }
}