| 3、数组及排序算法(2天) | |
| 3.1 数组的概述 | 2课时 |
| 3.2 一维数组的使用 | 3课时 |
| 3.3 多维数组的使用 | 3课时 |
| 3.4 数组中涉及到的常见算法 | 3课时 |
| 3.5 Arrays工具类的使用 | 3课时 |
| 3.6 数组使用中的常见异常 | 2课时 |
3-1 数组的概述
3-2 一维数组的使用
/**
* @author Heaton
* @email tzy70416450@163.com
* @date 2018/9/10 0010 14:04
* @describe
* 1-数组是多个相同类型数据的组合，实现对这些数据的统一管理
*
* 数组本身属于引用类型
* 数组的元素，可以是基本数据类型，也可以是引用数据类型
* 数组声明与使用： 数据类型 [] 变量名 = new 数据类型[]{}; 如:short [] scorse2 = new short[]{60,70,80,90,100};
* 或 数据类型 [] 变量名 = {}; 如：byte [] scorse1 = {60,70,80,90,100};
* 使用时根据下标使用 : 变量名[下标] = 某一个值;
*
* 变量声明与赋值: 数据类型 变量名 = 值; 例如: int i = 1;
*/
public class ArrayTest {
public static void main(String[] args) {;
//1.1一维数组的声明和初始化
int [] scorse;
byte [] scorse1 = {60,70,80,90,100};
short [] scorse2 = new short[]{60,70,80,90,100};
int [] scorse3 ;
String [] names;
//1.2初始化
//静态初始化：数组的初始化和数组元素的赋值是同时进行的。
scorse = new int[]{60,70,80,90,100};
//scorse3 = {60,70,80,90,100};//不能这么写
//动态初始化：数组的初始化和数组元素的赋值是分开进行的。
names = new String[4];
//2数组元素的调用，通过下角标的方式调用，角标从0开始，到数组长度-1结束。 动态赋值
names[0] = "王瑞";
names[1] = "哞哞";
names[2] = "小王";
names[3] = "小周";
int[] arr1 = {1,2,3};//简写方式，JAVA自动类型推断；
//错误的写法
/*
int [] arr2 = new int[3]{1,2,3};
int [3] arr3 = new int[]{60,70,80,90,100};
int arr4;
arr4 = new int[]{1,2,3,4,5};
*/
//3.如何获取数组的长度？
//String a = "asdasdasd";
//System.out.println(a.length());
System.out.println(scorse.length);
System.out.println(names.length);//4
//4.数组元素的遍历
System.out.println(names[0]);
System.out.println(names[1]);
System.out.println(names[2]);
System.out.println(names[3]);
//System.out.println(names[4]);//报数组下标越界异常java.lang.ArrayIndexOutOfBoundsException:
//names[4] = "小周";
//总结：不管是静态还是动态初始化，一旦数组初始化完成，其长度就是确定的！
for (int i = 0; i < scorse.length; i++) {
System.out.println(scorse[i]);
}
}
}
//二、一维数组的使用(5-6)
public class ArrayTest1 {
public static void main(String[] args) {
//5.不同类型的数组元素的默认初始化值。
//5.1 整型数组：byte、short、int、long的默认数组元素的初始化值都为:0
byte[] arr1 = new byte[4];
arr1[0] = 1;
for(int i = 0;i < arr1.length;i++){
System.out.println(arr1[i]);
}
long[] arr2 = new long[4];
System.out.println("long：" + arr2[0]);
//5.2 浮点型数组：float、double 的默认数组元素的初始化值都为:0.0
float[] arr3 = new float[5];
for(int i = 0;i < arr3.length;i++){
System.out.println("float:" + arr3[i]);
}
//5.3 字符型数组：char的默认数组元素的初始化值都为:'\u0000' \u开头的是一个Unicode码的字符,每一个'\u0000'都代表了一个空格.
char[] arr4 = new char[5];
for(int i = 0;i < arr4.length;i++){
System.out.println("char:" + arr4[i] + "-----");
}
//5.4 布尔型数组：boolean的默认数组元素的初始化值都为:false
boolean[] arr5 = new boolean[5];
for(int i = 0;i < arr5.length;i++){
System.out.println("boolean:" + arr5[i]);
}
//5.5 引用数据类型数组:数组、接口、类的默认数组元素的初始化值为：null
String[] arr6 = new String[5];
for(int i = 0;i < arr6.length;i++){
System.out.println("String:" + arr6[i]);//null,不是"null"
}
//6.一维数组的内存解析（难点）
}
}
练习
import java.util.*;
/*
* 一维数组的练习二
*
* 从键盘读入学生成绩，找出最高分，并输出学生成绩等级。
成绩>=最高分-10 等级为’A’
成绩>=最高分-20 等级为’B’
成绩>=最高分-30 等级为’C’
其余 等级为’D’
提示：先读入学生人数，根据人数创建int数组，存放学生成绩。
*/
public class ArrayTest1 {
public static void main(String[] args) {
//1.Scanner的实例化
Scanner s = new Scanner(System.in);
//2.根据提示，获取数组的元素的个数：数组的长度
System.out.println("请输入学生人数：");
int num = s.nextInt();
//3.根据获取的数组的长度，创建存放学生成绩的数组：动态
int[] scores = new int[num];
//4.通过循环的方式，使用Scanner获取每一个学生的成绩，并给数组的元素进行初始化
System.out.println("请输入" + num + "个成绩：");
int maxScore = 0;//记录最高分
for(int i = 0;i < scores.length;i++){
scores[i] = s.nextInt();
//5.在给数组元素赋值过程中，“顺便”获取成绩的最高分
if(maxScore < scores[i]){
maxScore = scores[i];
}
}
System.out.println("最高分是：" + maxScore);
//不使用如下的方式：效率差
//5.通过遍历数组，获取学生成绩的最大值,并输出
// int maxScore = 0;
// for(int i = 0;i < scores.length;i++){
// if(maxScore < scores[i]){
// maxScore = scores[i];
// }
// }
//6.通过遍历数组，获取每个学生的成绩，并输出其等级。（通过判断其成绩与最高分的差值）
char studentScores;
for(int i = 0;i < scores.length;i++){
if(scores[i] >= maxScore - 10){
studentScores = 'A';
}else if(scores[i] >= maxScore - 20){
studentScores = 'B';
}else if(scores[i] >= maxScore - 30){
studentScores = 'C';
}else{
studentScores = 'D';
}
System.out.println("student " + i + " score is " + scores[i] + ", studentScores is " + studentScores);
}
}
}
3-3 多维数组的使用
/**
* @author Heaton
* @email tzy70416450@163.com
* @date 2018/9/11 0011 13:40
* @describe 二维数组: 一维数组中的元素，恰好是一维数组
*/
public class ArrayTest2 {
public static void main(String[] args) {
String[] names = new String[]{"王瑞", "小宁"};
//1.二维数组初始化
//1.1静态初始化
String[][] arr1 = new String[][]{{"王瑞", "13548965486"}, {"小宁", "17356897845"}, {"张飞", "15896547896"}};
//1.2动态初始化
int[][] arr2 = new int[3][2];
//1.2动态初始化
int[][] arr3 = new int[3][];
arr3[0] = new int[]{1, 2, 3};
arr3[1] = new int[]{1, 2};
arr3[2] = new int[4];
//2.通过下标的方式进行数组元素的调用
System.out.println(arr1[1][0]);
arr2[1][0] = 1;
//{{0，0}，{1，0}，{0，0}}
System.out.println(arr2[1][0]);//1
//3.数组的属性:length
System.out.println(arr1.length);//3
System.out.println(arr1[0].length);//2
System.out.println(arr1[1].length);//2
System.out.println(arr1[2].length);//2
System.out.println("^^^^^^^^^^^^^^^");
//4.遍历二维数组
for (int i = 0; i < arr1.length ; i++) {
for (int j = 0; j < arr1[i].length; j++) {
//怎么拿arr1[0][0]
System.out.print(arr1[i][j] + "\t");
}
System.out.println();
}
}
}
/**
* @author Heaton
* @email tzy70416450@163.com
* @date 2018/9/11 0011 14:10
* @describe 二维数组的使用
*/
public class ArrayTest3 {
public static void main(String[] args) {
//5.二维数组元素的值：
//5.1如果调用的是二维数组元素a,而元素a任然是数组，根据元素a的数组元素类型，决定其内部元素的默认初始化值，与一维数组的规定相同
//5.2如果输出元素a，其值决定于是否初始化过，如果初始化过.则输出其他地址值。如果没有初始化过，则值为null.
short[][] arr1 = new short[3][2];
System.out.println(arr1[0][1]);//0
System.out.println(arr1[0]);//[S@28d93b30
System.out.println(arr1);//[[S@1b6d3586
boolean[][] arr2 = new boolean[3][2];
System.out.println(arr2[1][1]);//false
int[][] arr3 = new int[3][];
System.out.println(arr3[1]);// null
arr3[1] = new int[2];
System.out.println(arr3[1]);//[I@4554617c
System.out.println("&&&&&&&&&&&&");
//6。二维数组的内存解析（难点）
int [][] arr = new int[3][];
arr[1] = new int[]{1,2,3};
arr[2] = new int[3];
System.out.println(arr[0]);
System.out.println(arr[1]);
System.out.println(arr[1]);
}
}
练习3
练习4
/**
* @author Heaton
* @email tzy70416450@163.com
* @date 2018/9/11 0011 15:06
* @describe
* 使用二维数组打印一个 10 行杨辉三角.
* 1
* 1 1
* 1 2 1
* 1 3 3 1
* 1 4 6 4 1
* 1 5 10 10 5 1
* ....
*
* 1
* 1 1
* 1 2 1 :yanghui[3][1] = yanghui[2][0] + yanghui[2][1];
* 1 3 3 1
* 1 4 6 4 1
* 1 5 10 10 5 1 ::yanghui[6][2] = yanghui[5][1] + yanghui[5][2];
* ....
*
* 【提示】
* 1. 第一行有 1 个元素, 第 n 行有 n 个元素
* 2. 每一行的第一个元素和最后一个元素都是 1
* 3. 从第三行开始, 对于非第一个元素和最后一个元素的元素.
* yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
*
*/
public class YangHuiTriAngle {
public static void main(String[] args) {
//1.创建此二维数组：new int[10][];
int[][] yanghui = new int[10][];
//2.为这个二维数组元素的元素赋值
for (int i = 0; i <yanghui.length; i++) {
//先把每一行元素个数定义出来
yanghui[i] = new int[i+1];
//给每行首位元素赋值
yanghui[i][0] = yanghui[i][i] = 1;
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];
}
}
}
for (int i = 0; i < yanghui.length; i++) {
for (int j = 0; j < yanghui[i].length; j++) {
System.out.print(yanghui[i][j] + "\t");
}
System.out.println();
}
}
}
3-4 数组中涉及到的常见算法
1.求数组元素的最大值、最小值、平均数、总和等
2.数组的复制、反转、查找(线性查找、二分法查找)
3.数组元素的排序
案例
/**
*
* 1.求数组元素的最大值、最小值、平均数、总和等--->针对于数值类型的数组
*
*
*
*/
public class ArrayTest1 {
public static void main(String[] args) {
int[] arr1 = new int[]{23,5,23,64,66,-9,75,-77,3};
//求最大值
int max = arr1[0];
for(int i = 1;i < arr1.length;i++){
if(max < arr1[i]){
max = arr1[i];
}
}
System.out.println("数组的最大值为：" + max);
//求最小值
int min = arr1[0];
for(int i = 1;i < arr1.length;i++){
if(min > arr1[i]){
min = arr1[i];
}
}
System.out.println("数组的最小值为：" + min);
//求总和
int sum = 0;
for(int i = 0;i < arr1.length;i++){
sum += arr1[i];
}
System.out.println("数组的总和为：" + sum);
//求平均值
double avg = 0;
avg = sum / (arr1.length + 0.0);
System.out.println("数组的平均数为：" + avg);
}
}
案例
/*
* 2.数组的复制、反转、查找(线性查找、二分法查找)
*/
public class ArrayTest2 {
public static void main(String[] args) {
String[] arr1 = new String[]{"MM","JJ","GG","DD","AA","BB","CC"};
//数组的复制
String[] arr2 = new String[arr1.length];
for(int i = 0;i < arr2.length;i++){
arr2[i] = arr1[i];
}
//数组的反转
// String[] arr3 = new String[arr1.length];
// for(int i = arr1.length - 1;i >= 0;i--){
// arr3[arr3.length - i - 1] = arr1[i];
// }
//
// arr1 = arr3;
//反转方式一：
// for(int i = 0,j = arr1.length - 1;i < j;i++,j--){
// String temp = arr1[i];
// arr1[i] = arr1[j];
// arr1[j] = temp;
// }
//反转方式二：
// for(int i = 0;i < arr1.length / 2;i++){
// String temp = arr1[i];
// arr1[i] = arr1[arr1.length - 1 - i];
// arr1[arr1.length - 1 - i] = temp;
// }
//遍历
for(int i = 0;i < arr1.length;i++){
System.out.print(arr1[i] + " ");
}
//线性查找
String value = "CCC";
int i = 0;
for(;i < arr1.length;i++){
if(arr1[i].equals(value)){
System.out.println("找到指定元素，索引为：" + i);
break;
}
}
if(i == arr1.length){
System.out.println("未找到指定元素");
}
//二分法查找：要求此数组必须是有序的。
int[] arr3 = new int[]{-99,-54,-2,0,2,33,43,256,999};
boolean isFlag = true;
// int number = 256;
int number = 25;
int head = 0;//首索引位置
int end = arr3.length - 1;//尾索引位置
while(head <= end){
int middle = (head + end) / 2;
if(arr3[middle] == number){
System.out.println("找到指定的元素，索引为：" + middle);
isFlag = false;
break;
}else if(arr3[middle] > number){
end = middle - 1;
}else{//arr3[middle] < number
head = middle + 1;
}
}
if(isFlag){
System.out.println("未找打指定的元素");
}
}
}
数组排序
- 选择排序
- 直接选择排序、堆排序
- 交换排序
- 冒泡排序、快速排序
- 插入排序
- 直接插入排序、折半插入排序、Shell排序
- 归并排序
- 桶式排序
- 基数排序
冒泡排序
排序思想：
相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其它的数进行类似操作。
案例
/**
* 3.数组元素的排序
*
*
*
* @author Administrator
*
*/
public class ArrayTest3 {
public static void main(String[] args) {
int[] arr = new int[]{-43,23,9,-43,0,222,1,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.println(arr[i] + " ");
}
}
}
排序方法的选择
(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜；
(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
练习6
案例
/**
* 使用简单数组
(1)创建一个名为ArrayExer的类，在main()方法中声明array1和array2两个变量，他们是int[]类型的数组。
(2)使用大括号{}，把array1初始化为8个素数：2,3,5,7,11,13,17,19。
(3)显示array1的内容。
(4)赋值array2变量等于array1，修改array2中的偶索引元素，使其等于索引值(如array[0]=0,array[2]=2)。打印出array1。
思考：array1和array2是什么关系？array1和array2指向堆空间中同一个数组。
拓展：修改题目，实现array2对array1数组的复制
* @author Administrator
*
*/
public class ArrayExer {
public static void main(String[] args) {
int[] array1,array2;
array1 = new int[]{2,3,5,7,11,13,17,19};
//遍历array1:
for(int i = 0;i < array1.length;i++){
System.out.print(array1[i] + " ");
}
//赋值array2变量等于array1
array2 = array1;//此时，array1和array2指向堆空间中同一个数组。
//修改array2中的偶索引元素
for(int i = 0;i < array2.length;i++){
if(i % 2 == 0){
array2[i] = i;
}
}
//遍历array1:
System.out.println();
for(int i = 0;i < array1.length;i++){
System.out.print(array1[i] + " ");
}
}
}
3-5 Arrays工具类的使用
案例
/**
* 3-5 Arrays:操作数组的工具类
*
*
*/
public class ArraysTest {
public static void main(String[] args) {
int[] arr1 = {1,2,2,34,5,6};
int[] arr2 = {2,1,2,34,5,6};
//1.equals():比较两个数组的元素，是否完全相同。
boolean b = Arrays.equals(arr1, arr2);
System.out.println(b);
//2.toString():输出显示数组的具体的元素
System.out.println(arr1);//地址值
System.out.println(Arrays.toString(arr1));
//3.将数组的所有元素重新赋值，赋值为参数2的值
//Arrays.fill(arr1, 10);
//System.out.println(Arrays.toString(arr1));
//4.sort():排序,底层使用的是快速排序实现的。
Arrays.sort(arr1);
System.out.println(Arrays.toString(arr1));//[1, 2, 2, 5, 6, 34]
//5.binarySearch():使用二分法，在数组中查找指定元素的索引。前提：要求此数组是有序的。
int index = Arrays.binarySearch(arr1, 55);
System.out.println(index);
//6.copyOf()复制指定的数组，用零截取或填充（如有必要），以便复制具有指定的长度。
int[] arr4 = Arrays.copyOf(arr3, 20);
System.out.println(Arrays.toString(arr4));
}
}
3-6 数组使用中的常见异常
案例
/**
* 3-6数组中的常见异常：
*
* 1.数组角标越界异常：ArrayIndexOutOfBoundsException
*
* 2.空指针异常：NullPointerException
*
*
*/
public class ArrayExceptionTest {
public static void main(String[] args) {
//1.数组角标越界异常：ArrayIndexOutOfBoundsException
int[] arr1 = new int[10];//角标：0-9
arr1[0] = 10;
arr1[9] = 20;
// arr1[10] = 30;
// arr1[-1] = 1;
//2.空指针异常：NullPointerException
//举例1：
// int[] arr2 = new int[10];
// arr2 = null;
// System.out.println(arr2[0]);//空指针异常
//举例2：
// int[][] arr3 = new int[3][];
// System.out.println(arr3[0]);//null
//// arr3[0] = new int[]{1,2,3};
// System.out.println(arr3[0][0]);//空指针异常
//举例3：
String[] arr4 = new String[4];
System.out.println(arr4[0].toString());
}
}
银行提款机项目
import java.util.Arrays;
import java.util.Scanner;
/**
* @author Heaton
* @email tzy70416450@163.com
* @date 2018/9/12 0012 15:07
* @describe 银行提款机
* 注册
* 登陆
* -查询余额
* -转账
* -提款
* -存款
* -返回上一级
* 退出
*/
public class BankATM {
public static void main(String[] args) {
String[] usernames = new String[1];
Arrays.fill(usernames, "");
int[] passwords = new int[1];
double[] balances = new double[1];
int index = 0;
a:
while (true) {
if(Arrays.binarySearch(usernames,"")<0){
usernames = Arrays.copyOf(usernames, usernames.length * 2);
passwords = Arrays.copyOf(passwords,passwords.length*2);
balances = Arrays.copyOf(balances,balances.length*2);
for (int i = 0; i < usernames.length; i++) {
if(usernames[i]==null){
usernames[i] = "";
}
}
}
System.out.println(Arrays.toString(usernames)+"_____"+usernames.length);
System.out.println(Arrays.toString(passwords)+"_____"+passwords.length);
System.out.println(Arrays.toString(balances)+"_____"+balances.length);
System.out.println("***欢迎来到BANK OF 橙子***");
System.out.println("1.注册");
System.out.println("2.登陆");
System.out.println("3.退出");
Scanner s = new Scanner(System.in);
System.out.println("请输入您选择的业务");
String business = s.nextLine();
if (business.equals("1")) {
i:
while (true) {
System.out.println("请输入用户名:");
String username = s.next();
System.out.println("请输入密码:");
int password = s.nextInt();
while (true) {
System.out.println("是否创建用户名为：" + username + ",密码：" + password + "的用户？\n确认请输入Y;重新创建输入N.");
String isNY = s.next();
if (isNY.equals("Y") || isNY.equals("y")) {
for (int i = 0; i < usernames.length; i++) {
if (usernames[i].equals("")) {
usernames[i] = username;
passwords[i] = password;
System.out.println("用户名为：" + username + ",密码：" + password + "的用户注册成功");
break i;
}
}
break;
} else if (isNY.toUpperCase().equals("N")) {
continue i;
} else {
System.out.println("输入错误请重新输入");
}
}
}
} else if (business.equals("2")) {
j:
while (true) {
System.out.println("请输入用户名:");
String username = s.next();
System.out.println("请输入密码:");
int password = s.nextInt();
boolean isUserTrue = true;
for (int i = 0; i < usernames.length; i++) {
if (usernames[i].equals(username)) {
index = i;
break;
}
if (i == usernames.length - 1) {
System.out.println("未找到该用户,请重新输入");
isUserTrue = false;
continue j;
}
}
if (passwords[index] != password && isUserTrue) {
System.out.println("账户密码错误!请重新输入");
continue j;
}
System.out.println("登陆成功");
k:
while (true) {
System.out.println(" * -1.查询余额\n" +
" * -2.转账\n" +
" * -3.提款\n" +
" * -4.存款\n" +
" * -5.返回上一级");
System.out.println("请输入你要的业务");
switch (s.next()) {
case "1":
System.out.println("您的账户余额为：" + balances[index]);
break;
case "2":
b:
while (true){
int index2 = 0;
System.out.println("请输入对方用户名");
String name = s.next();
for (int i = 0; i < usernames.length; i++) {
if(i==index){
continue ;
}
if(!usernames[i].equals(name)){
System.out.println("未找到该用户；请重新输入用户名");
continue ;
}else{
index2 = i;
System.out.println("请输入转账金额");
double transferAmount = s.nextDouble();
if (balances[index] >= transferAmount) {
balances[index] = balances[index] - transferAmount;
balances[index2] = balances[index2] + transferAmount;
System.out.println("转账成功");
break b;
}else{
System.out.println("转账失败，这不是信用卡，亲！");
}
}
}
}
break ;
case "3":
System.out.println("您的账户余额为：" + balances[index]);
System.out.println("请输入您要提款的金额");
double withdrawalAmount = s.nextDouble();
if (balances[index] >= withdrawalAmount) {
balances[index] = balances[index] - withdrawalAmount;
System.out.println("提款成功");
}else{
System.out.println("提款失败，这不是信用卡，亲！");
}
break;
case "4":
System.out.println("您的账户余额为：" + balances[index]);
System.out.println("请输入您要存款的金额");
double depositAmount = s.nextDouble();
balances[index] += depositAmount;
System.out.println("存款成功");
break;
case "5":
continue a;
default:
System.out.println("输入错误，请重新输入");
continue k;
}
}
}
} else if (business.equals("3")) {
break;
} else {
System.out.println("输入错误请重新输入");
}
}
}
}