Java Learn(十九)

设计模式、查找算法、排序算法

常见的设计模式

创建型模式 — 工厂方法模式、抽象工厂模式、单例模式(掌握,会写)

结构型模式 — 装饰器模式、代理模式(看懂)

行为型模式 — 模版方法模式、观察者模式

常见的查找算法(重点)

线性查找算法(顺序查找算法)

(1)算法流程

a.使用目标元素与样本数列中的第一个元素起依次进行比较

b.若目标元素与样本数列中的元素相等,这表示查找成功

c.若目标元素与样本数列中的所有元素偶比较完毕也没有相等的元素,这表示查找失败

二分查找算法(折半查找算法)

(1)算法流程

a.假定样本数列的所有元素从小到大依次排列

b.使用目标元素与样本数列的中间元素比较大小,若相等则表示查找成功

c.若目标元素小于中间元素,则去中间元素的左边进行查找

d.若目标元素大于中间元素,则去中间元素的右边进行查找

e.直到使用目标元素与所有元素比较完毕时也没有相等的元素,则表示查找失败

常用的排序算法

冒泡排序算法(重中之重)

(1)算法流程

a.比较相邻位置的两个元素,若左边的元素大则交换两个元素的位置;

b.从开始的第一队一直到结尾的最后一对依次比较,进过这一轮,最后的元素将是这组元素的最大值;

c.重复步骤 b 对越来越少的元素进行比较,直到处理完毕所有元素为止(任意两个相邻位置的元素都无需交换位置为止);

插入排序算法

(1)算法流程

a.从第一个元素起,认定该元素已经有序;

b.取出下一个元素,让取出的元素与左边的有序数列从右向左依次比较;

c.若取出的元素小于左边的元素,则将左边的元素右移,也就是复制到下一个位置;

d.若取出的元素大于或等于左边的元素,则将取出的元素插入到左边元素的右边;

e.重复步骤 b,直到处理完毕所有元素为止;

选择排序算法

(1)算法流程

a.从第一个元素起取出该元素,并假定该元素是这组元素中的最小值,使用 min 记录下标;

b.使用 min 记录的最小值与后续元素依次进行比较;

c.若后续元素中找到比 min 记录的最小值还小的数据,则使用 min 记录该元素的下标;

d.直到 min 记录的最小值与后续所有元素比较完毕时,交换 min 记录的最小值和最开始假定的最小值,经过这一步最开始的元素将是该组元素中的最小值;

e.重复步骤 a,直到处理完毕所有元素为止;

快速排序算法

(1)算法流程

a.选择样本数列中的中间元素作为基准值,并单独保存;

b.分别使用左右两边的元素与基准值比较大小,将所有比基准值小的元素放在左边,将所有比基准值大或相等的元素放在右边,这个过程叫做分组;

c.直到左右两边元素的下标重合时,将基准值放到重合的位置;

d.分别对基准值两边的分组重复上述过程进行再次分组,使用递归的策略;