一、二维数组的使用以及数组的几种排序算法讲解

2020-12-04 00:00:00 算法 数组 几种

数组的使用

  • Eclipse
    • 安装教程
    • HelloWrold
  • 数组
    • 特点
    • 分类
    • 快速上手
    • 数组的查找
    • 排序算法
    • 衡量排序算法的优劣
    • 分类
      • 内部排序
      • 外部排序
    • 排序的五大特征
    • 冒泡排序
    • Arrays工具类的使用
  • 其他
  • 小问题

Eclipse

安装教程

       我这里就不给大家演示安装了,因为这个软件是免费的而且网上有很多的教程,这里就给大家几个教程地址给大家参考

官网: https://www.eclipse.org/downloads/

百度教程: https://jingyan.baidu.com/article/b24f6c8261297286bfe5da13.html (这个是老版教程,好像新版只需要下载然后解压就能用,只是猜测!)

百度网盘地址: 链接:https://pan.baidu.com/s/1FPoZ9-rfyWk8SQ4Me6hpZQ
提取码:150q(这个是我现在在还在使用的,下载解压即可使用,会自动进行配置)

B站视频教程: https://www.bilibili.com/video/BV1wE411c7Q8?from=search&seid=13990133972073404749

一点点小建议

  1. 不要使用汉化包,因为在开发时基本没有人会用中文版的,英文版也就是刚开始有一点不习惯,多用一下就好了
  2. 如果完全没有用过的小伙伴可以先一边使用一边百度,也就是说当自己不知道该怎么办了就可以先百度一下然后找不到的话在问别人

HelloWrold

在控制台打印 HelloWrold

步骤:

  1. 创建项目
    《一、二维数组的使用以及数组的几种排序算法讲解》
    《一、二维数组的使用以及数组的几种排序算法讲解》

  2. 创建包,右键 src 然后选择 Package
    《一、二维数组的使用以及数组的几种排序算法讲解》
    《一、二维数组的使用以及数组的几种排序算法讲解》

  3. 创建类,右键刚才创好的包选择 class
    《一、二维数组的使用以及数组的几种排序算法讲解》
    《一、二维数组的使用以及数组的几种排序算法讲解》

  4. 编写代码并测试
    《一、二维数组的使用以及数组的几种排序算法讲解》
    《一、二维数组的使用以及数组的几种排序算法讲解》

数组

       数组(Array) 是多个相同类型的数据按一定顺序排列的集合,并使用一个名字命名,并通过编号的方式对这些数据进行统一管理。

特点

  1. 数组本身是引用数据类型,而数组中的元素可以是任何数据类型,包括基本数据类型和引用数据类型。
  2. 创建数组对象会在内存中开辟一整块连续的空间,而数组名中引用的是这块连续空间的首地址。
  3. 数组的长度一旦确定,就不能修改!
  4. 可以直接通过下标的方式调用指定位置的元素,速度很快。
  5. 数组是有序排列的

分类

  1. 按照维数: 一维数组、二维数组、三维数组 …
  2. 按照数组元素的类型: 基本数据类型元素的数组、引用数据类型元素的数组

快速上手

格式: 数据类型[] 数组名 = new 数据类型[长度]; 或 数据类型[] 数组名 = new 数据类型[]{m1,m2 … n};

一维数组的使用:

package com.laoyang.concord; 	//包名

public class ArrayTest {  		// 类名

