一. 数组:Array
1. 数组相关基础知识
- 1、Java 语言中的数组是一种引用数据类型。不属于基本数据类型。数组的父类是 Object。
- 2、数组实际上是一个容器,可以同时容纳多个元素。(数组是一个数据的集合)。
数组:字面意思是“一组数据”。 - 3、数组当中可以存储基本数据类型的数据,也可以存储“引用数据类型” 的数据。
- 4、数组因为是引用类型,所以数组对象是堆内存当中的。(数组是存储在堆当中的)。
- 5、数组当中如果存储的是“java 对象” 的话,实际上存储的是 java 对象的“引用(内存地址)”,数组不能直接存储 java 对象。
- 6、数组的分类:一维数组、二维数组、三维数组、多维数组…(一维数组较多,二维数组偶尔使用)。
- 7、数组一旦创建,在 java 规定,长度不可变。(数组长度不可变)。
- 8、所有数组对象都有 length 属性(java 自带的),用来获取数组中元素的个数。
- 9、java 中的数组要求数组中的元素类型统一。
- 10、数组在内存方面存储的时候,数组中的元素内存地址(存储的每一个元素都是有规则的挨着排列的)是连续的。内存地址连续。这是数组存储元素的特点。数组实际上是一种简单的数据结构。
- 11、所有的数组都是拿“第一个小方框的内存地址”作为整个数组对象的内存地址。(数组中首元素的内存地址作为整个数组对象的内存地址)
- 12、数组中的每一个元素都是有下标的,下标从 0 开始,以 1 递增。最后一个元素的下标:length – 1
下标非常重要,因为我们对数组中的元素进行“存取”的时候都需要下标;来进行。
2. 数组的优缺点
2.1. 优点 :
查询、检索某个下标上的元素时效率极高。可以说查询效率最高的一个数据结构。
为什么检索效率高?
- 第一:每一个元素的内存地址在空间存储上是连续的。
- 第二:每一个元素类型相同,所以占用空间大小一样。
- 第三:如果知道一个元素内存地址,知道每一个元素占用空间大小,又知道下标,所以通过一个数学表达式就可以计算出某个下标上的元素的内存地址。直接通过内存地址定位元素,所以数组的检索效率是最高的。
2.2. 缺点 :
- 第一:由于为了保证数组中每个元素的内存地址连续,所以在数组上随即删除或者增加元素的时候效率较低,因为随机增删元素会涉及到后面元素统一向前或者向后位移的操作。
- 第二:数组不能存储大量数据,因为很难在空间上找到一块特别大的连续的内存
注意:对于数组中最后一个元素的增删是没有效率影响的
二. 一维数组
1. 怎样声明一个一维数组
语法格式:int[] array;double[] array;boolean[] array;String[] array;Object[] array;
2. 怎样初始化一个一维数组呢?
包括两种方式:静态初始化一维数组、动态初始化一维数组
静态初始化一维数组:int[] array = {100,200,300};、String[] str = {“as”,”cs” ,”ds”}; 也可以使用 int array[] = {1,2,3},这是 C++风格,不建议在 java 中使用
动态初始化一维数组: Int[] array = new int [5]; 这里的 5 表示数组元素个数, 初始化一个 5 个长度的 int 类型数组,每个元素默认值为 0
String[] names = new String[6]; 初始化 6 个长度的 String 类型数组,每个元素默认值 null
3. 对一维数组中的元素访问
public class ArrayTest01 {
public static void main(String[] args) {
int[] a = {1,2,3,4,5};
//取(读)
System.out.println(a.length);
System.out.println("第一个元素是" + a[0]);
System.out.println("最后一个元素是" + a[4]);
System.out.println("最后一个元素是" + a[a.length - 1]);
//存(改)
a[0] = 0;//把第一个元素修改
a[a.length-1] = 999;//把最后一个元素修改
System.out.println("第一个元素是" + a[0]);
System.out.println("最后一个元素是" + a[4]);
System.out.println("最后一个元素是" + a[a.length - 1]);
}
}
输出结果:

