尚硅谷_宋红康_Java中数组结构及经典排序算法解析

Java中数组结构及经典排序算法解析,讲师：宋红康新浪微博：尚硅谷-宋红康,解析流程控制结构在开发时具体使用及面试陷阱解读常用存储容器数组的内存结构多种排序算法实现及其复杂度分析,顺序结构程序从上到下逐行地执行，中间没有任何判断和跳转。分支结构根据条件，选择性地执行某段代码。有ifelse和switchcase两种分支语句。循环结构根据循环条件，重复性的执行某段代码。有while、dowhile、for三种循环语句。注：JDK1.5提供了foreach循环，方便的遍历集合、数组元素。,程序流程控制,if语句三种格式：1.if(条件表达式)执行代码块；2.if(条件表达式)执行代码块；else执行代码块；,3.if(条件表达式)执行代码块；elseif(条件表达式)执行代码块；else执行代码块；,分支语句1：if-else语句,分支结构2：switch语句,switch(表达式)case常量1:语句1;break;case常量2:语句2;break;case常量N:语句N;break;default:语句;break;,switch语句有关规则,switch(表达式)中表达式的返回值必须是下述几种类型之一：byte，short，char，int，枚举，String；case子句中的值必须是常量，且所有case子句中的值应是不同的；default子句是可任选的，当没有匹配的case时，执行defaultbreak语句用来在执行完一个case分支后使程序跳出switch语句块；如果没有break，程序会顺序执行到switch结尾,条件判断练习,编写程序：从键盘上读入一个学生成绩，存放在变量score中，根据score的值输出其对应的成绩等级：score=90等级：A70=score90等级:B60=score2)System.out.println(x+y);System.out.println(atguigu);elseSystem.out.println(xis+x);2)booleanb=true;if(b=false)System.out.println(a);elseif(b)System.out.println(b);elseif(!b)System.out.println(c);elseSystem.out.println(d);,循环结构,循环语句功能在某些条件满足的情况下，反复执行特定代码的功能循环语句的四个组成部分初始化部分（init_statement）循环条件部分（test_exp）循环体部分（body_statement）迭代部分（alter_statement）循环语句分类for循环while循环do/while循环,for循环语句,语法格式for(初始化表达式;布尔值测试表达式;更改表达式)语句或语句块；,1,2,3,4,while循环语句,语法格式初始化语句while(布尔值测试表达式)语句或语句块;更改语句;应用举例publicclassWhileLooppublicstaticvoidmain(Stringargs)intresult=0;inti=1;while(i=最高分-10等级为A成绩=最高分-20等级为B成绩=最高分-30等级为C其余等级为D提示：先读入学生人数，根据人数创建int数组，存放学生成绩。,经典面试题目,题目1：一个数组，让数组的每个元素去除第一个元素，得到的商作为被除数所在位置的新值。题目2：金额转换，阿拉伯数字的金额转换成中国传统的形式。如：105600123=壹亿零仟伍佰陆拾零万零仟壹佰贰拾叁圆整题目3：创建一个长度为6的int型数组，要求取值为1-30，同时元素值各不相同1,30拓展：34-102;(int)(Math.random()*30)+1;While(true).,多维数组,inti=newint32;,i0,i1,i2,i01=12;,inti=newint3;i0=newint2;i1=newint3;i2=newint4;,经典题目,题目4：使用二维数组打印一个10行杨辉三角.11112113311464115101051.【提示】1.第一行有1个元素,第n行有n个元素2.每一行的第一个元素和最后一个元素都是13.从第三行开始,对于非第一个元素和最后一个元素的元素.yanghuiij=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的先后次序保持不变，则称这种排序算法是稳定的。,排序算法的实现与复杂度分析,排序算法分类：内部排序和外部排序。内部排序：整个排序过程不需要借助于外部存储器（如磁盘等），所有排序操作都在内存中完成。外部排序：参与排序的数据非常多，数据量非常大，计算机无法把整个排序过程放在内存中完成，必须借助于外部存储器（如磁盘）。外部排序最常见的是多路归并排序。可以认为外部排序是由多次内部排序组成。,常用的内部排序,选择排序直接选择排序、堆排序交换排序冒泡排序、快速排序插入排序直接插入排序、折半插入排序、Shell排序归并排序桶式排序基数排序,各种内部排序方法性能比较,1.从平均时间而言：快速排序最佳。但在最坏情况下时间性能不如堆排序和归并排序。2.从算法简单性看：由于直接选择排序、直接插入排序和冒泡排序的算法比较简单，将其认为是简单算法，都包含在上图的“简单排序”中。对于Shell排序、堆排序、快速排序和归并排序算法，其算法比较复杂，认为是复杂排序。3.从稳定性看：直接插入排序、冒泡排序和归并排序时稳定的；而直接选择排序、快速排序、Shell排序和堆排序是不稳定排序4.从待排序的记录数n的大小看，n较小时，宜采用简单排序；而n较大时宜采用改进排序。,排序方法的选择,(1)若n较小(如n50)，可采用直接插入或直接选择排序。当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插入，应选直接选择排序为宜。(2)若文件初始状态基本有序(指正序)，则应选用直接插入、冒泡或随机的快速排序为宜；(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。,操作数组的工具类：Arrays,java.util.Arrays类包含了用来操作数组（比如排序和搜索）的各种方法。Arrays拥有一组static方法。equals()：比较两个array是否相等。array拥有相同元素个数，且所有对应元素两两相等。fill()：将值填入array中。sort()：用来对array进行排序。binarySearch()：在排好序的array中寻找元素。另：System.arraycopy()：array的复制。,数组排序,java.util.Arrays类的sort()方法提供了数组元素排序功能：importjava.util.*