	public static void main(String[] args) { 
		// 基本数据类型的声明和初始化
		int num;	 // 声明
		num = 10; 	// 初始化

		// 一维数组的声明和初始化
		int[] ids; 	// 声明
		/** * 第一种初始化方式:静态初始化 * 数组的初始化和数组元素的赋值操作同时进行 */
		ids = new int[] {  1, 2, 3, 4 }; // 初始化

		/** * 第二种初始化方式:动态初始化 * 数组的初始化和数组元素的赋值操作分开进行 */
		String[] names = new String[4];

		/* 错误的写法 int[] error1 = new int[]; //如果是使用动态初始化,那么必须要定义长度! int[3] error2= new int[]; //动态初始化定义的长度不可以定义在前面的中括号里! int[] error3 = new int[3]{1,2,3}; //不能同时在一个数组中进行静态初始化和动态初始化! int[] error4 = new long[3]; //前面是什么数据类型,后面就必须是什么数据类型 */

		/** * 调用数组指定位置的元素,通过下标的方式调用 数组的下标是从 0 开始的 */
		names[0] = "张三";
		names[1] = "李四";
		names[2] = "王五";
		names[3] = "赵六";
		//因为定义的长度为4,而names[4]已经是第五个值了,所以在运行的时候就会出现数组越界异常
		// names[4] = "老七"; 
		// 如果想要打印王五,那么直接打印names[2]即可
		System.out.println(names[2]);

		/** * 获取数组的长度:length */
		System.out.println(names.length);

		/** * 遍历数组,也就是一次性输出数组中所有的数据 * 1.可以使用上面的那种方法:names[下标] * 2.也可以使用上一章循环的方式 */
		for (int i = 0; i < names.length; i++) { 
			// 将 i 当作数组的下标,然后开始循环,第一次i=0,所以输出的就是names[0]...以此类推
			System.out.println(names[i]);
		}

		/** * 数组元素的默认初始化值 当我们没有自定义初始化值时,系统会自动给他一个默认值 */
		int[] arr = new int[5];
		char[] arr2 = new char[5];
		for (int i = 0; i < arr.length; i++) { 
			/** * 数组元素为整型时,默认值都是为:0 * 数组元素为浮点型时,默认值都是为:0.0 * 数组元素为char型时,默认值都是为:0 * 数组元素为布尔型时,默认值都是为:false * 数组元素为引用数据类型时,默认值都是为:null(注意:这个没有双引号!与char不同) */
			System.out.println("int类型:" + arr[i]);
			// 注意:char的这个0不是整型的,而是加了单引号的 '0',而且不会再控制台打印出来!效果和空格差不多
			System.out.println("char类型:" + arr2[i]);
		}
		
		/** * 小练习:在不运行的情况下理解并能推算出结果(一个电话号码) */
		int[] arrs = new int[]{ 8,2,1,0,3};
		int[] index = new int[]{ 2,0,3,2,4,0,1,3,2,3,3};
		String telephone = "";	//用于存放电话号码
		for (int i = 0; i < index.length; i++) { 
			/** * 采用套娃的方式我们就可以推算出 * 第一次循环时i=0,那么就可以得到index[0]=2 * 然后因为index是在arrs中的,所以arrs就变成了arrs[2],也就得出第一位为 1 * 以此类推... */
			telephone += arrs[index[i]];
		}
	}
}
package com.laoyang.concord;

import java.util.Scanner;	//使用 Alt+ / 快捷键进行导包

/** * 练习2 从键盘输入学生成绩,找出最高分,并输出学生成绩等级 * 成绩>=最高分-10 等级为 A * 成绩>=最高分-30 等级为 B * 其余 等级为 C */
public class ArrayDemo { 
	public static void main(String[] args) { 
		// 使用Scanner读取学生个数
		Scanner input = new Scanner(System.in);

		System.out.print("请输入学生人数:");
		int mark = input.nextInt();

		// 创建数组,存储学生成绩,动态初始化
		int[] marks = new int[mark];

		// 给数组中的元素赋值
		for (int i = 0; i < marks.length; i++) { 
			System.out.print("第" + (i + 1) + "位学生的成绩为:");
			marks[i] = input.nextInt();
		}

		// 获取数组中元素的最大值,也就是最高分
		int max = 0;
		for (int i = 0; i < marks.length; i++) { 
			if (max < marks[i]) { 
				max = marks[i];
			}
		}
		System.out.println("最高分为:" + max);

		// 根据每个学生成绩与最高分的差值,得到每个学生的等级然后输出
		for (int i = 0; i < marks.length; i++) { 
			if (marks[i] >= max - 10) { 
				System.out.println("第" + (i + 1) + "位学生的成绩等级为A");
			} else if (marks[i] >= max - 30) { 
				System.out.println("第" + (i + 1) + "位学生的成绩等级为B");
			} else { 
				System.out.println("第" + (i + 1) + "位学生的成绩等级为C");
			}
		}
	}
}

注意

  1. 如果是使用动态初始化,那么必须要定义长度!
  2. 动态初始化定义的长度不可以定义在前面的中括号里!
  3. 不能同时在一个数组中进行静态初始化和动态初始化!
  4. 前面是什么数据类型,后面就必须是什么数据类型,比如int[] i = new int[2]; 前面是int类型,那么后面也应该是int类型!
  5. 数组一旦初始化完成,长度就已经定义了!
  6. 一定要记住,数组的下标是从 0 开始的!很多人刚开始的时候会认为数组下标是从 1 开始。

二维数组的使用:

package com.laoyang.concord;

/** * 二维数组 * 规定:二维数组分为外层数组的元素和内层数组的元素 * 例如:int[][] arr = new int[3][2]; * 外层元素:arr[0]、arr[1]等 * 内层元素:arr[0][0]、arr[0][1]等 */
public class ArrayTest2 { 
	public static void main(String[] args) { 
		//二维数组的声明和初始化
		int[] nums = new int[]{ 1,2,2};	//一维数组
		
		//静态初始化
		int[][] arrs = new int[][]{ { 1,2,3},{ 4,5,6},{ 7,8}};	//二维数组
		//动态初始化1
		String[][] arrs2 = new String[3][2];
		//动态初始化2
		String[][] arrs3 = new String[3][];
		
		/*错误的写法 int[][] error1 = new int[4][3]{ {1,2,3},{4,5,6},{7,8}}; String[2][3] error2 = new String[][]; String[][] error3 = new String[][5]; 可以空第二个长度,但不可以空第一个长度 */
		
		//其它正确的写法(虽然也是正确的,但是不推荐使用)
		int[] arrs4[] = new int[][]{ { 1,2,3},{ 4,5,6},{ 7,8}};
		
		//调用数组的指定位置的元素
		System.out.println(arrs[0][1]); //2
		System.out.println(arrs2[1][1]);//null
		
		//这一种因为是只定义了一个长度,所以在调用前还需要自己手动在设置一下第二个的长度,否则就会报错
		arrs3[1] = new String[4];
		System.out.println(arrs3[1][0]);
		
		//获取数组的长度
		System.out.println(arrs2.length);    //3,在动态初始化中获取的是第一个中括号的长度
		System.out.println(arrs2[0].length); //2,如果在获取长度的时候标注了下标,那么获取的就是第二个中括号的长度
		System.out.println(arrs4.length);    //3,在静态初始化中获取的是每一个大括号,一个括号算一个长度
		System.out.println(arrs4[2].length); //2,获取的是下标为2的大括号中的值长度 
		
		//遍历二维数组,二维数组需要使用两个for循环,如果是三维,那就要使用三个,以此类推...
		for (int i = 0; i < arrs4.length; i++) { 
			for (int j = 0; j < arrs4[i].length; j++) { 
				System.out.println("arrs4---"+arrs4[i][j]);
			}
		}
		
		/** * 数组元素的默认初始化值 * 方式一:int[][] arr = new int[3][2]; * 外层元素的初始化值为:地址值 * 内层元素的初始化值为:与一维数组相同初始化情况相同 * 方式二:int[][] arr2 = new int[5][]; * 外层元素的初始化值为:null * 内层元素的初始化值为:不能调用,直接调用会导致报错 */
		int[][] arr = new int[3][2];	
		System.out.println(arr[0]);		//[I@2a139a55:一个中括号表示一维,I表示int类型,@后面的为地址
		System.out.println(arr[0][0]);  //0:二维数组调用下标输出时就是对应类型的默认值
		System.out.println(arr); 		//[[I@15db9742:两个中括号表示二维,I表示int类型,@后面的为地址
		
		int[][] arr2 = new int[5][];
		System.out.println(arr2[0]);	//null
// System.out.println(arr2[0][2]); //报错 
	}
}
package com.laoyang.concord;

public class ArrayDemo2 { 
	public static void main(String[] args) { 
		/** * 练习一:获取arr数组中所有元素的和 */
		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("arr数组元素总和为:" + sum);

		/** * 练习二:使用二维数组打印一个10行杨辉三角 * 杨辉三角:是二项式系数在三角形中的一种几何排列 */
		// 声明并初始化二维数组,这里不写第二个的长度原因是每一行的数据长度不同,所以暂时先不定义
		int[][] yangHui = new int[10][];

		// 给数组的元素赋值
		for (int i = 0; i < yangHui.length; i++) { 
			//i+1是因为i设置的默认值是0,但是第一行有一个值,所以需要加 1
			yangHui[i] = new int[i + 1];
			
			//给首个元素和最后一个元素赋值
			yangHui[i][0] = 1;	//首个元素 
			yangHui[i][i] = 1;	//最后一个元素
			
			//给每行的非首个元素和非最后一个元素赋值
			if (i > 1) { 
				/** * 每列都是从0开始,所以第一列是0第二列就是 1 * yangHui[i].length - 1表示从第0个元素到倒数第二个元素的长度 */
				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();
		}
	}
}

注意:

  1. 从数组底层的运行机制来看,其实没有多维数组。多维数组其实就是多个一维数组。

求数组中的最大值、最小值、总和、平均值

package com.laoyang.concord;

public class ArrayDemo3 { 
	public static void main(String[] args) { 
		int[] arr = new int[10];
		
		for (int i = 0; i < arr.length; i++) { 
			arr[i] = (int)(Math.random() * (99 - 10 + 1) + 10);
			System.out.print(arr[i] + "\t");
		}
		
		//最大值
		int max = arr[0];  //存放最大值
		for (int i = 1; i < arr.length; i++) { 
			if (max < arr[i]) { 
				max = arr[i];
			}
		}
		System.out.println("\n最大值为:" + max);
		
		//最小值
		int min = arr[0];  //存放最小值
		for (int i = 0; i < arr.length; i++) { 
			if (min > arr[i]) { 
				min = arr[i];
			}
		}
		System.out.println("最小值为:" + min);
		
		//总和
		int sum = 0;  //存放总和
		for (int i = 0; i < arr.length; i++) { 
			sum += arr[i];
		}
		System.out.println("总和为:" + sum);
		
		//平均值
		double avg = 0;
		for (int i = 0; i < arr.length; i++) { 
			avg = (double) sum / arr.length;
		}
		System.out.println("平均值为:" + avg);
	}
}

数组的查找

package com.laoyang.concord;

public class Seek { 
    public static void main(String[] args) { 
		//线性查找
        String[] arr = new String[]{ "XC","XM","XH"};
		String desc = "XM";
		boolean isFlag = true;
		for (int i = 0; i < arr.length; i++) { 
			if (desc.equals(arr[i])) { 
				System.out.println("找到了指定的元素,位置为" + i);
				isFlag = false;
				break;
			}
		}
		if (isFlag) { 
			System.out.println("不好意思,没有找到您想要的元素!");
		}
		
		/** * 二分法查找 * 前提:所要查找的数组必须有序! */
		int[] arr2 = new int[]{ 25,30,50,88,102,168,280};
		int des1 = 88;
		int head = 0; 				//初始的首索引
		int end = arr2.length - 1;	//初始的末索引
		boolean isFlag1 = true;
		while(head <= end){ 
			int middle = (head + end) / 2;	//找到数组的中间值
			if(des1 == arr2[middle]){ 
				System.out.println("找到了指定的元素,位置为" + middle);
				isFlag1 = false;
				break;
			}else if (arr2[middle] > des1) { 
				end = middle - 1;
			}else{ 
				head = middle - 1;
			}
		}
		if (isFlag1) { 
			System.out.println("不好意思,没有找到您想要的元素!");
		}
    }
}

排序算法

通常来说,排序的目的就是快速查找

衡量排序算法的优劣

  1. 时间复杂度: 分析关键字的比较次数和记录的移动次数
  2. 空间复杂度: 分析排序算法中需要多少辅助内存
  3. 稳定性: 若两个记录 A 和 B 的关键字值相等,但排序后 A、B的先后次序保持不变,则称这种排序算法是稳定的

分类

内部排序

整个排序过程不需要借助于外部存储器(如磁盘等),所有排序操作都在内存中完成。

十大内部排序算法:

  1. 选择排序:直接选择排序、推排序
  2. 交换排序:冒泡排序、快速排序(这两个经常使用)
  3. 插入排序:直接插入排序、折半插入排序、Shell排序
  4. 归并排序(了解)
  5. 桶式排序
  6. 基数排序

外部排序

       参与排序的数据非常多,数据量非常大,计算机无法将整个排序过程放在内存中完成,必须借助于外部存储器(如磁盘)。外部排序最常见的是多路归并排序。可以认为外部排序是多次内部排序组成。

排序的五大特征

  1. 输入: 算法有0个或多个输入,比如一个简单的函数就没有参数;

  2. 输出: 算法有1个或多个输出,如果没有输出这个算法就没有意义;

  3. 有穷性: 一个算法无限计算,可以在有自限时间内实现;

  4. 确定性: 算法每个步骤都应被精确定义,同样的直到输入只能有一种输出;

  5. 可行性: 算法的每一步都是可行的,在当前环境下可以实现。

冒泡排序

       冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

package com.laoyang.concord;

/** * 冒泡排序 */
public class Bubbling { ()
	public static void main(String[] args) { 
		int[] arr = new int[] {  12, 66, 35, 204, -121, -6, 11, 456 };
		// 数组长度-1表示把当前的值不算入其中
		for (int i = 0; i < arr.length - 1; i++) { 
			//数组长度-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");
		}
    }
}

Arrays工具类的使用

package com.laoyang.concord;

import java.util.Arrays;	//导包

/** * Arrays工具类的使用 */
public class ArraysTest { 

	public static void main(String[] args) { 
		// 1.boolean equals(int[] a,int[] b):判断两个数组是否相等
		int[] arr1 = new int[] {  1, 2, 3 };
		int[] arr2 = new int[] {  1, 3, 2 };
		boolean isEquals = Arrays.equals(arr1, arr2);
		System.out.println(isEquals);

		// 2.String toString(int[] a):输出数组信息
		System.out.println(Arrays.toString(arr1));

		// 3.void fill(int[] a,int val):将指定值填充到数组之中(将数组中的元素全部都变成指定的值)
		Arrays.fill(arr1, 5);
		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 index = Arrays.binarySearch(arr2, 2);		//如果返回负数,则表示未找到
		System.out.println("该元素的下标为:" + index);
	}
}

数组常见的异常

  1. 数组索引越界异常: ArrayIndexOutOfBoundsException
    产生的原因: 访问了不存在的索引
    更改: 不要访问不存在的索引

  2. 数组空指针异常: NullPointerException

    产生的原因: 数组类型变量没有指向任何数组

    更改: 不要让数组类型的变量赋值为null

其他

  1. 双击 Eclipse 不能正常启动?

    ① 环境变量是否正确配置,需要在命令行输入 javac.exe 或 java.exe 进行检查

    ② 是否正确安装了 JDK 和 JRE

    ③ 安装的 JDK 版本(32 或 64),必须要和 Eclipse 一致

    ④ 修改 Eclipse 安装目录下的 eclipse.ini 配置文件

  2. 内存中堆、栈(zhan)、方法区的了解

    ① 在函数中定义的一些基本类型的变量和对象的引用变量都是在函数的栈内存中分配的。当超过变量的作用 域后,java 会自动释放掉为该变量分配的内存空间。

    ② 堆内存用于存放有 new 创建的对象和数组。在堆中分配的内存,由 java 虚拟机自动垃圾回收来管理。

    ③ 方法区是系统分配的一个内存逻辑区域,是 JVM 在装载类文件时,用于存储类型信息的(类的描述信息)。

  3. 数据结构

    ① 数据与数据之间的逻辑关系,比如 集合、一对一、一对多、多对多

    ② 数据的存储结构:

     线性表:顺序表(比如数组)、链表、栈、队列树形结构:二叉树
    
  4. 算法(这里的是最简单的两种)

    ① 排序算法

    ② 搜索算法

小问题

  1. 写出一维数组和二维数组初始化的两种方式?

    	//一维数组:静态初始化
        int[] num = new int[]{ 1,2,3};
        //一维数组:动态初始化
        int[] nums = new int[5];
        //二维数组:静态初始化
        String[][] name = new String[][]{ { "小明","小美"},{ "小南"}};
        //二维数组:动态初始化
        String[][] names = new String[3][2];
    
  2. 不同类型的一维数组元素的默认初始化值各是多少?

    整型默认值为:0浮点型默认值为:0.0布尔类型默认值为:falsechar型默认值为:0(ASCII值)引用类型默认值为:null
    
  3. 如何反转数组中的值?

    public class ArrayTest {     
        public static void main(String[] args) { 
    	    int[] arr = { 10, 28, 9, 12, 38, 46, 59};        //数组的反转
    	        // 方式一:
    	        for (int i = 0; i < arr.length / 2; i++) { 
    	            int temp = arr[i];
    	            arr[i] = arr[arr.length - i - 1];
    	            arr[arr.length - i - 1] = temp;
    	        }
    	        for (int i = 0; i < arr.length; i++) { 
    	            System.out.print(arr[i] + "\t");
    	        }
    	
    	        System.out.println("\n-----------------------------");
    	
    	        // 方式二:
    	        for (int i = 0, j = arr.length - 1; i < j; i++, j--) { 
    	            int temp = arr[i];
    	            arr[i] = arr[j];
    	            arr[j] = temp;
    	        }
    	        for (int i = 0; i < arr.length; i++) { 
    	            System.out.print(arr[i] + "\t");
    	        }
    	    }
        }
    
    原文作者:万能的小白。
    原文地址: https://blog.csdn.net/Cicci_/article/details/119205112
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。

相关文章