Arrays类、冒泡排序、选择排序、插入排序、稀疏数组！

一、Arrays类

1、数组的工具类：java.util.Arrays;
2、Arrays类中的方法都是static修饰的静态方法，在使用的时候可以直接使用类名进行调用，而不用使用对象来调用（注意：是“不用”，不是“不能”）
3、常用功能：

1. 给数组赋值：通过fill方法；
2. 对数组排序：sort方法，按升序；
3. 比较数组：通过equals方法比较数组中元素值是否相等；
4. 查找数组元素：通过binarySearch方法能对排序好的数组进行二分查找发操作；

public static void main(String[] args) {
    
        int [] s = {
    2,3,333,55,67,8};
        //打印数组元素：Arrays.toString
        System.out.println(java.util.Arrays.toString(s));
        //打印元素方法
        printArrays(s);
        //升序输出
        java.util.Arrays.sort(s);
        System.out.println(java.util.Arrays.toString(s));
        //填充,索引2-4之间填充为0
        java.util.Arrays.fill(s,2,4,0);
        System.out.println(java.util.Arrays.toString(s));//[2, 3, 0, 0, 67, 333]
        
    }

    //打印元素方法
    public static void printArrays(int [] arrays){
    
        for (int i = 0; i < arrays.length; i++) {
    
            if (i == 0){
    
                System.out.print("[");
            }
            if (i == arrays.length - 1){
    
                System.out.print(arrays[i]+"]");
            }else {
    
                System.out.print(arrays[i]+",");
            }

        }
    }

二、冒泡排序（重点）

1、两个相邻的位置进行大小比较，谁小或者谁大，就交换位置；
2、两层循环，外层冒泡轮数，里层依次比较；
3、算法的时间复杂度为O(n2);

public static void main(String[] args) {
    
        //冒泡排序
        //1、比较数组中相邻的元素，如果第一个比第二个大，就交换位置
        //2、每一次比较，都会产生一个较大或者较小的数字
        //3、下一轮，可以减小一次排序
        int [] a = {
    12,4,6,2,9,0};
        System.out.println(Arrays.toString(a));

    }

    public  static int[] sort(int [] arrays){
    
        //临时变量
        int temp = 0;
        //外层循环。判断走多少次
        for (int i = 0; i < arrays.length - 1; i++) {
    
            boolean flag = false;//通过标志位来减少没有意义的比较
               //内层循环，比较大小，如果第二个数比第一个数大，就交换位置,从大到小
            for (int j = 0; j < arrays.length - 1 - i; j++) {
    
                if (arrays[j+1] > arrays[j]){
    
                      temp = arrays[j];
                      arrays[j] = arrays[j + 1];
                      arrays[j + 1] = temp;
                      flag = true;
                }
            }
            if (flag){
    
                break;
            }
        }
        return arrays;
    }

三、选择排序（Select Sort）

1、通过确定一个 Key 最大或最小值，再从带排序的的数中找出最大或最小的交换到对应位置。再选择次之。双重循环时间复杂度为 O(n^2)；

 public static void main(String[] args) {
    
        //每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕
        //给定数组：int[] arr={
    里面n个数据}；
        // 第1趟排序，在待排序数据arr[1]~arr[n]中选出最小的数据，将它与arrr[1]交换；
        // 第2趟，在待排序数据arr[2]~arr[n]中选出最小的数据，将它与r[2]交换；以此类推，
        // 第i趟在待排序数据arr[i]~arr[n]中选出最小的数据，将它与r[i]交换，直到全部排序完成。
        int [] a = {
    12,4,6,2,9,0};
        System.out.println(Arrays.toString(arrays(a)));


    }

    public static int[] arrays(int[]arrays){
    
        //外层循环控制轮数
        for (int i = 0; i < arrays.length - 1; i++) {
    
            int minKey = i;
            //先找最小的位置
            for (int j = minKey + 1; j < arrays.length; j++) {
    
                if (arrays[j] < arrays[minKey]){
    //如果后面的比前面的小
                    minKey = j;  //定位最小的数
                }
            }
            //在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
            for (int j = 0; j < arrays.length - 1; j++) {
    
                if (minKey != i){
    
                    int temp = arrays[i];
                    arrays[i] = arrays[minKey];
                    arrays[minKey] = temp;
                }
            }

        }
        return arrays;
    }

四、插入排序

1、通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

//    1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
//    2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。
//    （如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

    public static void main(String[] args) {
    
        int sourceArray[] = {
    9, 2, 1, 90, 33};
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < arr.length; i++) {
    
            // 记录要插入的数据
            int tmp = arr[i];
            // 从已经排序的序列最右边的开始比较，找到比其小的数
            int j = i;
            while (j > 0 && tmp < arr[j - 1]) {
    
                arr[j] = arr[j - 1];
                j--;
            }
            // 存在比其小的数，插入
            if (j != i) {
    
                arr[j] = tmp;
            }
        }
        for (int i = 0; i < arr.length; i++) {
    
            System.out.print(arr[i] + "\t");
        }

    }

五、稀疏数组

1、当一个数组中大部分元素是0，或者为同一值的数组时，可以用稀疏数组来保存该数组；
2、稀疏数组的处理方式是：
记录数组一共有几行几列，有多少个不同值；
把具有不同值的元素和行列及值记录在一个小规模中，从而缩小程序的规模；
3、下图，左边是原始数组，右边是稀疏数组 ；

public static void main(String[] args) {
    
        //定义一个十一行十一列二维数组
        int [][] arrays1 = new int[11][11];
        arrays1[0][4] = 1;
        arrays1[5][6] = 2;

        //输出二维数组
        for (int[] ints : arrays1) {
    
            for (int anInt : ints) {
    
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }

        System.out.println("================");

        //找到上面二位数组中不为0的个数
        int sum = 0;
        for (int[] ints : arrays1) {
    
            for (int anInt : ints) {
    
                if (anInt != 0){
    
                    sum++;
                }
            }
        }

        //定义一个稀疏数组，稀疏数组固定3列(原始数组的行，列，值)
        int [][] arrays2 = new int[sum + 1][3];

        //稀疏数组的头部，就是原数组的行数，列数，不同的值的个数
        arrays2[0][0] = 11;
        arrays2[0][1] = 11;
        arrays2[0][2] = sum;

        //遍历二维数组，将非0的值存放在稀疏数组中
        int count = 0;//计数器，拿出原数组不为0的值的横坐标
        for (int i = 0; i < arrays1.length; i++) {
    
            for (int j = 0; j < arrays1[i].length ; j++) {
    
                  if (arrays1[i][j] != 0){
    
                      count++;
                      arrays2[count][0] = i;
                      arrays2[count][1] = j;
                      arrays2[count][2] = arrays1[i][j];
                  }
            }
        }

        //输出稀疏数组
        for (int i = 0; i < arrays2.length; i++) {
    
            System.out.println(arrays2[i][0] + "\t" +
                    arrays2[i][1] + "\t" +
                    arrays2[i][2] + "\t" );
        }

        System.out.println("=============");

        //将稀疏数组还原成原始数组
        int [][]array3 = new int[arrays2[0][0]][arrays2[0][1]];

        for (int i = 1; i < arrays2.length; i++) {
    
            array3[arrays2[i][0]][arrays2[i][1]] = arrays2[i][2];
        }
        //打印
       //输出原始二维数组
        for (int[] ints : array3) {
    
            for (int anInt : ints) {
    
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }