• 1. Java中数组结构及 经典排序算法解析讲师:宋红康 新浪微博:尚硅谷-宋红康
  • 2. 解析流程控制结构在开发时具体使用及面试陷阱 解读常用存储容器—数组的内存结构 多种排序算法实现及其复杂度分析
  • 3. 顺序结构 程序从上到下逐行地执行,中间没有任何判断和跳转。 分支结构 根据条件,选择性地执行某段代码。 有if…else和switch…case两种分支语句。 循环结构 根据循环条件,重复性的执行某段代码。 有while、do…while、for三种循环语句。 注:JDK1.5提供了foreach循环,方便的遍历集合、数组元素。 <1> 程序流程控制
  • 4. if语句三种格式: 1. if(条件表达式){ 执行代码块; } 2. if(条件表达式){ 执行代码块; } else{ 执行代码块; } 3. if(条件表达式){ 执行代码块; } else if (条件表达式){ 执行代码块; } …… else{ 执行代码块; } 分支语句1: if-else语句
  • 5. 分支结构2:switch语句 switch(表达式){ case 常量1: 语句1; break; case 常量2: 语句2; break; … … case 常量N: 语句N; break; default: 语句; break; }
  • 6. switch语句有关规则switch(表达式)中表达式的返回值必须是下述几种类型之一:byte,short,char,int,枚举,String; case子句中的值必须是常量,且所有case子句中的值应是不同的; default子句是可任选的,当没有匹配的case时,执行default break语句用来在执行完一个case分支后使程序跳出switch语句块;如果没有break,程序会顺序执行到switch结尾
  • 7. 条件判断练习编写程序:从键盘上读入一个学生成绩,存放在变量score中,根据score的值输出其对应的成绩等级: score>=90 等级:A 70=
  • 8. 面试陷阱题目1)对下列代码,若有输出,指出输出结果。 int x = 4; int y = 1; if (x > 2) { if (y > 2) System.out.println(x + y); System.out.println("atguigu"); } else System.out.println("x is " + x); 2)boolean b = true; if(b = false) System.out.println("a"); else if(b) System.out.println("b"); else if(!b) System.out.println("c"); else System.out.println("d");
  • 9. 循环结构循环语句功能 在某些条件满足的情况下,反复执行特定代码的功能 循环语句的四个组成部分 初始化部分(init_statement) 循环条件部分(test_exp) 循环体部分(body_statement) 迭代部分(alter_statement) 循环语句分类 for 循环 while 循环 do/while 循环
  • 10. for 循环语句语法格式 for (初始化表达式①; 布尔值测试表达式②⑤⑦; 更改表达式){ 语句或语句块③⑥ ; }1234
  • 11. while 循环语句语法格式 [初始化语句] while( 布尔值测试表达式){ 语句或语句块; [更改语句;] } 应用举例 public class WhileLoop { public static void main(String args[]){ int result = 0; int i=1; while(i<=100) { result += i; i++; } System.out.println("result=" + result); } }
  • 12. do-while 循环语句语法格式 [初始化语句] do{ 语句或语句块; [更改语句;] }while(布尔值测试表达式); 应用举例 public class WhileLoop { public static void main(String args[]){ int result = 0, i=1; do{ result += i; i++; }while(i<=100); System.out.println("result=" + result); } }
  • 13. 循环语句经典题目编写程序一:求1到100之间所有偶数的和。用for和while语句分别完成。 编写程序二:从键盘读入个数不确定的整数,并判断读入的正数和负数的个数,输入为0时结束程序。 编写程序三:100以内所有质数的输出。(嵌套循环)
  • 14. 数组是多个相同类型数据的组合,实现对这些数据的统一管理 数组中的元素可以是任何数据类型,包括基本类型和引用类型 数组属引用类型,数组型数据是对象(object),数组中的每个元素相当于该对象的成员变量<2> 数据存储容器之一:数组
  • 15. 一维数组声明一维数组的声明方式: type var[] 或 type[] var; 例如: int a[]; int[] a1; double b[]; Mydate[] c; //对象数组 Java语言中声明数组时不能指定其长度(数组中元素的数), 例如: int a[5]; //非法
  • 16. 一维数组初始化动态初始化:数组声明且为数组元素分配空间与赋值的操作分开进行 int[] arr = new int[3]; arr[0] = 3; arr[1] = 9; arr[2] = 8; 静态初始化:在定义数组的同时就为数组元素分配空间并赋值。 int a[] = new int[]{ 3, 9, 8}; int[] a = {3,9,8}; MyDate dates[]; dates = new MyDate[3]; dates[0] = new MyDate(22, 7, 1964); dates[1] = new MyDate(1, 1, 2000); dates[2] = new MyDate(22, 12, 1964);MyDate dates[] = { new MyDate(22, 7, 1964), new MyDate(1, 1, 2000), new MyDate(22, 12, 1964) }
  • 17. 内存结构的分配栈stack 局部变量,对象的引用堆heap new 出来的“东西”方法区字符串常量池静态域:静态的属性
  • 18. 内存结构的分配栈stack 局部变量,对象的引用堆heap new 出来的“东西”int[] scores = new int[5]; scores[0] = 78; scores[1] = 89; //... scores[4] = 56;String[] names = new String[]{“李雷”,“韩梅梅”,“Lucy”,“Lily“,”Poly”};scores:0x3344000000x3344788956names:0x7788nullnullnullnullnull0x7788李雷Poly
  • 19. 内存结构栈:stack堆 heap方法区字符串常量池静态域
  • 20. int[] studentNum = new int[5]; studentNum[0] = 1001; studentNum[1] = 1002; String[] str = new String[3];栈:引用变量名堆:new出来的“东西”studentNum:0x1234000000x1234studentNum[4]studentNum[0]10011002str:0x4455nullnullnull0x4455
  • 21. 数组元素的默认初始化数组是引用类型,它的元素相当于类的成员变量,因此数组一经分配空间,其中的每个元素也被按照成员变量同样的方式被隐式初始化。例如: public class Test { public static void main(String argv[]){ int a[]= new int[5];  System.out.println(a[3]); //a[3]的默认值为0 } } 对于基本数据类型而言,默认初始化值各有不同 对于引用数据类型而言,默认初始化值为null(注意与0不同!)
  • 22. 数组元素的引用定义并用运算符new为之分配空间后,才可以引用数组中的每个元素; 数组元素的引用方式:数组名[数组元素下标] 数组元素下标可以是整型常量或整型表达式。如a[3] , b[i] , c[6*i]; 数组元素下标从0开始;长度为n的数组合法下标取值范围: 0 —>n-1;如int a[]=new int[3]; 可引用的数组元素为a[0]、a[1]、a[2] 每个数组都有一个属性length指明它的长度,例如:a.length 指明数组a的长度(元素个数) 数组一旦初始化,其长度是不可变的
  • 23. 经典题目 从键盘读入学生成绩,找出最高分,并输出学生成绩等级。 成绩>=最高分-10 等级为’A’ 成绩>=最高分-20 等级为’B’ 成绩>=最高分-30 等级为’C’ 其余 等级为’D’ 提示:先读入学生人数,根据人数创建int数组,存放学生成绩。
  • 24. 经典面试题目题目1:一个数组,让数组的每个元素去除第一个元素,得到的商作为被除数所在位置的新值。 题目2:金额转换,阿拉伯数字的金额转换成中国传统的形式。如:105600123 => 壹亿零仟伍佰陆拾零万零仟壹佰贰拾叁圆整 题目3:创建一个长度为6的int型数组,要求取值为1-30,同时元素值各不相同 [1,30] 拓展:34-102; (int)(Math.random()*30) + 1; While(true){...}
  • 25. 多维数组二维数组[][]:数组中的数组格式1(动态初始化):int[][] arr = new int[3][2]; 定义了名称为arr的二维数组 二维数组中有3个一维数组 每一个一维数组中有2个元素 一维数组的名称分别为arr[0], arr[1], arr[2] 给第一个一维数组1脚标位赋值为78写法是:arr[0][1] = 78;格式2(动态初始化):int[][] arr = new int[3][]; 二维数组中有3个一维数组。 每个一维数组都是默认初始化值null (注意:区别于格式1) 可以对这个三个一维数组分别进行初始化 arr[0] = new int[3]; arr[1] = new int[1]; arr[2] = new int[2]; 注: int[][]arr = new int[][3]; //非法
  • 26. 格式3(静态初始化):int[][] arr = new int[][]{{3,8,2},{2,7},{9,0,1,6}}; 定义一个名称为arr的二维数组,二维数组中有三个一维数组 每一个一维数组中具体元素也都已初始化 第一个一维数组 arr[0] = {3,8,2}; 第二个一维数组 arr[1] = {2,7}; 第三个一维数组 arr[2] = {9,0,1,6}; 第三个一维数组的长度表示方式:arr[2].length;注意特殊写法情况:int[] x,y[]; x是一维数组,y是二维数组。 Java中多维数组不必都是规则矩阵形式
  • 27. int[][] i = new int[3][2];12i[0]i[1]i[2]i[0][1] = 12;int[][] i = new int[3][]; i[0] = new int[2]; i[1] = new int[3]; i[2] = new int[4];
  • 28. 经典题目题目4:使用二维数组打印一个 10 行杨辉三角. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 .... 【提示】 1. 第一行有 1 个元素, 第 n 行有 n 个元素 2. 每一行的第一个元素和最后一个元素都是 1 3. 从第三行开始, 对于非第一个元素和最后一个元素的元素. yanghui[i][j] = yanghui[i-1][j-1] + yanghui[i-1][j];
  • 29. 排序:假设含有n个记录的序列为{R1,R2,...,Rn},其相应的关键字序列为{K1,K2,...,Kn}。将这些记录重新排序为{Ri1,Ri2,...,Rin},使得相应的关键字值满足条Ki1<=Ki2<=...<=Kin,这样的一种操作称为排序。 通常来说,排序的目的是快速查找。衡量排序算法的优劣: 1.时间复杂度:分析关键字的比较次数和记录的移动次数 2.空间复杂度:分析排序算法中需要多少辅助内存 3.稳定性:若两个记录A和B的关键字值相等,但排序后A、B的先后次序保持不变,则称这种排序算法是稳定的。<3> 排序算法的实现与复杂度分析
  • 30. 排序算法分类:内部排序和外部排序。 内部排序:整个排序过程不需要借助于外部存储器(如磁盘等),所有排序操作都在内存中完成。 外部排序:参与排序的数据非常多,数据量非常大,计算机无法把整个排序过程放在内存中完成,必须借助于外部存储器(如磁盘)。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。
  • 31. 常用的内部排序选择排序 直接选择排序、堆排序 交换排序 冒泡排序、快速排序 插入排序 直接插入排序、折半插入排序、Shell排序 归并排序 桶式排序 基数排序
  • 32. (本页无文本内容)
  • 33. 各种内部排序方法性能比较1.从平均时间而言:快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序。 2.从算法简单性看:由于直接选择排序、直接插入排序和冒泡排序的算法比较简单,将其认为是简单算法,都包含在上图的“简单排序”中。对于Shell排序、堆排序、快速排序和归并排序算法,其算法比较复杂,认为是复杂排序。 3.从稳定性看:直接插入排序、冒泡排序和归并排序时稳定的;而直接选择排序、快速排序、 Shell排序和堆排序是不稳定排序 4.从待排序的记录数n的大小看,n较小时,宜采用简单排序;而n较大时宜采用改进排序。
  • 34. 排序方法的选择(1)若n较小(如n≤50),可采用直接插入或直接选择排序。 当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插入,应选直接选择排序为宜。 (2)若文件初始状态基本有序(指正序),则应选用直接插入、冒泡或随机的快速排序为宜; (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。
  • 35. 操作数组的工具类:Arraysjava.util.Arrays类包含了用来操作数组(比如排序和搜索)的各种方法。Arrays拥有一组static方法。 equals():比较两个array是否相等。array拥有相同元素个数,且所有对应元素两两相等。 fill():将值填入array中。  sort():用来对array进行排序。  binarySearch():在排好序的array中寻找元素。  另:System.arraycopy():array的复制。   
  • 36. 数组排序java.util.Arrays类的sort()方法提供了数组元素排序功能: import java.util.*; public class Sort { public static void main(String[] args) { int [] number = {5,900,1,5,77,30,64,700}; Arrays.sort(number); for(int i = 0; i < number.length; i++) System.out.println(number[i]); } }