4. 一维数组的遍历
遍历写法:
提示:下标越界会出现异常:
接上面代码
for (int i = 0;i < a.length; i++){
System.out.println(a[i]);
}
//颠倒遍历
for (int i = a.length - 1;i >= 0; i--){
System.out.println("颠倒顺序输出-->" + a[i]);
}
结果:

5. 静态存储Object类
Object o1 = new Object();
Object o2 = new Object();
Object o3 = new Object();
Object[] object= {o1,o2,o3};
/*或
Object[] object= {new Object(),new Object(),new Object()};
*/
for(int i = 0; i < object.length; i++){
System.out.println(object[i]);
}
6. 动态初始化一维数组
public class ArrayTest {
public static void main(String[] args) {
//声明定义一个数组,采用动态初始化的方式创建
int[] a = new int[4];//创建长度为4的int数组,数组中每个元素的默认值为0
//遍历数组
for (int i = 0; i < a.length; i++){
System.out.println("数组中的下标为" + i +"的元素是" + a[i]);
}
}
}
输出结果:

7. 什么时候采用静态初始化方法/动态初始化方法?
当你创建数组的时候,确定数组中存储哪些具体的元素的时候,采用静态初始化。
当你创建数组的时候,不确定数组中存储哪些数据,你可以采用动态初始化的方式,预先分配内存空间。
8. 方法的参数为数组
public class ArrayTest {
public static void main(String[] args) {
//调用方法时传一个数组
int[] a = {1,2,3,4};
printArray(a);
//不能printArray({1,2,3});没有这个语法
/* 或
printArray(new int[] {1,2,3});
*/
}
public static void printArray(int[] array){
for (int i = 0; i < array.length; i++) {
System.out.println( array[i]);
}
}
}
9. 数组中存储引用数据类型
对于数组来说,实际上只能存储java对象的“内存地址”。数组中存储的每个元素都是“引用”
提示:不能存放别的引用数据类型
如果继承该引用数据类型的数据类型可以使用该数组
public class ArrayTest2 {
public static void main(String[] args) {
Animal a1 = new Animal();
Animal a2 = new Animal();
Animal[] animals = {a1,a2};
for (int i = 0; i < animals.length; i++){
animals[i].move();
}
}
}
class Animal{
public void move(){
System.out.println("Animal move");
}
}
运行结果:

10. 输出数组的方法
错误示范:System.out.println(array); //这样输出的是数组的首地址,而不能打印出数组数据
正确写法:int[] array= {1,2,3,4,5,6};
方式一:for循环
for(int i=0;i<array.length;i++)
{
System.out.println(array[i]);
}
输出为:(自动换行格式的)
方式二:for each
for(int a:array)
System.out.println(a);
输出格式同方式一。
方式三:Arrays类中的toString方法(注意,是Arrays不是Array,Arrays类位于java.util包下)
需要导入 import java.util.Arrays 包
int[] array= {1,2,3,4,5,6};
System.out.println(Arrays.toString(array));
11. 数组扩容
Java 中对数组的扩容是:
先新建一个大容量的数组,然后将小容量数组中的数据一个一个拷贝到大数据当中。
结论:数组扩容效率较低。因为涉及到拷贝的问题。所以在以后的开发中请注意:尽可能少的进行数组的拷贝。可以在创建数组对象的时候预估计以下多长合适,最好预估准确,这样可以减少数组的扩容次数,提高效率。
第一种方法,建立一个新的数组,通过 for 循环来进行拷贝扩容
int[] b=new int[a.length*2];//a.length 长度;a数组的长度。即数组中数据的个数
for(int i=0;i<a.length;i++){
b[i]=a[i];
}
System.out.println(Arrays.toString(b));//这个函数就是将数组b进行遍历输出
//如果不明白遍历什么意思,建议先学习遍历后再来看此篇文章
第二种方法:固定的写法。System.Arrays.copy(a,0,b,0,a.length);
int[] c=new int[20];
System.arraycopy(a,0,c,0,a.length);
//a,需要复制的内容。第一个0(零):在a中开始复制的内容的位置
//c,要复制的载体,在这里写c就是将a中需要复制的内容赋值给c
//第二个0(零):在c中开始复制的位置
//a.length:要复制的元素量
System.out.println(Arrays.toString©);
方法三:利用函数方法直接扩容
//原理,利用Arrays中的函数进行扩容
int[] d=Arrays.copyOf(a,22);//此函数的作用就是复制a的值。定义d的长度
// Arrays.copyOf(a,22); a,需要复制的内容(a数组),22:定义d数组的长度
System.out.println(Arryas.toString(d));
}
}
12. 数组拷贝
数组拷贝的方法:System.arraycopy( Object src,int srcPos,Object dest, int destPos,int length)
Object src:源数组
int srcPos:源数组起点下标
Object dest:目标数组
int destPos:目标数组起点下标
int length:拷贝的源数组的长度
数组中存储的元素是引用也可以拷贝。且拷贝的是对象的内存地址
public class ArrayTest3 {
public static void main(String[] args) {
int[] src = {1,11,22,33,44};//拷贝源
int[] dest = new int[20];//拷贝目标
for (int i = 0; i < dest.length; i++){
System.out.print(dest[i]+" ");
}
System.out.println();
System.arraycopy(src,1,dest,2,2);//进行拷贝
for (int i = 0; i < dest.length; i++){
System.out.print(dest[i]+" ");
}
}
}
运行结果:

