logo
搜索
我的图书馆

发文章

发文工具

其他工具

留言交流
搜索
分享

第四章、数组（续）

 印度阿三17 2019-07-12

内容

  • 数组查找
  • 数组的排序
  • 二维数组的初始化
  • 二维数组的遍历

学习目标

  • 掌握数组的顺序查找
  • 理解数组的二分查找
  • 掌握数组的冒泡排序
  • 了解数组的简单选择排序
  • 了解二维数组的初始化
  • 了解二维数组的遍历

第四章 数组（续）

4.9.6 数组的顺序查找

顺序查找：挨个查看

要求：对数组元素的顺序没要求

顺序查找示例代码：

//查找value第一次在数组中出现的index
public static void main(String[] args){
    int[] arr = {4,5,6,1,9};
    int value = 1;
    int index = -1;

    for(int i=0; i<arr.length; i  ){
        if(arr[i] == value){
            index = i;
            break;
        }
    }

    if(index==-1){
        System.out.println(value   "不存在");
    }else{
        System.out.println(value   "的下标是"   index);
    }
}

4.9.7 数组的二分查找

二分查找：对折对折再对折

要求：要求数组元素必须支持比较大小，并且数组中的元素已经按大小排好序

[外链图片转存失败(img-y4BdgpCw-1562937709596)(imgs/1561509956568.png)]

/*
2、编写代码，使用二分查找法在数组中查找 int value = 2;是否存在，如果存在显示下标，不存在显示不存在。
已知数组：int[] arr = {1,2,3,4,5,6,7,8,9,10};
*/
class Exam2{
	public static void main(String[] args){
		int[] arr = {2,5,7,8,10,15,18,20,22,25,28};//数组是有序的
		int value = 18;
		
        int index = -1;
		int left = 0;
        int right = arr.length - 1;
        int mid = (left   right)/2;
        while(left<=right){
            //找到结束
            if(value == arr[mid]){
                index = mid;
                break;
            }//没找到
            else if(value > arr[mid]){//往右继续查找
                //移动左边界，使得mid往右移动
                left = mid   1;
            }else if(value < arr[mid]){//往左边继续查找
                right = mid - 1;
            }
            
            mid = (left   right)/2;
        }
        
        if(index==-1){
    		System.out.println(value   "不存在");
		}else{
    		System.out.println(value   "的下标是"   index);
		}
        
	}
}

4.9.8 冒泡排序

Java中的经典算法之冒泡排序（Bubble Sort）

原理：比较两个相邻的元素，将值大的元素交换至右端。

思路：依次比较相邻的两个数，将小数放到前面，大数放到后面。

​ 即第一趟，首先比较第1个和第2个元素，将小数放到前面，大数放到后面。

​ 然后比较第2个和第3个元素，将小数放到前面，大数放到后面。

​ 如此继续，直到比较最后两个数，将小数放到前面，大数放到后面。

​ 重复第一趟步骤，直至全部排序完成。

