当前课程知识点:Java程序设计 > 第六章 对象群体的组织 > 6.3-常用算法 > 常用算法
大家好
欢迎回来继续学习Java语言程序设计
这一节我们来了解一下
Java集合框架中的一些常用算法
对集合运算的算法大多数
都是用来操作List的
有两个最值算法
是可以用于所有集合对象的
首先我们来了解一下排序算法
排序算法能够对List进行排序
使其中的元素
按照某种次序关系进行升序排列
排序算法它有两种形式
简单的形式就是
将元素按照自然次序排列
如果说这个集合中的元素
它本身有自然次序的话
那么可以用这种简单的办法
对自然次序排列
或者集合它实现了Comparable接口
那也就是说在这个实现
这个接口的方法的时候
我们为其中的元素
定义了如何比较大小这样的操作
那么这个算法
就可以在这个集合上
对它进行排序了
那么第二种形式
就是附加一个Comparator对象
作为参数
那么这个Comparator对象
就规定比较的规则
也就是说我们一些
自定义的类的对象
你说让它对这些对象进行排序
那么对象与对象之间
什么叫做大什么叫做小
它们的比较规则是什么
这些是不可能自然的
被编译器能够知道的
所以我们就需要
用这个Comparator对象
去为它定义比较规则
这样的话我们可以
按照自己的需要去定义比较规则
通常就可以用于实现反序
或者是特殊次序的这种排序
这个排序算法
它的算法性能上来说
首先第一个是速度还是比较快的
时间复杂度是nlog(n)的
关于什么是时间复杂度
这个也是需要大家
有一些数据结构的知识
就能够知道
如果说你没有学过数据结构
大致的知道这个算法
还是比较快的就可以了
另外它是稳定的
所谓稳定也是数据结构里面
对算法评价的一种角度
简单的解释就是如果这个序列中
有几个相等的元素
本身它们原始的
相对次序是某种次序
那么在排序过程中
应该说本来就相等的元素
它们的相对次序
你就没有必要去调换它了
如果你来回调换
那么这样就会造成
这个排序的不稳定
如果说本来相等的元素
在排序过程中它们的相对位置
相对次序是不调换的
绝对不会发生调换的
我们就可以认为它是稳定的
如果大家要详细了解这概念
也需要去学一下数据结构
那洗牌算法跟排序算法
正好它是反过来的
它是打乱次序用的
打乱一个List里面的元素的次序
以随机的方式重排List元素
那么这样操作的时候
它的任何次序的几率都是相等的
所以是这个打乱是随机的
一般在实现偶然性的
这个游戏的时候
这个算法就很有用
你看这算法的名字就叫洗牌算法
比如说你要
做一个排列的游戏的话
洗牌的时候那就会用到这个算法
还有一些常规的数据处理算法
叫reverse是将一个List中的元素
进行反向排列
那么fill是用来填充的
所以用指定的值去填充
或者叫做复写List中的每一个元素
这个操作用在
重新初始化List的时候
是很有用的
把它的所有的值都填充成一样的
copy接受两个参数
一个是源一个是目标
用来进行两个List对象之间的复制
这个时候目标List
必须至少与源一样长
如果它更长的话
那么多余的部分
原有的内容就不会受影响
好接下来我们再来了解一下
这个二分法查找算法
二分法查找是作用
在一个有序的序列中的
所以使用二分法查找的List
它必须已经按照
有序序列的方式排序好了
那么二分法查找使用有两种形式
一种形式是假定这个List它本身
是按照自然顺序升序排列的
首先List中的元素
它们之间要存在着自然顺序
其次要确实是按照这种自然顺序
升序排列好了
那么如果不是这样情况
我们可以使用第二种形式
第二种形式就要
增加一个Comparator对象
表示比较规则
那前提是这个List
原来是按照这个Comparator对象
所规定的这种排序规则
升序排列好的
另外二分法查找它还必须能够
对集合中的元素
对这个List中的元素
进行随机访问
所谓随机访问也就是说
我们可以按照序号
或者是指定位置
去任意访问其中的元素
这是随机访问
另一种我们知道叫顺序访问
比如链表就是顺序访问的
它必须从最开始的头节点
指向下一个再下一个再下一个
依次从前往后访问
那叫顺序访问的结构
那么二分法查找它应该是作用于
能够实现随机访问的
这样的集合类型
所以我们将一个binarySearch算法
作用到一个集合上的时候
它会首先检查
这个集合是否实现了
RandomAccess接口
也就是是否能够进行随机访问
是的话就将二分法查找算法
用在这上面
如果不是那么它
还是直接进行线性查找
求最小值和最大值的算法
是可以用于任何集合的
min和max算法
它是返回指定集合中的
最小值和最大值
那这两个算法
它的使用也分别都有两种形式
简单形式是按照元素的
自然顺序来找它的最值
另一种形式就是需要
给一个Comparator对象做参数
然后按照Comparator对象
给出的比较规则来返回最值
这一节我们了解了几个常用的算法
好
这一节内容就是这些
-1.0-导学
--1.0-导学
-1.1-Java与面向对象程序设计简介
--第一章 Java语言基础知识--1.1-Java与面向对象程序设计简介
-1.2-基本数据类型与表达式
-第一章 Java语言基础知识--1.2-基本数据类型与表达式
-1.3-数组
--1.3.1-数组
-第一章 Java语言基础知识--1.3-数组
-1.4-算法的流程控制
--第一章 Java语言基础知识--1.4-算法的流程控制
-1.5-第一章小结
-第一章编程练习题
-课件
--外部链接
-Java环境配置、Eclipse使用、Helloworld程序详解
--使用eclipse建立Java项目、编写和运行Java程序
-Java数据类型
--Java整数类型
--Java浮点类型
--数据类型实战
--数据类型转换
--Java强制类型转换精度损失示例与表达式中的数据类型转换
-Java数组
-Java变量
--Java的变量
-命令行参数
--命令行参数的介绍
-2.0-导学
--2.0-导学
-2.1-面向对象方法的特性
--第二章 类与对象--2.1-面向对象方法的特性
-2.2-1-类声明与对象创建
--第二章 类与对象--2.2-1-类声明与对象创建
-2.2-2-数据成员
--第二章 类与对象--2.2-2-数据成员
-2.2-3-方法成员
--第二章 类与对象--2.2-3-方法成员
-2.2-4-包
--2.2-4-包
--第二章 类与对象--2.2-4-包
-2.2-5-类的访问权限控制
--第二章 类与对象--2.2-5-类的访问权限控制
-2.3-1-对象初始化
--第二章 类与对象--2.3-1-对象初始化
-2.3-2-内存回收
--第二章 类与对象--2.3-2-内存回收
-2.4-枚举类
--2.4-枚举类
--第二章 类与对象--2.4-枚举类
-2.5-应用举例
--2.5-应用举例
-2.6-第2章小结
-第二章编程练习题
-课件
--第二章课件
-3.0-导学
--3.0-导学
-3.1.1-3.1.2-类继承的概念和语法
--第三章 类的重用--3.1.1-3.1.2-类继承的概念和语法
-3.1.3-隐藏和覆盖
--第三章 类的重用--3.1.3-隐藏和覆盖
-3.2-Object 类
--第三章 类的重用--3.2-Object 类
-3.3-终结类与终结方法
--第三章 类的重用--3.3-终结类与终结方法
-3.4-抽象类
--3.4-抽象类
--第三章 类的重用--3.4-抽象类
-3.5-泛型
--3.5-泛型
--第三章 类的重用--3.5-泛型
-3.6-类的组合
--3.6-类的组合
-3.7-小结
--3.7-小结
-第三章编程练习题
-课件
--课件
-4.0-导学
--导学
-4.1-接口
--接口
--第四章 接口与多态--4.1-接口
-4.2.1-4.2.2-类型转换
--类型转换
--第四章 接口与多态--4.2.1-4.2.2-类型转换
-4.2.3-方法的查找
--方法的查找
--第四章 接口与多态--4.2.3-方法的查找
-4.3-多态的概念
--多态的概念
--第四章 接口与多态--4.3-多态的概念
-4.4-多态的应用举例
--多态的应用举例
--第四章 接口与多态--4.4-多态的应用举例
-4.5-构造方法与多态性
--构造方法和多态性
--第四章 接口与多态--4.5-构造方法与多态性
-4.6-本章小结
--本章小结
-第四章编程作业
-课件
--课件
-5.0-导学
--5.0-导学
-5.1.1-5.1.2-异常处理的概念
--第五章 输入输出--5.1.1-5.1.2-异常处理的概念
-5.1.3-5.1.5-异常的处理
--第五章 输入输出--5.1.3-5.1.5-异常的处理
-5.2-输入输出流的概念
--输入输出流的概念
--第五章 输入输出--5.2-输入输出流的概念
-5.3.1-写文本文件
--写文本文件
--第五章 输入输出--5.3.1-写文本文件
-5.3.2-读文本文件
--读文本文件
--第五章 输入输出--5.3.2-读文本文件
-5.3.3-写二进制文件
--写二进制文件
--第五章 输入输出--5.3.3-写二进制文件
-5.3.4-读二进制文件
--读二进制文件
-5.3.5-File类
--File类
-5.3.6-处理压缩文件
--处理压缩文件
-5.3.7-对象序列化
--对象序列化
-5.3.8-随机文件读写
--随机文件读写
-5.4-本章小结
--本章小结
-课件
--课件
-6.0-导学
--导学
-6.1-Java集合框架介绍
--第六章 对象群体的组织--6.1-Java集合框架介绍
-6.2-主要接口及常用的实现类
--第六章 对象群体的组织--6.2-主要接口及常用的实现类
-6.3-常用算法
--常用算法
-6.4-数组实用方法
-6.5-基于动态数组的类型(Vector, ArrayList)
--基于动态数组的类型(Vector, ArrayList)
-6.6-遍历Collection
-6.7-Map接口及其实现
-6.8-第6章小结
--第6章小结
-课件
--课件
-7.0-导学
--导学
-7.1-绘图
--绘图
-7.2-Swing基础
--Swing基础
-7.3-Swing的层次
--Swing的层次
-7.4-布局管理
--布局管理
-7.5-内部类
--内部类
-7.6-事件处理的基本概念
-7.7-事件派发机制
--事件派发机制
-7.8-顶层容器
--7.8-顶层容器
-7.9-中间层容器(一)
-7.10-中间层容器(二)
-7.11-原子组件(一)
-7.12-原子组件(二)
-7.13-原子组件(三)
-7.14-其它Swing特性
-7.15-第7章小结
-课件
--课件