[Java算法系列教程]-冒泡排序
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
Guava包里的Service用于封装一个服务对象的运行状态、包括start和stop等方法。例如web服务器,RPC服务器、计时器等可以实现这个接口。对此类服务的状态管理并不轻松、需要对服务的开启/关闭进行妥善管理、特别是在多线程环境下尤为复杂。Guava 包提供了一些基础类帮助你管理复杂的状态转换逻辑和同步细节。
一个服务正常生命周期有:
并发编程是一个难题,但是一个强大而简单的抽象可以显著的简化并发的编写。出于这样的考虑,Guava定义了ListenableFuture
接口并继承了JDK concurrent包下的Future
接口。
我们强烈地建议你在代码中多使用ListenableFuture
来代替JDK的Future
Futures
方法中需要它。ListenableFuture
编程比较容易。ListenableFuture
的扩展方法。希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
选择一个增量序列 t1,t2,……,tk,其中 ti > tj, tk = 1;
按增量序列个数 k,对序列进行 k 趟排序;
每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。仅增量因子为 1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
Java 8包含java.util.function和java.util.stream包,它代替Guava的函数式编程。
Guava的函数式编程可以在Java 8之前的Java版本上使用,也不像Java 8的函数编程需要笨拙而冗长地使用匿名类。
过度使用Guava的函数式编程习惯可能导致代码冗长、混乱、不可读和效率低下。这些都是Guava中最容易也是最常被滥用的部分,当您将代码变成“一行代码”时,Guava团队会哭。
LoadingCache<Key, Graph> graphs = CacheBuilder.newBuilder()
.maximumSize(1000)
.expireAfterWrite(10, TimeUnit.MINUTES)
.removalListener(MY_LISTENER)
.build(
new CacheLoader<Key, Graph>() {
public Graph load(Key key) throws AnyException {
return createExpensiveGraph(key);
}
});
缓存在很多场景下都是相当有用的。例如,计算或检索一个值的代价很高,并且对同样的输入需要不止一次获取值的时候,就应当考虑使用缓存。
单例模式(Singleton Pattern)是Java中最简单的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。
这种模式涉及到一个单一的类,该类负责创建自己的对象,同时确保只有单个对象被创建。这个类提供了一种访问其唯一的对象的方式,可以直接访问,不需要实例化该类的对象。
插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到 {\displaystyle O(1)} {\displaystyle O(1)}的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
Insertion Sort和打扑克牌时,从牌桌上逐一拿起扑克牌,在手上排序的过程相同。
举例:
Input: {5 2 4 6 1 3}。
首先拿起第一张牌, 手上有 {5}。
拿起第二张牌 2, 把 2 insert 到手上的牌 {5}, 得到 {2 5}。
拿起第三张牌 4, 把 4 insert 到手上的牌 {2 5}, 得到 {2 4 5}。
以此类推。
任何对 JDK 集合框架有经验的程序员都熟悉和喜欢 java.util.Collections 包含的工具方法。Guava 沿着这些路线提供了更多的工具方法:适用于所有集合的静态方法。这是 Guava 最流行和成熟的部分之一。
我们用相对直观的方式把工具类与特定集合接口的对应关系归纳如下:
接口 | JDK or Guava | Guava工具类 |
---|---|---|
Collection | JDK | Collections2:不要和 java.util.Collections 混淆 |
List | JDK | Lists |
Set | JDK | Sets |
SortedSet | JDK | Sets |
Map | JDK | Maps |
SortedMap | JDK | Maps |
Queue | JDK | Queues |
Multiset | Guava | Multisets |
Multimap | Guava | Multimaps |
BiMap | Guava | Maps |
Table | Guava | Tables |
有时候你需要实现自己的集合扩展。也许你想要在元素被添加到列表时增加特定的行为,或者你想实现一个Iterable,其底层实际上是遍历数据库查询的结果集。Guava为你,也为我们自己提供了若干工具方法,以便让类似的工作变得更简单。
针对所有类型的集合接口,Guava都提供了Forwarding抽象类以简化装饰者模式的使用。
Forwarding抽象类定义了一个抽象方法:delegate(),你可以覆盖这个方法来返回被装饰对象。所有其他方法都会直接委托给delegate()。例如说:ForwardingList.get(int)实际上执行了delegate().get(int)。
通过创建ForwardingXXX的子类并实现delegate()方法,可以选择性地覆盖子类的方法来增加装饰功能,而不需要自己委托每个方法——译者注:因为所有方法都默认委托给delegate()返回的对象,你可以只覆盖需要装饰的方法。
此外,很多集合方法都对应一个”标准方法[standardxxx]”实现,可以用来恢复被装饰对象的默认行为,以提供相同的优点。比如在扩展AbstractList 或JDK中的其他骨架类时,可以使用类似standardAddAll这样的方法。
让我们看看这个例子。假定你想装饰一个List,让其记录所有添加进来的元素。当然,无论元素是用什么方法——add(int, E), add(E), 或 addAll(Collection)——添加进来的,我们都希望进行记录,因此我们需要覆盖所有这些方法。