JAVA 基础学习之数组和算法

女爷i 2023-05-29 06:56 140阅读 0赞

# 数组 #

## 1、定义和特点 ##

###  1.1、定义 ###

数组是由相同类型的数据组成的有序集合。数组描述的是相同类型的若干个数据，按照一定的先后次序排列组合而成。

### 1.2、特点 ###

1.   数组的长度是确定的，一旦被创建大小不可更改。
2.   数组中的元素必须是相同类型的。
3.   数组类型可以是任何数据类型，包括基本类型和引用类型。

## 2、声明数组 ##

**   2.1****、数组的声明方式有两种(以一维数组为例)**

type[]   arr_name; //（推荐使用这种方式）
    type    arr_name[];

注意事项：

1. 声明数组时没有实例化数组对象，JVM不会分配空间的，只有当数组真正被实例化时，在这个时候才要指定数组的大小， JVM才会分配空间

2. 声明一个数组的时候并没有数组真正被创建。

3. 构造一个数组，必须指定长度。

示例：

public class TestArray {
       public static void main(String[] args) {
    	   int[] s=new int[10];
    	   for (int j = 0; j < s.length; j++) {
    		   s[j]=2*j+1;
    	   }
    	   System.out.println(Arrays.toString(s));
      }
    }

数组的内存分析图

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU2MDM0Mg_size_16_color_FFFFFF_t_70][] ##

# #

## 3、初始化 ##

初始化分为三种：静态初始化、动态初始化、默认初始化。

### 3.1、静态初始化 ###

> int\[\] a=\{1,2,3,4,5\};//静态初始化

### 3.2、动态初始化 ###

> int\[\]  a=new int\[2\];//动态初始化 i
> 
> nt\[0\]=1;
> 
> int\[1\]=2;

### 3.3、默认初始化 ###

> int a2\[\] = new int\[2\]; // 默认值：0,0
> 
> boolean\[\] b = new boolean\[2\]; // 默认值：false,false
> 
> String\[\] s = new String\[2\]; // 默认值：null, null

## 4、数组的循环遍历 ##

### 4.1、使用for循环遍历初始化和遍历数组 ###

public class Test {
        public static void main(String[] args) {
            int[] a = new int[4];
            //初始化数组元素的值
            for(int i=0;i<a.length;i++){
                a[i] = 100*i;
            }
            //读取元素的值
            for(int i=0;i<a.length;i++){
                System.out.println(a[i]);
            }
        }
    }

**4.2、for-each 循环**

增强for循环for-each是JDK1.5新增加的功能，专门用于读取数组或集合中所有的元素，即对数组进行遍历。

public class Test {
        public static void main(String[] args) {
            String[] ss = { "aa", "bbb", "ccc", "ddd" };
            for (String temp : ss) {
                System.out.println(temp);
            }
        }
    }

### 4.3、java.util.Arrays类 ###

JDK提供的java.util.Arrays类，包含了常用的数组操作，方便我们日常开发。Arrays类包含了：排序、查找、填充、打印内容等常见的操作。

**1、打印**

import java.util.Arrays;
    public class Test {
        public static void main(String args[]) {
            int[] a = { 1, 2 };
            System.out.println(a); // 打印数组引用的值；
            System.out.println(Arrays.toString(a)); // 打印数组元素的值；
        }
    }

**注意**：此处的Arrays.toString()方法是Arrays类的静态方法，不是前面讲的Object的toString()方法。

**2、排序**

import java.util.Arrays;
    public class Test {
        public static void main(String args[]) {
            int[] a = {1,2,323,23,543,12,59};
            System.out.println(Arrays.toString(a));
            Arrays.sort(a);
            System.out.println(Arrays.toString(a));
        }
    }

**3、查找**

import java.util.Arrays;
    public class Test {
        public static void main(String[] args) {
            int[] a = {1,2,323,23,543,12,59};
            System.out.println(Arrays.toString(a));
            Arrays.sort(a);   //使用二分法查找，必须先对数组进行排序;
            System.out.println(Arrays.toString(a));
            //返回排序后新的索引位置,若未找到返回负数。
            System.out.println("该元素的索引："+Arrays.binarySearch(a, 12)); 
        }
    }

**4、填充**

输出结果

![20191105145217869.png][]