三. 冒泡排序算法
思想:
1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2、对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。 3、针对所有的元素重复以上的步骤,除了最后一个。 4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
举例: (1) 要排序数组:[10,1,35,61,89,36,55]
(2) 第一趟排序:
第一次排序:10 和 1 比较,10 大于 1,交换位置 [1,10,35,61,89,36,55]
第二趟排序:10 和 35 比较,10 小于 35,不交换位置 [1,10,35,61,89,36,55]
第三趟排序:35 和 61 比较,35 小于 61,不交换位置 [1,10,35,61,89,36,55]
第四趟排序:61 和 89 比较,61 小于 89,不交换位置 [1,10,35,61,89,36,55]
第五趟排序:89 和 36 比较,89 大于 36,交换位置 [1,10,35,61,36,89,55]
第六趟排序:89 和 55 比较,89 大于 55,交换位置 [1,10,35,61,36,55,89]
第一趟总共进行了六次比较,排序结果:[1,10,35,61,36,55,89]
(3) 第二趟排序:
第一次排序:1 和 10 比较,1 小于 10,不交换位置 [1,10,35,61,36,55,89]
第二次排序:10 和 35 比较,10 小于 35,不交换位置 [1,10,35,61,36,55,89]
第三次排序:35 和 61 比较,35 小于 61,不交换位置 [1,10,35,61,36,55,89]
第四次排序:61 和 36 比较,61 大于 36,交换位置 [1,10,35,36,61,55,89]
第五次排序:61 和 55 比较,61 大于 55,交换位置 [1,10,35,36,55,61,89]
第二趟总共进行了 5 次比较,排序结果:[1,10,35,36,55,61,89]
(4) 第三趟排序:
1 和 10 比较,1 小于 10,不交换位置 [1,10,35,36,55,61,89]
第二次排序:10 和 35 比较,10 小于 35,不交换位置 [ 1,10,35,36,55,61,89]
第三次排序:35 和 36 比较,35 小于 36,不交换位置 [1,10,35,36,55,61,89]
第四次排序:36 和 61 比较,36 小于 61,不交换位置 [1,10,35,36,55,61,89]
第三趟总共进行了 4 次比较,排序结果:[1,10,35,36,55,61,89]
到目前位置已经为有序的情形了。