例如：冒泡：从小到大，从左到右两两比较
/*
{6,3,8,2,9,1}
	第一轮：
	第1次：arr[0]与arr[1]比较，6>3成立，就交换，{3,6,8,2,9,1}
	第2次：arr[1]与arr[2]比较，6>8不成立，不交换{3,6,8,2,9,1}
	第3次：arr[2]与arr[3]比较，8>2成立，就交换，{3,6,2,8,9,1}
	第4次：arr[3]与arr[4]比较，8>9不成立，不交换{3,6,2,8,9,1}
	第5次：arr[4]与arr[5]比较，9>1成立，就交换，{3,6,2,8,1,9}
	
	第一轮结果：{3,6,2,8,1,9}   9已经到达正确位置，下一轮不用在参与

	第二轮：
	第1次：arr[0]与arr[1]比较，3>6不成立，不交换{3,6,2,8,1,9}
	第2次：arr[1]与arr[2]比较，6>2成立，就交换，{3,2,6,8,1,9}
	第3次：arr[2]与arr[3]比较，6>8不成立，不交换{3,2,6,8,1,9}
	第4次：arr[3]与arr[4]比较，8>1成立，就交换，{3,2,6,1,8,9}
	
	第二轮结果：{3,2,6,1,8,9}   8已经到达正确位置，下一轮不用在参与
	
	第三轮：
	第1次：arr[0]与arr[1]比较，3>2成立，就交换，{2,3,6,1,8,9}
	第2次：arr[1]与arr[2]比较，3>6不成立，不交换{2,3,6,1,8,9}
	第3次：arr[2]与arr[3]比较，6>1成立，就交换，{2,3,1,6,8,9}
	
	第三轮结果：{2,3,1,6,8,9}   6已经到达正确位置，下一轮不用在参与
	
	第四轮：
	第1次：arr[0]与arr[1]比较，2>3不成立，不交换{2,3,1,6,8,9} 
	第2次：arr[1]与arr[2]比较，3>1成立，就交换，{2,1,3,6,8,9} 
	
	第四轮结果：{2,1,3,6,8,9}    3已经到达正确位置，下一轮不用在参与
	
	第五轮
	第1次：arr[0]与arr[1]比较，2>1成立，就交换，{1,2,3,6,8,9}
	
	第五轮结果：{1,2,3,6,8,9}   2已经到达正确位置，下一轮不用在参与
	
	剩下1，肯定是最小的了，不用比较了
	
	6个元素，比较了5轮， n个元素需要n-1轮
	每一轮比较很多次
*/

示例代码：


	public static void main(String[] args){
		int[] arr = {6,3,8,2,9,1};  //arr.length = 6
		
		//i=1,2,3,4,5  一共5轮
		for(int i=1; i<arr.length; i  ){//轮数
			/*
			i=1，第1轮，j=0,1,2,3,4   arr[j]与arr[j 1]
			i=2，第2轮，j=0,1,2,3     arr[j]与arr[j 1]
			i=3，第3轮，j=0,1,2       arr[j]与arr[j 1]
			i=4，第4轮，j=0,1         arr[j]与arr[j 1]
			i=5，第5轮，j=0           arr[j]与arr[j 1]
			
			j=0, j<=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]   " ");
		}
	}

示例代码：从大到小，从右到左

char[] arr = {'h','e','l','l','o','j','a','v','a'};
for(int i=1; i<arr.length; i  ){//外循环的次数 = 轮数 = 数组的长度-1
    /*
    第1轮，i=1，从右到左两两比较，arr[8]与arr[7]，arr[7]与arr[6]....arr[1]与arr[0]
    第2轮，i=2，从右到左两两比较，arr[8]与arr[7]，arr[7]与arr[6]....arr[2]与arr[1]
    ...
    第8轮，i=8，从右到左两两比较，arr[8]与arr[7]
    		   arr[j]与arr[j-1]
    找两个关键点：（1）j的起始值：8（2）找j的终止值，依次是1,2,3,。。。8，得出j>=i
    */
    for(int j=8; j>=i; j--){
        //从大到小，后面的元素 > 前面的元素，就交换
        if(arr[j]>arr[j-1]){
            int temp = arr[j];
            arr[j] = arr[j-1];
            arr[j-1] = temp;
        }
    }
}

4.9.9 简单选择排序

[外链图片转存失败(img-GbkrHomt-1562937709601)(imgs/1561513110004.png)]

[外链图片转存失败(img-bckfULgD-1562937709603)(imgs/1561513135868.png)]

示例代码：简单的直接选择排序

int[] arr = {49,38,65,97,76,13,27,49};

for(int i=1; i<arr.length; i  ){//外循环的次数 = 轮数 = 数组的长度-1
    //（1）找出本轮未排序元素中的最值
    /*
    未排序元素：
    第1轮：i=1,未排序，[0,7]
    第2轮：i=2,未排序，[1,7]
    ...
    第7轮：i=7,未排序，[6,7]
    
    每一轮未排序元素的起始下标：0,1,2,3,4,5,6，正好是i-1的
    未排序的后面的元素依次：
    第1轮：[1,7]  j=1,2,3,4,5,6,7
    第2轮：[2,4]  j=2,3,4,5,6,7
    。。。。
    第7轮：[7]    j=7
    j的起点是i，终点都是7
    */
    int max = arr[i-1];
    int index = i-1;
    for(int j=i; j<arr.length; j  ){
        if(arr[j] > max){
            max = arr[j];
            index = j;
        }
    }
    
    //（2）如果这个最值没有在它应该在的位置，就与这个位置的元素交换
    /*
    第1轮，最大值应该在[0]
    第2轮，最大值应该在[1]
    ....
    第7轮，最大值应该在[6]
    正好是i-1的值
    */
    if(index != i-1){
        //交换arr[i-1]与arr[index]
        int temp = arr[i-1];
        arr[i-1] = arr[index];
        arr[index] = temp;
    }
}

//显示结果
for(int i=0; i<arr.length; i  ){
	System.out.print(arr[i]);
}

4.10 二维数组

  • 二维数组：本质上就是元素为一维数组的一个数组。

  • 二维数组的标记：[][]

int[][] arr; //arr是一个二维数组，可以看成元素是int[]一维数组类型的一个数组

二维数组也可以看成一个二维表，行*列组成的二维表，只不过这个二维表，每一行的列数还可能不同。但是每一个单元格中的元素的数据类型是一致的，例如：都是int，都是String等

[外链图片转存失败(img-KNNs6fEF-1562937709607)(imgs/1561524724397.png)]

4.10.1 二维数组的声明

语法格式：

//推荐
元素的数据类型[][] 二维数组的名称;

//不推荐
元素的数据类型  二维数组名[][];
//不推荐
元素的数据类型[]  二维数组名[];

面试：

int[] x, y[];
//x是一维数组，y是二维数组

4.10.2 二维数组的初始化

1、静态初始化

元素的数据类型[][] 二维数组名 = new 元素的数据类型[][]{
			{元素1，元素2，元素3 。。。}, 
			{第二行的值列表},
			...
			{第n行的值列表}
		};

元素的数据类型[][] 二维数组名;
二维数组名 = new 元素的数据类型[][]{
			{元素1，元素2，元素3 。。。}, 
			{第二行的值列表},
			...
			{第n行的值列表}
		};
		
//以下格式要求声明与静态初始化必须一起完成
元素的数据类型[][] 二维数组的名称 = {
			{元素1，元素2，元素3 。。。}, 
			{第二行的值列表},
			...
			{第n行的值列表}
		};

举例：

	int[][] arr;
	arr = new int[][]{{1,2,3},{4,5,6},{7,8,9}};

	int[][] arr = new int[][]{{1,2,3},{4,5,6},{7,8,9}};

	int[][] arr = {{1,2,3},{4,5,6},{7,8,9}};//声明与初始化必须在一句完成

public class Array2Demo1 {
	public static void main(String[] args) {
		//定义数组
		int[][] arr = {{1,2,3},{4,5},{6}};
		
		System.out.println(arr);
		System.out.println(arr[0]);
		System.out.println(arr[1]);
		System.out.println(arr[2]);
		
		System.out.println(arr[0][0]); //1
		System.out.println(arr[1][0]); //4
		System.out.println(arr[2][0]); //6
		
		System.out.println(arr[0][1]); //2
		System.out.println(arr[1][1]); //5
		//越界
		System.out.println(arr[2][1]); //错误
	}
}

2、动态初始化（规则二维表：每一行的列数是相同的）

//（1）确定行数和列数
元素的数据类型[][] 二维数组名 = new 元素的数据类型[m][n];
	m:表示这个二维数组有多少个一维数组。或者说一共二维表有几行
	n:表示每一个一维数组的元素有多少个。或者说每一行共有一个单元格

//此时创建完数组，行数、列数确定，而且元素也都有默认值

//（2）再为元素赋新值
二维数组名[行下标][列下标] = 值;

public static void main(String[] args) {
    //定义一个二维数组
    int[][] arr = new int[3][2];
    
    //定义了一个二维数组arr
    //这个二维数组有3个一维数组的元素
    //每一个一维数组有2个元素
    //输出二维数组名称
    System.out.println(arr); //地址值	[[I@175078b
    
    //输出二维数组的第一个元素一维数组的名称
    System.out.println(arr[0]); //地址值	[I@42552c
    System.out.println(arr[1]); //地址值	[I@e5bbd6
    System.out.println(arr[2]); //地址值	[I@8ee016
    
    //输出二维数组的元素
    System.out.println(arr[0][0]); //0
    System.out.println(arr[0][1]); //0
    
    //...
}

3、动态初始化（不规则：每一行的列数可能不一样）

//（1）先确定总行数
元素的数据类型[][] 二维数组名 = new 元素的数据类型[总行数][];

//此时只是确定了总行数，每一行里面现在是null

//（2）再确定每一行的列数，创建每一行的一维数组
二维数组名[行下标] = new 元素的数据类型[该行的总列数];

//此时已经new完的行的元素就有默认值了，没有new的行还是null

//(3)再为元素赋值
二维数组名[行下标][列下标] = 值;

	public static void main(String[] args) {
		//定义数组
		int[][] arr = new int[3][];
        
        System.out.println(arr);	//[[I@175078b
        
        System.out.println([1][0]);//NullPointerException
		System.out.println(arr[0]); //null
		System.out.println(arr[1]); //null
		System.out.println(arr[2]); //null
		
		//动态的为每一个一维数组分配空间
		arr[0] = new int[2];
		arr[1] = new int[3];
		arr[2] = new int[1];
		
		System.out.println(arr[0]); //[I@42552c
		System.out.println(arr[1]); //[I@e5bbd6
		System.out.println(arr[2]); //[I@8ee016
		
		System.out.println(arr[0][0]); //0
		System.out.println(arr[0][1]); //0
		//ArrayIndexOutOfBoundsException
		//System.out.println(arr[0][2]); //错误
		
		arr[1][0] = 100;
		arr[1][2] = 200;
	}

4.10.3 相关表示方式

（1）二维数组的长度/行数：

​ 二维数组名.length

（2）二维数组的其中一行：

​ 二维数组名[行下标]

​ 行下标的范围：[0, 二维数组名.length-1]

（3）每一行的列数：

​ 二维数组名[行下标].length

​ 因为二维数组的每一行是一个一维数组

（4）每一个元素

​ 二维数组名[行下标][列下标]

4.10.4 二维数组的遍历

for(int i=0; i<二维数组名.length; i  ){
    for(int j=0; j<二维数组名[i].length; j  ){
        System.out.print(二维数组名[i][j]);
    }
    System.out.println();
}

4.10.5 二维数组练习

1、练习1

1、请使用二维数组存储如下数据，并遍历显示

1

2 2

3 3 3

4 4 4 4

5 5 5 5 5

	public static void main(String[] args){
		//1、声明一个二维数组，并且确定行数
		//因为每一行的列数不同，这里无法直接确定列数
		int[][]  arr = new int[5][];
		
		//2、确定每一行的列数
		for(int i=0; i<arr.length; i  ){
			/*
			arr[0] 的列数是1
			arr[1] 的列数是2
			arr[2] 的列数是3
			arr[3] 的列数是4
			arr[4] 的列数是5
			*/
			arr[i] = new int[i 1];
		}
		
		//3、确定元素的值
		for(int i=0; i<arr.length; i  ){
			for(int j=0; j<arr[i].length; j  ){
				arr[i][j] = i 1;
			}
		}
		
		//4、遍历显示
		for(int i=0; i<arr.length; i  ){
			for(int j=0; j<arr[i].length; j  ){
				System.out.print(arr[i][j]   " ");
			}
			System.out.println();
		}
		
	}

	public static void main(String[] args){
		//1、声明一个二维数组，并且初始化
        int[][] arr = {
            {1},
            {2,2},
            {3,3,3},
            {4,4,4,4},
            {5,5,5,5,5}
        };
		
		
		//2、遍历显示
		for(int i=0; i<arr.length; i  ){
			for(int j=0; j<arr[i].length; j  ){
				System.out.print(arr[i][j]   " ");
			}
			System.out.println();
		}
		
	}

	public static void main(String[] args){
		//1、声明一个二维数组，并且确定行数
		//因为每一行的列数不同，这里无法直接确定列数
		int[][]  arr = new int[5][];
		
		
		for(int i=0; i<arr.length; i  ){
			//2、确定每一行的列数
			arr[i] = new int[i 1];
			
			//3、确定元素的值
			for(int j=0; j<arr[i].length; j  ){
				arr[i][j] = i 1;
				
				System.out.print(arr[i][j]   " ");
			}

			System.out.println();
		}

	}

2、练习2

2、请使用二维数组存储如下数据，并遍历显示

1 1 1 1 1

2 2 2 2 2

3 3 3 3 3

4 4 4 4 4

public static void main(String[] args){
		int[][] arr = {
			{1,1,1,1,1},
			{2,2,2,2,2},
			{3,3,3,3,3},
			{4,4,4,4,4}
		};
		
		for(int i=0; i<arr.length; i  ){
			for(int j=0; j<arr[i].length; j  ){
				System.out.print(arr[i][j] " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		//1、声明二维数组，并确定行数和列数
		int[][] arr = new int[4][5];
		
		//2、确定元素的值
		for (int i = 0; i < arr.length; i  ) {
			for (int j = 0; j < arr.length; j  ) {
				arr[i][j] = i   1;
			}
		}
		
		//3、遍历显示
		for(int i=0; i<arr.length; i  ){
			for(int j=0; j<arr[i].length; j  ){
				System.out.print(arr[i][j]   " ");
			}
			System.out.println();
		}
	}

3、练习3

3、请使用二维数组存储如下数据，并遍历显示

		String[][] employees = {
		        {"10", "1", "段誉", "22", "3000"},
		        {"13", "2", "令狐冲", "32", "18000", "15000", "2000"},
		        {"11", "3", "任我行", "23", "7000"},
		        {"11", "4", "张三丰", "24", "7300"},
		        {"12", "5", "周芷若", "28", "10000", "5000"},
		        {"11", "6", "赵敏", "22", "6800"},
		        {"12", "7", "张无忌", "29", "10800","5200"},
		        {"13", "8", "韦小宝", "30", "19800", "15000", "2500"},
		        {"12", "9", "杨过", "26", "9800", "5500"},
		        {"11", "10", "小龙女", "21", "6600"},
		        {"11", "11", "郭靖", "25", "7100"},
		        {"12", "12", "黄蓉", "27", "9600", "4800"}
		    };

其中"10"代表普通职员，"11"代表程序员，"12"代表设计师，"13"代表架构师

[外链图片转存失败(img-rXLR9SsJ-1562937709611)(imgs/1561529559251.png)]

	public static void main(String[] args) {
		String[][] employees = {
		        {"10", "1", "段誉", "22", "3000"},
		        {"13", "2", "令狐冲", "32", "18000", "15000", "2000"},
		        {"11", "3", "任我行", "23", "7000"},
		        {"11", "4", "张三丰", "24", "7300"},
		        {"12", "5", "周芷若", "28", "10000", "5000"},
		        {"11", "6", "赵敏", "22", "6800"},
		        {"12", "7", "张无忌", "29", "10800","5200"},
		        {"13", "8", "韦小宝", "30", "19800", "15000", "2500"},
		        {"12", "9", "杨过", "26", "9800", "5500"},
		        {"11", "10", "小龙女", "21", "6600"},
		        {"11", "11", "郭靖", "25", "7100"},
		        {"12", "12", "黄蓉", "27", "9600", "4800"}
		    };
		System.out.println("员工类型\t编号\t姓名\t年龄\t薪资\t奖金\t股票\t");
		for (int i = 0; i < employees.length; i  ) {
			switch(employees[i][0]){
			case "10":
				System.out.print("普通职员");
				break;
			case "11":
				System.out.print("程序员");
				break;
			case "12":
				System.out.print("设计师");
				break;
			case "13":
				System.out.print("架构师");
				break;
			}
			for (int j = 1; j < employees[i].length; j  ) {
				System.out.print("\t"   employees[i][j]);
			}
			System.out.println();
		}
	}
来源：https://www./content-4-321701.html

    本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。
    转藏 分享 献花（0）

    来自： 印度阿三17 > 《开发》

    举报/认领

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多