**注意**：是将2到4之间的索引替换成100，包括2，不包括4 \[2,4)

### 4.4、多维数组 ###

多维数组可以看成以数组为元素的数组。可以有二维、三维、甚至更多维数组，但是实际开发中用的非常少。最多到二维数组(学习容器后，我们一般使用容器，二维数组用的都很少)。

4.4.1、声明

public class Test {
        public static void main(String[] args) {
            // Java中多维数组的声明和初始化应按从低维到高维的顺序进行
            int[][] a = new int[3][];
            a[0] = new int[2];
            a[1] = new int[4];
            a[2] = new int[3];
            // int a1[][]=new int[][4];//非法
        }
    }

4.4.2、静态初始化

public class Test {
        public static void main(String[] args) {
            int[][] a = { { 1, 2, 3 }, { 3, 4 }, { 3, 5, 6, 7 } };
            System.out.println(a[2][3]);
        }
    }

# 算法(排序和查找) #

##  1、冒泡排序的基础算法 ##

冒泡排序是最常用的排序算法，在笔试中也非常常见，能手写出冒泡排序算法可以说是基本的素养。

运行规则：

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

大家可以用如上思想，将下面的人按照身高从低到高重新排列：冒泡排序的基础算法：

![2019110514580018.png][]

//冒泡排序法
    	   int[] arr= {1,4,2,5,7,13,8,86,0};
    	   int temp;
    	   for(int i=0;i<arr.length;i++) {
    		   for(int j=0;j<arr.length-1-i;j++) {
    			   if(arr[j]>arr[j+1]) {
    				   temp=arr[j];
    				   arr[j]=arr[j+1];
    				   arr[j+1]=temp;
    			   }
    		   }
    	   }
    	   System.out.println(Arrays.toString(arr));

冒泡排序的优化算法：

int[] arr= {3, 1, 6, 2, 9, 0, 7, 4, 5, 8};
    	   int temp;
    	   boolean flag;
    	    for(int i=0;i<arr.length;i++) {
             flag=true;
        	for(int j=0;j<arr.length-1-i;j++) {
     			if(arr[j]>arr[j+1]) {
     				temp=arr[j];
     				arr[j]=arr[j+1];
     				arr[j+1]=temp;
     				flag=false;
     			}
     		   }	   
    	   if(flag) {
    		   break; 
    	   }
    			  
    	   }

## 2、二分查找法 ##

二分法检索(binary search)又称折半检索，二分法检索的基本思想是设数组中的元素从小到大有序地存放在数组(array)中，首先将给定值key与数组中间位置上元素的关键码(key)比较，如果相等，则检索成功;

否则，若key小，则在数组前半部分中继续进行二分法检索；

若key大，则在数组后半部分中继续进行二分法检索。

这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败。

二分法检索是一种效率较高的检索方法

比如，我们要在数组\[7, 8, 9, 10, 12, 20, 30, 40, 50, 80, 100\]中查询到10元素，过程如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU2MDM0Mg_size_16_color_FFFFFF_t_70 1][]

> **思路**：（思路很重要）
> 
>       将查找值与数组最中间的值比较，若查找的值跟中间值相等，就返回下标值，若查找值小于中间值，就把最左边到中间作为一个数组进行查找，若查找值大于中间值，就把中间到最右边作为一个数组进行查找。

**代码：**

public class TestArray {
       public static void main(String[] args) {
    	   int[] arr= {1,3,5,6,8,9,20,34};
    	   System.out.println(binary(arr,34));
      }
       public static int binary(int[] arr,int value) {
    	   int low = 0;
           int high = arr.length - 1;
           while(low<=high) {
        	   int mid=(low+high)>>>1;
               if(arr[mid]==value) {
            	  return mid;
               }else if(value>arr[mid]) {
            	   low=mid+1;
               }else {
            	   high=mid-1; 
               }
           }
           return -1;
       }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU2MDM0Mg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191105144647397.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU2MDM0Mg==,size_16,color_FFFFFF,t_70
[20191105145217869.png]: https://img-blog.csdnimg.cn/20191105145217869.png
[2019110514580018.png]: https://img-blog.csdnimg.cn/2019110514580018.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU2MDM0Mg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2019110514592326.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU2MDM0Mg==,size_16,color_FFFFFF,t_70