Java学习笔记（五）——数组、排序和查找

一、数组

数组可以存放多个同一类型的数据。数组也是一种数据类型，是引用类型。即数组就是一组数据。

（一）数组的使用

1、使用方式1——动态初始化

（1）数组的定义：数据类型数组名[] = new 数据类型[大小]

或数据类型[] 数组名 = new 数据类型[大小]

int a[] = new int[5];

（2）数组的引用（使用）：数组名[下标/索引/index]

import java.util.Scanner;
public class Array02{public static void main(String[] args){Scanner myScanner = new Scanner(System.in);double scores[] = new double[5];for(int i = 0; i < scores.length; i++){System.out.print("请输入第" + (i + 1) + "个元素的值：");scores[i] = myScanner.nextDouble();}System.out.println("当前数组的值如下:");for(int i = 0; i < scores.length; i++){System.out.print(scores[i] + " ");}}
}

2、使用方式2——动态初始化

（1）先声明数组：数据类型数组名[]; 或数据类型[] 数组名;

int a[];

（2）创建数组：数组名 = new 数据类型[大小];

a = new int[10];

import java.util.Scanner;
public class Array03{public static void main(String[] args){Scanner myScanner = new Scanner(System.in);double scores[]; //声明数组，这时scores是nullscores = new double[5]; // 分配内存空间，可以存放数据for(int i = 0; i < scores.length; i++){System.out.print("请输入第" + (i + 1) + "个元素的值：");scores[i] = myScanner.nextDouble();}System.out.println("当前数组的值如下:");for(int i = 0; i < scores.length; i++){System.out.print(scores[i] + " ");}}
}

3、使用方式3——静态初始化

（1）初始化数组：数据类型数组名[] = {元素值,元素值...}

int a[] = {2,5,6,7,8,89,90,34,56}

上面的用法相当于：int a[] = new int[9];

a[0] = 2; a[1] = 5; a[2] = 6; a[3] = 7; a[4] = 8; a[5] = 89; a[6] = 90; a[7] = 34; a[8] = 56;


public class Array01{public static void main(String[] args){double hens[] = {3, 5, 1, 3.4, 2, 50};double sum = 0;for(int i = 0; i < hens.length; i++){sum += hens[i];}System.out.println("sum=" + sum + ",avg=" + sum/hens.length);}
}

（二）数组使用注意事项和细节

1、数组是多个相同类型数据的组合，实现对这些数据的统一管理。

2、数组中的元素可以是任何数据类型，包括基本类型和引用类型，但是不能混用。

3、数组创建后，如果没有赋值，有默认值。int 0,short 0,byte 0,long 0,float 0.0,double 0.0,

char \u0000,boolean false,String null

4、使用数组的步骤：（1）声明数组并开辟空间（2）给数组各个元素赋值（3）使用数组

5、数组的下标是从0开始的。

6、数组下标必须在指定范围内使用，否则报下标越界异常，比如int arr[] = new int[5];的有效下标为0-4。

7、数组属于引用类型，数组型数据是对象（object）

（三）数组赋值机制

1、基本数据类型赋值，这个值就是具体的数据，而且相互不影响。（值传递/值拷贝）

2、数组在默认情况下是引用传递，赋的值是地址。

public class Array06{public static void main(String[] args){int arr1[] = {1,2,3,4,5};int arr2[] = arr1;arr2[0] = 10;for(int i = 0; i < arr1.length; i++){System.out.print(arr1[i] + " ");}}
}

（四）数组拷贝

将arr1拷贝到arr2，要求数据空间是独立的。

public class Array07{public static void main(String[] args){int arr1[] = {1,2,3};// 开辟一个和arr1一样大的数组int arr2[] = new int[arr1.length];for(int i = 0; i < arr1.length; i++){arr2[i] = arr1[i];}// 修改arr2[0]arr2[0] = 10;// 修改arr2不会影响arr1System.out.print("arr1的元素为：");for(int i = 0; i < arr1.length; i++){System.out.print(arr1[i] + " ");}System.out.println();System.out.print("arr2的元素为：");for(int i = 0; i < arr2.length; i++){System.out.print(arr2[i] + " ");}}
}

（五）数组反转

public class Array08{public static void main(String[] args){int arr[] = {1,2,3,4,5};int temp = 0;int len = arr.length;for(int i = 0; i < len/2; i++){temp = arr[i];arr[i] = arr[len - 1 - i];arr[len - 1 - i] = temp;}for(int i = 0; i < len; i++){System.out.print(arr[i] + " ");}}
}

（六）数组扩容

要求：动态地给数组添加元素效果，实现对数组扩容。

（1）原始数组使用静态分配 int arr[] = {1,2,3};

（2）增加元素4，直接放在数组的最后

（3）用户可以通过如下方法来决定是否继续添加，添加成功，是否继续？y/n

public class Array09{public static void main(String[] args){int arr[] = {1,2,3};int arrNew[] = new int[arr.length + 1];for(int i = 0; i < arr.length; i++){arrNew[i] = arr[i];}arrNew[arrNew.length - 1] = 4;arr = arrNew;System.out.print("arr数组的元素为：");for(int i = 0; i < arr.length; i++){System.out.print(arr[i] + " ");}}
}

// 数组扩容
import java.util.Scanner;
public class Array10{public static void main(String[] args){int arr[] = {1,2,3};char choose = 'n';do{System.out.print("请输入需要添加的数字：");Scanner myScanner = new Scanner(System.in);int newNum = myScanner.nextInt();int arrNew[] = new int[arr.length + 1];for(int i = 0; i < arr.length; i++){arrNew[i] = arr[i];}arrNew[arrNew.length - 1] = newNum;arr = arrNew;System.out.print("添加后的数组元素如下:");for(int i = 0; i < arr.length; i++){System.out.print(arr[i] + " ");}System.out.println();System.out.print("是否继续添加(y/n)：");choose = myScanner.next().charAt(0);}while(choose == 'y');}
}

使用链表可以优化

（七）数组缩减

要求：有一个数组，可以将该数组进行缩减，提示用户是否继续缩减，每次缩减最后那个元素。当只剩下最后一个元素，提示不能再缩减。

// 数组缩减
import java.util.Scanner;
public class Array11{public static void main(String[] args){int arr[] = {1,2,3,4,5,6,7};System.out.print("当前的数组元素如下:");for(int i = 0; i < arr.length; i++){System.out.print(arr[i] + " ");}System.out.println();System.out.print("是否缩减数组(y/n)：");Scanner myScanner = new Scanner(System.in);char choose = myScanner.next().charAt(0);while(choose == 'y'){if(arr.length == 1){System.out.print("数组元素只剩一个，不能再继续缩减");break;}int arrNew[] = new int[arr.length - 1];for(int i = 0; i < arrNew.length; i++){arrNew[i] = arr[i];}arr = arrNew;System.out.print("缩减后的数组元素如下:");for(int i = 0; i < arr.length; i++){System.out.print(arr[i] + " ");}System.out.println();System.out.print("是否继续缩减(y/n)：");choose = myScanner.next().charAt(0);}}
}

二、排序

排序是将一群数据，依指定的顺序进行排列的过程。

排序的分类：

1、内部排序：指将需要处理的所有数据都加载到内部存储器中进行排序，包括交换式排序法、选择式排序法和插入式排序法。

2、外部排序：数据量过大，无法全部加载到内存中，需要借助外部存储进行排序，包括合并排序法和直接合并排序法。

冒泡排序

基本思想：通过对待排序列从后向前（从下标较大的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就像水底下的气泡一样逐渐向上冒。

// 冒泡排序
import java.util.Scanner;
public class BubbleSort{public static void main(String[] args){int arr[] = {24,69,80,57,13};int temp;for(int i = 0; i < arr.length; i++){for(int j = 0; j < arr.length - i - 1; j++){if(arr[j] > arr[j + 1]){temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}for(int i = 0; i < arr.length; i++){System.out.print(arr[i] + " ");}}
}

三、查找

常用的查找有两种：顺序查找、二分查找

顺序查找

案例：有一个数列：白眉鹰王、金毛狮王、紫衫龙王、青翼蝠王。猜数游戏：从键盘中任意输入一个名称，判断数列中是否包含此名称。要求：如果找到了，就提示找到，并给出下标值。

// 顺序查找
import java.util.Scanner;
public class SeqSearch{public static void main(String[] args){String arr[] = {"白眉鹰王","金毛狮王","紫衫龙王","青翼蝠王"};System.out.print("请输入名字：");Scanner myScanner = new Scanner(System.in);String name = myScanner.next();boolean flag = true;for(int i = 0; i < arr.length; i++){if(name.equals(arr[i])){System.out.println("已找到该名字，下标值为：" + i);flag = false;break;}}if(flag){System.out.println("找不到该名字");}}
}

四、多维数组——二维数组

（一）二维数组的使用

1、使用方式1——动态初始化

语法：类型数组名[][] = new 类型[大小][大小]

int a[][] = new int[2][3];

2、使用方式2——动态初始化

（1）先声明：类型数组名[][];

（2）再定义（开辟空间）数组名[][] = new 类型[大小][大小];

（3）赋值（有默认值）

3、使用方式3——动态初始化——列数不确定

动态创建下面二维数组：

public class TwoDimensionArray02{public static void main(String[] args){int arr[][] = new int[3][];for(int i = 0; i < arr.length; i++){arr[i] = new int[i + 1];for(int j = 0; j < arr[i].length; j++){arr[i][j] = i + 1;}}for(int i = 0; i < arr.length; i++){for(int j = 0; j < arr[i].length; j++){System.out.print(arr[i][j] + " ");}System.out.println();}}
}

4、使用方式4——静态初始化

public class TwoDimensionArray01{public static void main(String[] args){int arr[][] = {{0, 0, 0, 0, 0, 0},{0, 0, 1, 0, 0, 0},{0, 2, 0, 3, 0, 0},{0, 0, 0, 0, 0, 0}};for(int i = 0; i < arr.length; i++){for(int j = 0; j < arr[i].length; j++){System.out.print(arr[i][j] + " ");}System.out.println();}}
}