平均时间复杂度:O(n²)
最好情况:O(n)
最坏情况:O(n²)
空间复杂度:O(1)
public class BubbleSort {
public static void main(String[] args) {
int temp ; //临时变量,存储数据
int[] a = {2,4,1,7,9,6,3};
for (int i = a.length-1 ; i > 0 ; i-- ){
for (int j = 0 ; j < a.length-1 ; j++){
if (a[j] > a[j+1]){
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
for ( int i = 0; i < a.length ; i++){
System.out.print(a[i]+ " ");
}
}
}
四. 选择排序
思想:
简单选择排序采用最简单的选择方式,从头至尾顺序扫描序列找出最小的一个关键字,和第一个关键字交换,接着从剩下的关键字中继续这种选择和交换,最终使序列有序。
图解:

示例代码:
public class SelectSort {
public static void main(String[] args) {
int[] a = {2, 4, 6, 3, 1, 5};
for (int i = 0; i < a.length - 1; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (a[min] > a[j]) {
min = j;
}
}
int temp;
temp = a[i];
a[i] = a[min];
a[min] = temp;
}
for (int i = 0 ; i < a.length ; i++){
System.out.println(a[i]);
}
}
}
五. 二分查找法
思想:
假设数据是按升序排序的,对于给定值 x,从序列的中间位置开始比较,如果当前位置值等于 x,则查找成功;若 x 小于当前位置值,则在数列的前半段中查找;若 x 大于当前位置值则在数列的后半段中继续查找,直到找到为止。
示例: 假如有一组数为 3,12,24,36,55,68,75,88 要查给定的值 24. 可设三个变量 front,mid,end 分别指向数据的上界,中间和下界,mid=(front+end)/2.
1、开始令 front=0(指向 3),end=7(指向 88),则 mid=3(指向 36)。因为 mid>x,故应在前半段中查找。
2、令新的 end=mid-1=2,而 front=0 不变,则新的 mid=1。此时 x>mid,故确定应在后半段中查找。
3、令新的 front=mid+1=2,而 end=2 不变,则新的 mid=2,此时 a[mid]=x,查找成功。
如果要查找的数不是数列中的数,例如 x=25,当第三次判断时,x>a[mid],按以上规律,令 front=mid+1,即 front=3,出现 front>end 的情况,表示查找不成功。
代码:
public static int binarySearch(Integer[] srcArray, int des) {
//定义初始最小、最大索引
int start = 0;
int end = srcArray.length - 1;
//确保不会出现重复查找,越界
while (start <= end) {
//计算出中间索引值
int mid = (end + start)/2 ;
if (des == srcArray[mid]) {
return mid;
//判断下限
} else if (des < srcArray[mid]) {
end = mid - 1;
//判断上限
} else {
start = mid + 1;
}
}
//若没有,则返回-1
return -1;
}
六. 一维数组模拟栈数据结构
1. 使用一维数组,模拟栈数据结构
要求:
- 1、这个栈可以存储java中任何引用数据类型。
- 2、在栈中提供push方法模拟压栈。(栈满会有提示信息)
- 3、在栈中提供pop方法模拟弹栈。(栈空了也要有提示信息)
- 4、编写测试程序,new栈对象,调用push、pop方法来模拟压栈弹栈动作。
MyStack类:
public class MyStack {
/**属性私有化需要get和set方法*/
private Object[] elements;
/**栈帧,永远指向栈顶元素。
栈顶初始默认值应该是-1,因为刚开始栈是空的没有元素。*/
private int index ;
public MyStack(){
//一维数组动态初始化
//默认初始化容量为10
this.elements = new Object[10];
//给index初始化
this.index = -1;
}
/**
* 压栈的方法
* @param obj 被压入元素
*/
public void push(Object obj){
if (this.index >= this.elements.length - 1){
System.out.println("栈已满,压栈失败!");
return;
}
//程序能走到这里,说明栈没满
//向栈中加1个元素,栈帧向上移动一个位置。
this.index++;
this.elements[index] = obj;
//所有System.out.println()方法执行时。如果输出引用的话,自动调用引用的toString()方法
System.out.println("压栈" + obj + "元素成功,栈帧指向" + index);
}
/**
* 弹栈的方法,从数组中取出一个元素
* @return
*/
public void pop(){
if (index < 0 ){
System.out.println("弹栈失败,栈已空");
return;
}
System.out.print("弹栈" + elements[index] + "元素成功,");
index--;
System.out.println("栈帧指向" + index);
}
/**set 和 get也许用不上,但是必须写上,这是规则
封装:第一步:属性私有化,第二步:对外提供set和get方法。*/
public Object[] getElements() {
return elements;
}
public void setElements(Object[] elements) {
this.elements = elements;
}
}
StackTest类:
public class SatckTest {
public static void main(String[] args) {
//创建一个栈对象,初始化容量是10个
MyStack stack = new MyStack();
stack.push(new Object());
stack.push(new Object());
stack.push(new Object());
stack.push(new Object());
stack.push(new Object());
stack.push(new Object());
stack.push(new Object());
stack.push(new Object());
stack.push(new Object());
stack.push(new Object());
//压这个元素失败了
stack.push(new Object());
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
stack.pop();
}
}
输出结果:

七. 二维数组
二维数组其实是一个特殊的一维数组,特殊在这个一维数组当中的每一个元素都是一个一维数组
1. 二维数组静态初始化
int[][] array = {{1,1,1},{2,2,2},{3,3,3}};
2. 二维数组的length属性
public class ArrayTest4 {
public static void main(String[] args) {
int[][] a ={
{1,2,3},
{10,20,30,40,50},
{6,7,8,9},
{0}
};
System.out.println(a.length);//指二维数组中有几个大括号
System.out.println(a[0].length);//指{1,2,3}的长度
}
}
输出结果:

3. 二维数组的元素访问
a[二维数组中的一维数组的下标][一维数组的小标]
a[0][0]:表示第一个一维数组中的一个一维元素。
取出上面二维数组中的第1个一维数组和一维数组的第一个元素:
int[] first = a[0] ;
int firstnum = first[0];
System.out.println(firstnum);
//或
System.out.println(a[0][0]);
System.out.println(Arrays.toString(a[0]));
输出结果:

4. 二维数组的遍历
public class ArrayTest5 {
public static void main(String[] args) {
String[][] array = {
{"java","oracle","c++","python","c#"},
{"张三","李四","王五"},
{"lucy","jack","rose"}
};
for (int i = 0; i < array.length; i++){
for (int j = 0 ; j < array[i].length ; j++){
System.out.print(array[i][j] + " ");
}
System.out.println("");
}
}
}
输出结果:

5. 动态初始化二维数组
int[][] = new int[3][4];
6. 方法的参数是一个二维数组
public class ArrayTest6 {
public static void main(String[] args) {
int[][] a ={
{1,2,3,4},
{5,6,7,8},
{9,10,11}
};
printArray(a);
}
public static void printArray(int[][] array){
for (int i = 0 ; i < array.length ; i++){
for (int j = 0; j < array[i].length ; j++){
System.out.print(array[i][j] + " ");
}
System.out.println();
}
}
}
输出结果:

八. 二维数组模拟酒店管理系统
为某个酒店编写程序:酒店管理系统,模拟订房、退房、打印所有房间状态等功能 要求:
1、该系统的用户是:酒店前台。 2、酒店中所有房间使用一个二维数组来模拟:Room[][] rooms; 3、酒店中的每一个房间应该是一个 java 对象:Room。 4、每一个房间 Room 应该有:房间编号、房间类型属性、房间是否空闲 5、系统应该对外提供哪些功能: 可以预定房间:用户输入房间编号,订房。 可以退房:用户输入房间编号,退房。 可以查看所有房间的状态:用户输入某个指令应该可以查看所有房间状态。
HotelSystem: 酒店前台系统
package com.company;
import java.util.Scanner;
public class HotelSystem {
public static void main(String[] args) {
//创建酒店对象
Hotel hotel = new Hotel();
/*
首先输出一个欢迎界面
*/
System.out.println("************************");
System.out.println(" 欢迎使用本酒店管理系统 ");
System.out.println(" 请输入对于的功能编号: ");
System.out.println(" 1 查看房间列表 ");
System.out.println(" 2 订房 ");
System.out.println(" 3 退房 ");
System.out.println(" 0 退出系统 ");
System.out.println("************************");
Scanner s = new Scanner(System.in);
boolean flag = true;
//循环一直可以使用
while (flag){
System.out.print("请输入功能编号:");
int i = s.nextInt();
switch (i){
case 0:
System.out.println("已退出系统,欢迎下次光临!");
flag = false;
break;
case 1:
hotel.print();
break;
case 2:
System.out.print("请输入订房编号");
Scanner s1 = new Scanner(System.in);
int i1 = s1.nextInt();
hotel.order(i1);
break;
case 3:
System.out.print("请输入退房编号");
Scanner s2 = new Scanner(System.in);
int i2 = s2.nextInt();
hotel.exit(i2);
break;
default:
System.out.println("输入功能编号有误,请重新输入");
}
}
}
}
Hotel类: 酒店对象,包含二维数组
package com.company;
/*
酒店对象,酒店中有二维数组,二维数组模拟酒店房间
*/
public class Hotel {
/**
* 二维数组,模拟大厦所有房间
*/
private Room[][] rooms;
/**
* 盖楼通过构造方法盖楼
*/
public Hotel() {
//一共有几层,每层的房间类型是什么,每个房间的编号是什么
//一层为单人间、二层为标准间、三层为总统套房
/*房间编号的规律
* 1楼:101 102 103...
* 2楼:201 202 203...
* 3楼:301 302 302...*/
rooms = new Room[3][10];
for (int i = 0; i < rooms.length ; i++){
for (int j =0 ; j < rooms[i].length; j++ ){
if (i==0){
rooms[i][j] = new Room((i+1)*100+j+1,"单人间",true);
}else if (i == 1){
rooms[i][j] = new Room((i+1)*100+j+1,"标准间",true);
}else{
rooms[i][j] = new Room((i+1)*100+j+1,"总统套房",true);
}
}
}
}
public void print(){
for (int i = 0; i < rooms.length ; i++) {
for (int j = 0; j < rooms[i].length; j++) {
Room room = rooms[i][j];
System.out.print(room.toString() + " | ");
}
System.out.println();
}
}
/**
* 订房方法
* @param roomNo 调用此方法是需要传递一个房间的编号过来。这个房间编号是前台输入过来的。
*/
public void order(int roomNo){
//订房最主要的是将房间对象的status改为false。
//Room对象的status修改为false
Room room = rooms[(roomNo / 100) - 1][(roomNo % 100) - 1];
//修改为占用
room.setStatus(false);
}
public void exit(int roomNo){
Room room = rooms[(roomNo / 100) - 1][(roomNo % 100) - 1];
room.setStatus(true);
System.out.println(roomNo + "已退房!");
}
}
Room类: 房间信息
package com.company;
import java.util.Objects;
public class Room {
/**
* 房间编号
*/
private int no;
/**
* 房间类型:标准间 单人间 总统套房
*/
private String type;
/**
* 房间状态:
* true:表示空闲,可以预定。
* false:表示占用,不能预定
*/
private boolean status;
public Room() {
}
public Room(int no, String type, boolean status) {
this.no = no;
this.type = type;
this.status = status;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public String getType() {
return type;
}
public void setType(String type) {
this.type = type;
}
public boolean isStatus() {
return status;
}
public void setStatus(boolean status) {
this.status = status;
}
/**
* equals方法重写
* @param obj
* @return 房间号是否相等
*/
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null || !(obj instanceof Room)) {
return false;
}
Room room = (Room) obj;
return this.getNo() == room.getNo();
}
@Override
public int hashCode() {
return Objects.hash(no, type, status);
}
/**
* toString方法重写
* @return 输出房间信息
*/
@Override
public String toString() {
return "房间号为" + no +
", 类型为'" + type + '\'' +
", 状态为" + (status?"空闲":"占用") ;
}
}
运行截图:







