2.5数组

数组

概述

数组是相同数据类型的多个数据的容器。这些元素按线性顺序排列。所谓线性顺序是指除第一个元素外，每一个元素都有唯一的前驱元素；除最后一个元素外，每一个元素都有唯一的后继元素。（“简单理解就是：一个跟一个顺序排列”）。 创建格式.

格式 1. 数据类型[] 数组名称 = new 数据类型[数组长度]; 格式 2. 数据类型[] 数组名称 = {数组内容 1,数组内容 2,数组内容 3…数组内容 n}; 格式 3. 数据类型[] 数组名; 格式 3 属于只创建了数组引用名， 并未在内存创建数组空间。 格式 4. 数据类型[] 数组名称 = new 数据类型[]{内容 1,内容 2,内容 3…内容 n};

1.常见数组的格式： (1) int []ages ={12,12,34,43,43,}; (2)Int [] ages = new int [10]; (3)int[] nums; nums = news int[]; (4) int ags = new int {12,45,45,45,};

下标 3. 可以理解为数组中内容的数字序号，从 0 开始 ，对于长度为 n 的数组，下标的范围是 0~n-1。 可以通过下标的方式访问数组中的每一个元素。

*例如： 创建 int 类型数组 arr ， 给数组 arr 的 5 下标赋值数据 ， 然后打印* int[] arr = new int[10]; arr[5] = 123; System.out.println(arr[5]);

数组长度获取 数组名称.length 注意 使用数组不当， 会出现如下问题： 数组未赋值： 空指针异常 超出长度的下标操作： 数组越界异常 注意：数组的长度在创建时就固定了。

多维数组

数组常用算法

冒泡排序 原理：

比较相邻的元素。如果第一个比第二个大，就交换他们两个。对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 升序排列的口诀: N个数字来排队 两两相比小靠前, 外层 循环length-1 内层循环length-i-1 降序排序的口诀: N个数字来排队 两两相比大靠前, 外层 循环length-1 内层循环length-i-1

二分查找 （折半查找）

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，二分查找要求数组数据必须采用顺序存储结构有序排列 首先，假设数组中元素是按升序排列，将数组中间位置的数据与查找数据比较，如果两者相等，则查找成功；否则利用 中间位置记录将数组分成前、后两个子数组，如果中间位置数据大于查找数据，则进一步查找前子数组，否则进一步查 找后子数组。 重复以上过程，直到找到满足条件的数据，则表示查找成功， 直到子数组不存在为止，表示查找不成功。

数组动态扩容

例题:

import java.util.Scanner; /*定义一个长度为 10 的整型数组 nums ，循环输入 10 个整数。 然后将输 入一个整数，查找此整数，找到输出下标， 没找到给出提示。*/ public class Demo1 { public static void main(String[] args) { //控制台输入 Scanner input = new Scanner(System.in); //创建一个长度为10的数组 int[] nums = new int[10]; System.out.println("请循环输入10个整数"); //接收控制台输入的10个整数，并把他们按输入顺序存放到数组中 for(int i=0;i<nums.length;i++){ System.out.println("请输入第"+(i+1)+"个整数："); int m = input.nextInt(); nums[i] = m; } System.out.println("请输入要查询的整数："); int n = input.nextInt(); //循环遍历数组 for (int i=0;i<nums.length;i++){ //如果数组当前元素不等于n 则跳过当前循环 if(n!=nums[i]){ continue; //如果当前元素等于n 则输出找到了+下标 }else { System.out.println("找到了，下标为"+i); break;//跳出循环 } } } } import java.util.Scanner; /*定义一个长度为 10 的整型数组 nums ，循环输入 10 个整数。 输出数组 的最大值、最小值。*/ public class Demo2 { public static void main(String[] args) { Scanner input = new Scanner(System.in); //创建长度为10的数组 int[] nums = new int[10]; System.out.println("请输入十个不重复整数："); for (int i=0;i<nums.length;i++){ //接收控制台输入并存入数组 nums[i] = input.nextInt(); } //冒泡排序从小到大 for(int i=0;i<nums.length-1;i++){ for(int j=0;j<nums.length-i-1;j++){ if(nums[j]>nums[j+1]){ int temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; } } } //数组已有序 从左到右 从小到大 System.out.println("最大值为"+nums[9]); System.out.println("最小值为"+nums[0]); } } /*给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为 目标值的那两个整数，并输出他们的数组下标 假设每种输入只会对应一个答案 ，不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以输出 0，1*/ public class Demo3 { public static void main(String[] args) { //定义数组 int[] nums = {2, 7, 11, 15}; //定义变量 int target = 9; //暴力循环 for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { //判断两数之和等于target if (nums[i] == target - nums[j]) { //新建一个数组array int[] array = new int[]{i, j}; //遍历数组 for (int k = 0; k < array.length; k++) { System.out.print(array[k] + " "); } } } } } } import java.util.Arrays; /*对数组{1，3，9，5，6，7，15，4，8}进行排序， 然后使用二分查找 6 并 输出排序后的下标。*/ public class Demo4 { public static void main(String[] args) { int[] nums = {1,3,9,5,6,7,15,48}; //冒泡排序 for(int i=0;i<nums.length-1;i++){ for(int j=0;j<nums.length-i-1;j++){ if(nums[j]>nums[j+1]){ int temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; } } } for(int i=0;i<nums.length-1;i++){ System.out.print(nums[i]+" "); } System.out.println(); //换行 //调用search方法 search(nums,6); } public static void search(int[] nums,int find) { int start = 0; int end = nums.length - 1; int middle = 0; while (start<=end) { middle = (start + end) / 2; if (nums[middle] == find) { System.out.println("找到了，下标为" + middle); return; //跳出当前方法 } else if (nums[middle] < find) { //把middle加1设置为起点 start = middle + 1; } else { //把middle减1设置为终点 end = middle - 1; } } System.out.println("没找到"); } } ``/*给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾， 同时保 持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0]*/ public class Demo1 { public static void main(String[] args) { //定义数组 int[] nums = {0,1,0,3,12}; //定义变量 int m=0; //循环 当元素不等于0的时候把元素往前赋值 for(int i=0;i<nums.length;i++){ if(nums[i]!=0){ nums[m] = nums[i]; m++; } } //把剩下的位置都赋值为0 for (int i=m;i<nums.length;i++){ nums[i] = 0; } //循环遍历数组 for (int i=0;i<nums.length;i++){ System.out.print(nums[i]+" "); } } } ```java /** * 今天同学们相约一起爬山游玩，为了更好的进行这场活动，大家准备推举 一个人作为出游的临时队长。 * 为了体现合理公平，大家提出了一个比较有趣的 规则。所有人围成一圈，顺序排号。从第一个人开始 * 报数（从 1 到 3 报数）， 凡报到 3 的人退出圈子，剩下的人继续报数，最后留下的当选为队长。 * 请你通过编写程序，求出一组人中的队长是原来第几位同学。 * */ public class Demo12 { public static void main(String[] args) { System.out.println("请输入爬山人数："); Scanner inPut = new Scanner(System.in); int a = inPut.nextInt(); //接收控制台输入来的数，赋值给a int[] arr = new int[a]; for (int i=0;i<arr.length;i++){ arr[i] = 1; } int m=1; //m=1,2,3,循环报数 int index = 0; int count = 0; while (true){ if (arr[index]==1){ if(m==3){ arr[index]=-1; count++; } m++; index++; }else { index++; } if(m==4){ m=1; } if(index==a){ index=0; } //最后剩下一个人的值为1，其余人值都为-1，则队长选出 if(count==a-1){ System.out.println("找到了，下标为"+index--); break; } } } }