分类

040_数组

JAVA学习网 2020-11-03 23:13:02

目录

数组

https://www.bilibili.com/video/BV12J41137hu/?p=51

数组的定义

数组是相同类型数据的有序集合。

数组的创建

//静态初始化
int[] nums1 = {1,2,3};
//动态初始化
int[] nums2 = new int[10];
nums2[0] = 1;
nums2[1] = 2;

数组的特点

  1. 其长度是确定的。数组一旦被创建，它的大小是不可改变的。
  2. 其元素必须是相同类型，不允许出现混合类型。
  3. 数组中的元素可以是任何数据类型，包括基本类型和引用类型。
  4. 数组变量属引用类型，数组可以看成是对象，数组中的每个元素相当于该对象的成员变量。数组本身就是对象，Java中对象是在堆中的，因此数组无论保存的是基本类型还是引用类型，数组对象本身是在堆中。

数组的使用

  1. for循环或for-each循环
  2. 数组作方法入参
  3. 数组作为返回值

二维数组

int[][] nums = {{1,2},{2,3},{3,4}};
int[][] nums = new int[3][2];
nums[0] = {1,2};
nums[0][0] = 1;

Arrays类

  1. 数组的工具类java.util.Arrays。
  2. 查看jdk帮助文档或查看源码。

冒泡排序

package com.qing.array;

import java.util.Arrays;

public class Demo01 {
    public static void main(String[] args) {
        int[] array = {12,455,22,23,25,3,443,44};
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(sort(array)));
    }
    /*
    冒泡排序
    1.从前开始两两比较，大的交换
    2.外层循环：循环的轮数，长度-1，最后一位不需要比较
    3.内层循环：比较的次数，第一次长度-1，依次递减，比较一次会产生最大值，不需要再比较
     */
    public static int[] sort(int[] array) {
        int temp = 0;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
}

[12, 455, 22, 23, 25, 3, 443, 44]
[3, 12, 22, 23, 25, 44, 443, 455]

简单优化

package com.qing.array;

import java.util.Arrays;

public class Demo01 {
    public static void main(String[] args) {
//        int[] array = {12,455,22,23,25,3,443,44};
        int[] array = {12,45,12,11,125,133,143,144};
        System.out.println(Arrays.toString(array));
        System.out.println(Arrays.toString(sort(array)));
        int[] array1 = {12,45,12,11,125,133,143,144};
        System.out.println(Arrays.toString(sort1(array1)));
    }
    /*
    冒泡排序
    1.从前开始两两比较，大的交换
    2.外层循环：循环的轮数，长度-1，最后一位不需要比较
    3.内层循环：比较的次数，第一次长度-1，依次递减，比较一次会产生最大值，不需要再比较
    简单优化
    4.如果一轮比较都不交换，说明已成功排序，不需要再比较
     */
    public static int[] sort1(int[] array) {
        int temp = 0;
        int count = 0;
        for (int i = 0; i < array.length - 1; i++) {
            boolean flag = true;
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                    flag = false;
                }
            }
            count+=1;
            if (flag) {
                System.out.println("sort1循环轮数：" + (count));
                return array;
            }
        }
        System.out.println("sort1循环轮数：" + (count));
        return array;
    }
    /*
    冒泡排序
    1.从前开始两两比较，大的交换
    2.外层循环：循环的轮数，长度-1，最后一位不需要比较
    3.内层循环：比较的次数，第一次长度-1，依次递减，比较一次会产生最大值，不需要再比较
     */
    public static int[] sort(int[] array) {
        int temp = 0;
        int count = 0;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    temp = array[j + 1];
                    array[j + 1] = array[j];
                    array[j] = temp;
                }
            }
            count+=1;
        }
        System.out.println("sort循环轮数：" + (count));
        return array;
    }

}

[12, 45, 12, 11, 125, 133, 143, 144]
sort循环轮数：7
[11, 12, 12, 45, 125, 133, 143, 144]
sort1循环轮数：4
[11, 12, 12, 45, 125, 133, 143, 144]

稀疏数组

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

image.png

package com.qing.array;

public class Demo02 {
    public static void main(String[] args) {
        //1. 创建一个二维数组，记录棋局，11 * 11 ，0：没有棋子，1：黑棋，2：白棋
        int[][] arr1 = new int[11][11];
        arr1[1][2] = 1;
        arr1[2][3] = 2;
        System.out.println("输出原始的数组");
        for (int[] ints : arr1) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
        System.out.println("=========================");
        /*
        2. 转换为稀疏数组
        稀疏数组的列数为3，行数为原始数组有效值+1。
        第一行记录数组一共有几行几列，有多少个不同值。
         */
        int sum = 0;
        //计算原始数组有效值
        for (int[] ints : arr1) {
            for (int anInt : ints) {
                if (anInt != 0) {
                    sum ++;
                }
            }
        }
        System.out.println("原始数组有效值：" + sum);
        //稀疏数组的列数为3，行数为原始数组有效值+1。
        //第一行记录数组一共有几行几列，有多少个不同值。
        int[][] arr2 = new int[sum + 1][3];
        arr2[0][0] = 11;
        arr2[0][1] = 11;
        arr2[0][2] = sum;
        int count = 1;
        //记录有效值的行，列，值
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1[i].length; j++) {
                if (arr1[i][j] != 0) {
                    arr2[count][0] = i;
                    arr2[count][1] = j;
                    arr2[count][2] = arr1[i][j];
                    count++;
                }
            }
        }
        System.out.println("输出稀疏数组");
        for (int[] ints : arr2) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
        System.out.println("===================");
        //3. 还原原始数组
        int[][] arr3 = new int[arr2[0][0]][arr2[0][1]];
        for (int i = 1; i < arr2.length; i++) {
            arr3[arr2[i][0]][arr2[i][1]] = arr2[i][2];
        }
        System.out.println("输出还原的原始数组");
        for (int[] ints : arr3) {
            for (int anInt : ints) {
                System.out.print(anInt + "\t");
            }
            System.out.println();
        }
    }
}

输出原始的数组
0	0	0	0	0	0	0	0	0	0	0	
0	0	1	0	0	0	0	0	0	0	0	
0	0	0	2	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
=========================
原始数组有效值：2
输出稀疏数组
11	11	2	
1	2	1	
2	3	2	
===================
输出还原的原始数组
0	0	0	0	0	0	0	0	0	0	0	
0	0	1	0	0	0	0	0	0	0	0	
0	0	0	2	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	0
阅读(2344) 评论(0)