Java中数组结构及经典排序算法解析

1、JavaJava中数组结构中数组结构及及经典经典排序算法解析排序算法解析讲师：宋红康讲师：宋红康 新浪微博：尚硅谷新浪微博：尚硅谷- -宋红康宋红康 解析流程控制结构在开发时具体使用及解析流程控制结构在开发时具体使用及面试面试陷阱陷阱 解读常用存储容器解读常用存储容器数组的内存数组的内存结构结构 多种排序算法实现及其复杂度分析多种排序算法实现及其复杂度分析l 顺序结构顺序结构 程序从上到下逐行地执行，中间没有任何判断和跳转。l 分支分支结构结构 根据条件，选择性地执行某段代码。 有ifelse和switchcase两种分支语句。l 循环循环结构结构 根据循环条件，重复性的执行某段代码。 有wh

2、ile、dowhile、for三种循环语句。 注：JDK1.5提供了foreach循环，方便的遍历集合、数组元素。if语句三语句三种格式种格式：1. if(条件表达式条件表达式)执行代码块；执行代码块； 2. if(条件表达式条件表达式)执行代码块；执行代码块； else执行代码块；执行代码块； 3. if(条件表达式条件表达式)执行代码块；执行代码块； else if (条件表达式条件表达式)执行代码块；执行代码块； else执行代码块；执行代码块； 分支语句分支语句1： if-else语句语句分支分支结构结构2：switch语句语句switch(表达式表达式)case 常量1:语句1;br

3、eak;case 常量2:语句2;break; case 常量N:语句N;break;default:语句;break; switch语句有关规则语句有关规则l switch(表达式)中表达式的返回值返回值必须是下述几种类型之一：byte，short，char，int，枚举，枚举，String；l case子句中的值必须是常量常量，且所有case子句中的值应是不同的；l default子句是可任选的可任选的，当没有匹配的case时，执行defaultl break语句用来在执行完一个case分支后使程序跳出switch语句块；如果没有break，程序会顺序执行到switch结尾条件判断练习条件

4、判断练习l 编写程序：从键盘上读入一个学生成绩，存放在变量score中，根据score的值输出其对应的成绩等级：score=90 等级：A70=score90 等级: B60=score70 等级: Cscore 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);

5、else if(!b) System.out.println(c); else System.out.println(d);循环循环结构结构l 循环语句功能循环语句功能在某些条件满足的情况下，反复执行特定代码的功能l 循环语句的四个组成部分循环语句的四个组成部分初始化部分（init_statement）循环条件部分（test_exp） 循环体部分（body_statement） 迭代部分（alter_statement） l 循环语句分类循环语句分类for 循环while 循环do/while 循环 for 循环语句循环语句l 语法格式语法格式 for (初始化表达式初始化表达式; 布尔值测试

6、表达式布尔值测试表达式; 更改表达式更改表达式) 语句或语句块语句或语句块 ； 1234while 循环语句循环语句l 语法格式语法格式 初始化语句初始化语句while( 布尔值测试表达式布尔值测试表达式) 语句或语句块语句或语句块;更改语句更改语句;l 应用举例应用举例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); do-while 循环语句

7、循环语句l 语法格式语法格式初始化语句初始化语句do 语句或语句块语句或语句块; 更改语句更改语句;while(布尔值测试表达式布尔值测试表达式); l 应用举例应用举例public class WhileLoop public static void main(String args) int result = 0, i=1; do result += i; i+; while(in-1；如int a=new int3; 可引用的数组元素为a0、a1、a2l 每个数组都有一个属性length指明它的长度，例如：a.length 指明数组a的长度(元素个数)数组一旦初始化，其长度是不可变的 经

8、典经典题目题目从键盘读入学生成绩，找出最高分，并输出学生成绩等级。成绩=最高分-10 等级为A 成绩=最高分-20 等级为B成绩=最高分-30 等级为C 其余 等级为D提示：先读入学生人数，根据人数创建int数组，存放学生成绩。经典面试题目经典面试题目题目题目1：一个数组，让数组的每个元素去除第一个元素，得到的商作为被除数所在位置的新值。题目题目2：金额转换，阿拉伯数字的金额转换成中国传统的形式。如：105600123 = 壹亿零仟伍佰陆拾零万零仟壹佰贰拾叁圆整题目题目3：创建一个长度为6的int型数组，要求取值为1-30，同时元素值各不相同 1,30 拓展：34-102;1) (int)(M

9、ath.random()*30) + 1;2) While(true).多维数组多维数组二维数组二维数组：数组中的数组：数组中的数组格式格式1（动态初始化）（动态初始化）：int arr = new int32; 定义了名称为arr的二维数组 二维数组中有3个一维数组 每一个一维数组中有2个元素 一维数组的名称分别为arr0, arr1, arr2 给第一个一维数组1脚标位赋值为78写法是：arr01 = 78;格式格式2（动态初始化）（动态初始化）：int arr = new int3; 二维数组中有3个一维数组。 每个一维数组都是默认初始化值null (注意：区别于格式1） 可以对这个三个

10、一维数组分别进行初始化 arr0 = new int3; arr1 = new int1; arr2 = new int2;注：intarr = new int3; /非法非法格式格式3（静态初始化）（静态初始化）：int arr = new int3,8,2,2,7,9,0,1,6; 定义一个名称为arr的二维数组，二维数组中有三个一维数组 每一个一维数组中具体元素也都已初始化 第一个一维数组 arr0 = 3,8,2; 第二个一维数组 arr1 = 2,7; 第三个一维数组 arr2 = 9,0,1,6; 第三个一维数组的长度表示方式：arr2.length; 注意特殊写法情况：int x

11、,y; x是一维数组，y是二维数组。 Java中多维数组不必都是规则矩阵形式int i = new int32;12i0i1i2i01 = 12;int i = new int3;i0 = new int2;i1 = new int3;i2 = new int4;经典题目经典题目题目题目4：使用二维数组打印一个 10 行杨辉三角.11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1 . 【提示】 1. 第一行有 1 个元素, 第 n 行有 n 个元素 2. 每一行的第一个元素和最后一个元素都是 1 3. 从第三行开始, 对于非第一个元素和最后一个元素的元素. yangh

12、uiij = yanghuii-1j-1 + yanghuii-1j;排序：排序：假设含有n个记录的序列为R1，R2，.,Rn,其相应的关键字序列为K1，K2，.,Kn。将这些记录重新排序为Ri1,Ri2,.,Rin,使得相应的关键字值满足条Ki1=Ki2=.=Kin,这样的一种操作称为排序。 通常来说，排序的目的是快速查找。衡量排序算法的优劣：衡量排序算法的优劣：1.时间复杂度：分析关键字的比较次数和记录的移动次数2.空间复杂度：分析排序算法中需要多少辅助内存3.稳定性：若两个记录A和B的关键字值相等，但排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。排序算法分类：排序算法分类：内

13、部排序内部排序和和外部排序外部排序。 内部排序：整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。 外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。常用的内部排序常用的内部排序l 选择排序选择排序 直接选择排序、堆排序l 交换排序交换排序 冒泡排序、快速排序l 插入插入排序排序 直接插入排序、折半插入排序、Shell排序l 归并排序归并排序l 桶式排序桶式排序l 基数排序基数排序各种内部排序方法性能比较各种内部排序方法性能比较1.

14、从平均时间而言从平均时间而言：快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序。2.从算法简单性看从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较简单，将其认为是简单算法，都包含在上图的“简单排序”中。对于Shell排序、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序。3.从稳定性看从稳定性看：直接插入排序、冒泡排序和归并排序时稳定的；而直接选择排序、快速排序、 Shell排序和堆排序是不稳定排序4.从待排序的记录数从待排序的记录数n的大小看的大小看，n较小时，宜采用简单排序；而n较大时宜采用改进排序。排序方法的选择排序方法的选择(1)若n较小(如n5

15、0)，可采用直接插入直接插入或直接选择排序直接选择排序。 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，应选直接选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用直接直接插插入入、冒泡冒泡或随机的快速排序快速排序为宜；(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序快速排序、堆排序堆排序或归并排序归并排序。操作数组的工具类：操作数组的工具类：Arraysl java.util.Arrays类包含了用来操作数组（比如排序和搜索）的各种方法。Arrays拥有一组static方法。 equals()：比较两个array是否相等。array拥有相同元素个数，且所有对应元素两两相等。fill()：将值填入array中。 sort()：用来对array进行排序。 binarySearch()：在排好序的array中寻找元素。 另：System.arraycopy()：array的复制