一.数组的概述
数组（Array），是多个相同类型数据按一定顺序排列的集合，并使用一个名字命名，通过编号的方式对这些数据进行统一管理。
数组的常见概念
数组名
下标（或索引）
元素
数组的长度
数组本身是引用数据类型，而数组中的元素可以是任何数据类型，包括基本数据类型和引用数据类型。
创建数组对象会在内存中开辟一整块连续的空间，而数组名中引用的是这个连续空间的首地址。
数组的长度一旦确定，就不能修改。
我们可以直接通过下标（或索引）的方式调用指定位置的元素，速度很快。
数组的分类
①：按照维度：一维数组，二维数组，三维数组
②：按照元素的数据类型分：基本数据类型元素的数组，引用类型元素的数组。
二.一维数组的使用
一维数组的声明方式：
type var[] 或 type[] var;
例如： int a[]; int[] a; double b[]; String[] c; //引用类型变量数组
Java语言中声明数组时不能指定其长度（数组中元素的数），例如：int a[5]; //非法
一维数组的初始化方式：
①动态初始化：数组声明且为数组元素分配空间与赋值的操作分开进行。
②静态初始化：在定义数组的同时就为数组元素分配空间并赋值。
数组的引用：
定义并用运算符new为之分配空间后，才可以引用数组中的每个元素。
数组元素的引用方式：数组名[元素下标]
数组元素小标可以是整型常量或整型表达式。如a[3] , b[i] , c[6 * i];
数组元素下标从0开始：长度为n的数组合法下标取值范围为：0--->n-1; 如int[] a =new int[3];可引用的数组元素为：a[0],a[1],a[2].
每个数组都有一个属性length指明他的长度，例如：a.length指明数组a的长度(元素个数)
数组一旦初始化，其长度是不可变的。
数组是引用类型，它的元素相当于类的成员变量，因此数组一经分配空间，其中的每个元素也被按照成员变量同样的凡是别隐式初始化。
例如：
从图中可以看到，我们创建了名为a的数，并为其开启空间长度为5但是没有赋值，但是我们可以打印里面的数据，所以可以看出我们创建的没有赋值的数组java自动给我们赋了值，都为0。
注意：
对于基本数据类型而言，默认初始化值各有不同。
对于引用数据类型而言，默认初始化值为null(注意与0不同)
例题：
//升景坊单间短期出租4个月，550元/月（水电煤公摊，网费35元/月），空调、卫生间、厨房齐全。
// 屋内均是IT行业人士，喜欢安静。所以要求来租者最好是同行或者刚毕业的年轻人，爱干净、安静
public class test1 {
public static void main(String[] args) {
int[] arr = new int[]{8,2,1,0,3};
int[] index = new int[]{2,0,3,2,4,0,1,3,2,3,3};
String tel = "";
for(int i = 0;i < index.length;i++){
tel += arr[index[i]];
}
System.out.println("联系方式：" + tel); //联系方式：18013820100
}
}
/*
*2. 从键盘读入学生成绩，找出最高分，
并输出学生成绩等级。
成绩>=最高分-10 等级为’A’
成绩>=最高分-20 等级为’B’
成绩>=最高分-30 等级为’C’
其余 等级为’D’
提示：先读入学生人数，根据人数创建int数组，
存放学生成绩。
*
*/
import java.util.Scanner;
public class ArrayDemo1 {
public static void main(String[] args) {
//1.使用Scanner，读取学生个数
Scanner scanner = new Scanner(System.in);
System.out.println("请输入学生人数：");
int number = scanner.nextInt();
//2.创建数组，存储学生成绩，动态初始化
int[] scores = new int[number];
int maxScore = 0;
//3.给数组中的元素赋值
System.out.println("请输入" + number + "个学生成绩");
for(int i = 0;i < scores.length;i++){
scores[i] = scanner.nextInt();
if(maxScore < scores[i]){
maxScore = scores[i];
}
}
//4.获取数组元素中的最大值：最高分
// int maxScore = 0;
// for(int i = 0;i < scores.length;i++){
// if(maxScore < scores[i]){
// maxScore = scores[i];
// }
// }
//5.根据每个学生成绩与最高分的差值，得到每个学生的等级，并输出等级和成绩
char level;
for(int i = 0;i < scores.length;i++){
if(maxScore - scores[i] <= 10){
level = 'A';
}else if(maxScore - scores[i] <= 20){
level = 'B';
}else if(maxScore - scores[i] <= 30){
level = 'C';
}else{
level = 'D';
}
System.out.println("student " + i + "score is " + scores[i] + ", grade is " + level);
}
}
}三.多维数组的使用
对于二维数组的理解，我们可以看成是一维数组array1又作为另一个一维数组array2的水元素而存在。其实，从数组底层的运行机制来看，其实没有多维数组的。
二维数组：数组中的数组
初始化方式有两种（动态初始化和静态初始化）
动态初始化（格式一）：int[][] arr = new int[3][2];
定义了名称为arr的二维数组
二维数组中有3个一维数组
每一个一维数组中有2个元素
一维数组的名称分别是：arr[0],arr[1],arr[2].
给第一个一维数组1脚标赋值为78写法是：arr[0][1] = 78.
动态初始化(格式二)：intp[][] = new int[3][];
二维数组中有3个一维数组
每一个一维数组都是默认初始化值null（注意：区别于格式1）
可以对这三个一维数组分别进行初始化
arr[0] = new int[3]; arr[1] = new int[1]; arr[2] = new int[2];
注意： int[] []arr = new int[][3]; //非法
静态初始化：int[][] arr = new int[][]{{3,8,2}{2,7}{9,0,1,6}};
定义一个名称为arr的二维数组，二维数组中有三个一维数组
每定义一个一维数组中具体元素也都已初始化
第一个一维数组 arr[0] = {3,8,2}
第二个一维数组 arr[1] = {2,7}
第三个一维数组 arr[2] = {9,0,1,6}
第三个一维数组的长度的表示方式：arr[2].length;
注意特殊写法：int[] x,y[];x是一维数组，y是二维数组
java中多维数组不必都是规则矩阵形式。
/*
* 二维数组的使用
*
* 1.理解：
* 对于二维数组的理解，我们可以看成是一维数组array1又作为另一个一维数组array2的元素而存在。
* 其实，从数组底层的运行机制来看，其实没有多维数组。
*
* 2. 二维数组的使用:
* ① 二维数组的声明和初始化
* ② 如何调用数组的指定位置的元素
* ③ 如何获取数组的长度
* ④ 如何遍历数组
* ⑤ 数组元素的默认初始化值 :见 ArrayTest3.java
* ⑥ 数组的内存解析 :见 ArrayTest3.java
*
*
*/
public class ArrayTest2 {
public static void main(String[] args) {
//1.二维数组的声明和初始化
int[] arr = new int[]{1,2,3};//一维数组
//静态初始化
int[][] arr1 = new int[][]{{1,2,3},{4,5},{6,7,8}};
//动态初始化1
String[][] arr2 = new String[3][2];
//动态初始化2
String[][] arr3 = new String[3][];
//错误的情况
// String[][] arr4 = new String[][4];
// String[4][3] arr5 = new String[][];
// int[][] arr6 = new int[4][3]{{1,2,3},{4,5},{6,7,8}};
//也是正确的写法：
int[] arr4[] = new int[][]{{1,2,3},{4,5,9,10},{6,7,8}};
int[] arr5[] = {{1,2,3},{4,5},{6,7,8}};
//2.如何调用数组的指定位置的元素
System.out.println(arr1[0][1]);//2
System.out.println(arr2[1][1]);//null
arr3[1] = new String[4];
System.out.println(arr3[1][0]);//null
//3.获取数组的长度
System.out.println(arr4.length);//3
System.out.println(arr4[0].length);//3
System.out.println(arr4[1].length);//4
//4.如何遍历二维数组
for(int i = 0;i < arr4.length;i++){
for(int j = 0;j < arr4[i].length;j++){
System.out.print(arr4[i][j] + " ");
}
System.out.println();
}
}
}
package com.atguigu.java;
/*
* 二维数组的使用：
* 规定：二维数组分为外层数组的元素，内层数组的元素
* int[][] arr = new int[4][3];
* 外层元素：arr[0],arr[1]等
* 内层元素：arr[0][0],arr[1][2]等
*
* ⑤ 数组元素的默认初始化值
* 针对于初始化方式一：比如：int[][] arr = new int[4][3];
* 外层元素的初始化值为：地址值
* 内层元素的初始化值为：与一维数组初始化情况相同
*
* 针对于初始化方式二：比如：int[][] arr = new int[4][];
* 外层元素的初始化值为：null
* 内层元素的初始化值为：不能调用，否则报错。
*
* ⑥ 数组的内存解析
*
*/
public class ArrayTest3 {
public static void main(String[] args) {
int[][] arr = new int[4][3];
System.out.println(arr[0]);//[I@15db9742
System.out.println(arr[0][0]);//0
// System.out.println(arr);//[[I@6d06d69c
System.out.println("*****************");
float[][] arr1 = new float[4][3];
System.out.println(arr1[0]);//地址值
System.out.println(arr1[0][0]);//0.0
System.out.println("*****************");
String[][] arr2 = new String[4][2];
System.out.println(arr2[1]);//地址值
System.out.println(arr2[1][1]);//null
System.out.println("*****************");
double[][] arr3 = new double[4][];
System.out.println(arr3[1]);//null
// System.out.println(arr3[1][0]);//报错
}
}
public class test1 {
public static void main(String[] args) {
int[][] arr = new int[][]{ {3,5,8},{12,9},{7,0,6,4} };
int sum = 0;
for(int i = 0;i < arr.length;i++){
for(int j = 0; j < arr[i].length;j++){
sum += arr[i][j];
}
}
System.out.println(sum);
}
}
/*
* 使用二维数组打印一个 10 行杨辉三角。 【提示】
1. 第一行有 1 个元素, 第 n 行有 n 个元素
2. 每一行的第一个元素和最后一个元素都是 1
3. 从第三行开始, 对于非第一个元素和最后一个元素的元素。即：
yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
*
*/
public class YangHuiTest {
public static void main(String[] args) {
//1.声明并初始化二维数组
int[][] yanghui = new int[10][];
//2.给数组的元素赋值
for(int i = 0;i < yanghui.length;i++){
yanghui[i] = new int[i + 1];
//2.1给首末元素赋值
yanghui[i][0] = 1;
yanghui[i][i] = 1;
//2.2给每行的首末元素赋值
if(i > 1){
for(int j = 1;j < yanghui[i].length - 1;j++){
yanghui[i][j] = yanghui[i - 1][j - 1] + yanghui[i - 1][j];
}
}
}
//3.遍历二维数组
for(int i = 0;i < yanghui.length;i++){
for(int j = 0;j < yanghui[i].length;j++){
System.out.print(yanghui[i][j] + " ");
}
System.out.println();
}
}
}
/*
* 数组中的常见异常：
* 1. 数组角标越界的异常：ArrayIndexOutOfBoundsExcetion
*
* 2. 空指针异常：NullPointerException
*
*/
public class ArrayExceptionTest {
public static void main(String[] args) {
//1. 数组角标越界的异常：ArrayIndexOutOfBoundsExcetion
int[] arr = new int[]{1,2,3,4,5};
// for(int i = 0;i <= arr.length;i++){
// System.out.println(arr[i]);
// }
// System.out.println(arr[-2]);
// System.out.println("hello");
//2.2. 空指针异常：NullPointerException
//情况一：
// int[] arr1 = new int[]{1,2,3};
// arr1 = null;
// System.out.println(arr1[0]);
//情况二：
// int[][] arr2 = new int[4][];
// System.out.println(arr2[0][0]);
//情况三：
String[] arr3 = new String[]{"AA","BB","CC"};
arr3[0] = null;
System.out.println(arr3[0].toString());
}
}
//算法的考查：求数值型数组中元素的最大值、最小值、平均数、总和等
//定义一个int型的一维数组，包含10个元素，分别赋一些随机整数，
//然后求出所有元素的最大值，最小值，和值，平均值，并输出出来。
//要求：所有随机数都是两位数。
public class test1 {
public static void main(String[] args) {
//创建10个元素
int[] arr = new int[10];
//为这10个元素赋值
for(int i = 0;i < arr.length;i++){
arr[i] = (int)(Math.random() * 89 + 10);
System.out.print(arr[i] + " ");
}
System.out.println();
//求这十个元素的最大值
int maxValue = arr[0];
for(int i = 1;i < arr.length;i++){
if(arr[i] > maxValue){
maxValue = arr[i];
}
}
System.out.println("最大值为：" + maxValue);
//求这十个元素的最小值
int minValue = arr[0];
for(int i = 1;i < arr.length;i++){
if(arr[i] < minValue){
minValue = arr[i];
}
}
System.out.println("最小值为：" + minValue);
//求这十个元素之和
int sum = 0;
for(int i = 0; i <arr.length;i++){
sum += arr[i];
}
System.out.println("十个数组元素的和为：" + sum);
//求这十个元素的平均值
int average = 0;
for(int i = 0; i < arr.length;i++){
average = sum / 10;
}
System.out.println("十个数组元素的平均值为：" + average);
}
}
/*
* 算法的考查：数组的复制、反转、查找(线性查找、二分法查找)
*
*
*/
public class ArrayTest2 {
public static void main(String[] args) {
String[] arr = new String[]{"JJ","DD","MM","BB","GG","AA"};
//数组的复制(区别于数组变量的赋值：arr1 = arr)
String[] arr1 = new String[arr.length];
for(int i = 0;i < arr1.length;i++){
arr1[i] = arr[i];
}
//数组的反转
//方法一：
// for(int i = 0;i < arr.length / 2;i++){
// String temp = arr[i];
// arr[i] = arr[arr.length - i -1]; 1 2 3 4
// arr[arr.length - i -1] = temp;
// }
//方法二：
// for(int i = 0,j = arr.length - 1;i < j;i++,j--){
// String temp = arr[i];
// arr[i] = arr[j];
// arr[j] = temp;
// }
//遍历
for(int i = 0;i < arr.length;i++){
System.out.print(arr[i] + "\t");
}
System.out.println();
//查找（或搜索）
//线性查找：
String dest = "BB";
dest = "CC";
boolean isFlag = true;
for(int i = 0;i < arr.length;i++){
if(dest.equals(arr[i])){
System.out.println("找到了指定的元素，位置为：" + i);
isFlag = false;
break;
}
}
if(isFlag){
System.out.println("很遗憾，没有找到的啦！");
}
//二分法查找：(熟悉)
//前提：所要查找的数组必须有序。
int[] arr2 = new int[]{-98,-34,2,34,54,66,79,105,210,333};
int dest1 = -34;
dest1 = 35;
int head = 0;//初始的首索引
int end = arr2.length - 1;//初始的末索引
boolean isFlag1 = true;
while(head <= end){
int middle = (head + end)/2;
if(dest1 == arr2[middle]){
System.out.println("找到了指定的元素，位置为：" + middle);
isFlag1 = false;
break;
}else if(arr2[middle] > dest1){
end = middle - 1;
}else{//arr2[middle] < dest1
head = middle + 1;
}
}
if(isFlag1){
System.out.println("很遗憾，没有找到的啦！");
}
}
}
五.排序算法
衡量排序算法的优劣
1.时间复杂度：分析关键字的比较次数和记录的移动次数
2.空间复杂度：分析排序算法中需要多少辅助内存
3.稳定性：若两个记录A和B的关键字值相等，但排序后A，B的先后次序保持不变，则称这种算法是稳定的。
排序算法分类：内部排序和外部排序
十大内部排序算法
选择排序：例：直接选择排序，堆排序
交换排序：例：冒泡排序，快速排序
插入排序：例：直接插入排序，折半插入排序，Shell排序
归并排序
桶式排序
基数排序
冒泡排序：
介绍：
冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元 素，如果他们的顺序错误就把他们交换过来。
排序思想：
1. 比较相邻的元素。如果第一个比第二个大（升序），就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步 做完后，最后的元素会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要 比较为止。
/*
* 数组的冒泡排序的实现
*
*/
public class BubbleSortTest {
public static void main(String[] args) {
int[] arr = new int[]{43,32,76,-98,0,64,33,-21,32,99};
//冒泡排序
for(int i = 0;i < arr.length - 1;i++){
for(int j = 0;j < arr.length - 1 - i;j++){
if(arr[j] > arr[j + 1]){
int 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] + "\t");
}
}
}
快速排序：
介绍：
快速排序通常明显比同为 O(nlogn) 的其他算法更快，因此常被采用，而且快 排采用了分治法的思想，所以在很多笔试面试中能经常看到快排的影子。可 见掌握快排的重要性。
快速排序（ Quick Sort ）由图灵奖获得者 Tony Hoare 发明，被列为 20 世纪十 大算法之一 ，是迄今为止所有内排序算法中速度最快的一种。冒泡排序的升 级版，交换排序的一种。快速排序的时间复杂度为O(nlog(n)) 。
排序思想：
1. 从数列中挑出一个元素，称为 " 基准 " （ pivot ），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准 值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后， 该基准就处于数列的中间位置。这个称为分区（partition ）操作。
3. 递归地（ recursive ）把小于基准值元素的子数列和大于基准值元素的子数 列排序。
4. 递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好 了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代 (iteration ）中，它至少会把一个元素摆到它最后的位置去。
/**
* 快速排序
* 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，
* 则分别对这两部分继续进行排序，直到整个序列有序。
* @author shkstart
* 2018-12-17
*/
public class QuickSort {
private static void swap(int[] data, int i, int j) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
private static void subSort(int[] data, int start, int end) {
if (start < end) {
int base = data[start];
int low = start;
int high = end + 1;
while (true) {
while (low < end && data[++low] - base <= 0)
;
while (high > start && data[--high] - base >= 0)
;
if (low < high) {
swap(data, low, high);
} else {
break;
}
}
swap(data, start, high);
subSort(data, start, high - 1);//递归调用
subSort(data, high + 1, end);
}
}
public static void quickSort(int[] data){
subSort(data,0,data.length-1);
}
public static void main(String[] args) {
int[] data = { 9, -16, 30, 23, -30, -49, 25, 21, 30 };
System.out.println("排序之前：\n" + java.util.Arrays.toString(data));
quickSort(data);
System.out.println("排序之后：\n" + java.util.Arrays.toString(data));
}
}
各种内部排序方法性能比较
1. 从平均时间而言 ： 快速排序最佳。 但在最坏情况下时间性能不如堆排序和归并排序。
2. 从算法简单性看 ：由于直接选择排序、直接插入排序和冒泡排序的算法比较 简单，将其认为是简单算法。对于Shell 排序、堆排序、快速排序和归并排序 算法，其算法比较复杂，认为是复杂序。
3. 从稳定性看 ：直接插入排序、冒泡排序和归并排序时稳定的；而直接选择排 序、快速排序、 Shell 排序和堆排序是不稳定排序
4. 从待排序的记录数 n 的大小看 ， n 较小时，宜采用简单排序；而 n 较大时宜采 用改进排序。
排序算法的选择
(1) 若 n 较小 ( 如 n≤50) ，可采用 直接插入 或 直接选择排序 。
当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直 接插入，应选直接选择排序为宜
(2) 若文件初始状态基本有序 ( 指正序 ) ，则应选用 直接插入 、 冒泡 或随机的 快速排 序 为宜；
(3) 若 n 较大，则应采用时间复杂度为 O(nlgn) 的排序方法： 快速排序 、 堆排序 或 归并排序
六.Arrays工具类的使用
package com.atguigu.java;
import java.util.Arrays;
/*
* java.util.Arrays:操作数组的工具类，里面定义了很多操作数组的方法
*
*
*/
public class ArraysTest {
public static void main(String[] args) {
//1.boolean equals(int[] a,int[] b):判断两个数组是否相等。
int[] arr1 = new int[]{1,2,3,4};
int[] arr2 = new int[]{1,3,2,4};
boolean isEquals = Arrays.equals(arr1, arr2); //判断的是地址
System.out.println(isEquals); //false
//2.String toString(int[] a):输出数组信息。
System.out.println(Arrays.toString(arr1));
//3.void fill(int[] a,int val):将指定值填充到数组之中。
Arrays.fill(arr1,10);
System.out.println(Arrays.toString(arr1));
//4.void sort(int[] a):对数组进行排序。
Arrays.sort(arr2);
System.out.println(Arrays.toString(arr2));
//5.int binarySearch(int[] a,int key)
int[] arr3 = new int[]{-98,-34,2,34,54,66,79,105,210,333};
int index = Arrays.binarySearch(arr3, 210);
if(index >= 0){
System.out.println(index); //8
}else{
System.out.println("未找到");
}
}
}