Java常用算法原理剖析

用Java实现的所有算法(用于教育)

这些只是为了演示的目的。在Java标准库中有许多不同类型的实现，由于性能原因这些要好得多。

排序算法

气泡

从维基百科气泡排序，叫做下沉排序，是一种简单的排序算法，反复遍历要排序的列表，比较每一对相邻的项目，并在排序错误的情况下交换。遍历列表将被重复，直到不需要交换，这表明列表已被排序。

特性

• 最差情况下的性能O(n^2)
• 最佳案例表现O(N)
• 平均病例性能O(n^2)

查看算法行动

插入

从维基百科插入排序是一种简单的排序算法，每次构建最终排序数组(或列表)。在大型列表中，效率要比更高级的算法(如快速排序、堆排序或合并排序)低得多。

特性

• 最差情况下的性能O(n^2)
• 最佳案例表现O(N)
• 平均病例性能O(n^2)

查看算法行动

合并

合并排序(通常也是拼写合并)是一种高效的、通用的、基于比较排序算法。大多数实现都会产生稳定的排序，实现在排序的输出中保留相同元素的输入顺序。Mergesort是由JohnvonNeumann于1945年发明的分而治之的算法。

特性

• 最坏的情况性能O(N Log N)(典型)
• 最佳情况性能O(N Log N)
• 平均情况性能O(N Log N)

查看算法行动

速战速决

从维基百科快速排序(有时称为分区-交换排序)是一种有效的排序算法，是一种系统的方法，用于排列数组的元素。

特性

• 最差情况下的性能O(n^2)
• 最佳情况下O(N Log N)或O(N)具有三向分区
• 平均病例性能O(n^2)

查看算法行动

选择

将输入列表分为两个部分：已经排序项的子列表(在列表的前面(左)从左到右建立)和占据列表其余部分的待排序项的子列表。最开始排序子列表是空的，未排序子列表是整个输入列表。该算法通过查找未排序子列表中最小的(或最大的，取决于排序顺序)元素，将其与最左边的未排序元素交换(按排序顺序排列)，并将子列表边界向右移动。

特性

• 最差情况下的性能O(n^2)
• 最佳案例性能O(n^2)
• 平均病例性能O(n^2)

查看算法行动

壳

ShellSort是插入排序的一种推广，允许交换相距很远的项。思路是安排元素列表，以便从任何地方开始，考虑到每个第n个元素都会给出一个排序列表。这样的列表叫做h排序。等效地，可以被认为是h交错列表，每个元素都是单独排序的。

特性

• 最坏的性能O(Nlog 2 2n)
• 最佳情况性能O(N Log N)
• 平均病例性能取决于间隙序列

查看算法行动

时间紧图

比较排序算法(气泡排序、插入排序、选择排序)的复杂性

复杂性图

搜索算法

线性

线性搜索或顺序搜索是在列表中查找目标值的一种方法。会依次检查列表中的每个元素的目标值，直到找到匹配或搜索所有元素为止。线性搜索在最坏的线性时间运行，最多进行n个比较，其中n是列表的长度。

特性

• 最坏的性能O(N)
• 最佳案例表现O(1)
• 平均个案表现O(N)
• 最坏情况下空间复杂度O(1)迭代

二进制

此算法也叫半间隔搜索或对数搜索算法，查找目标值在排序数组中的位置。将目标值与数组的中间元素进行比较；如果不相等，则消除目标数组的一半，并在其余的一半上继续搜索，直到成功为止。

特性

• 最坏的性能O(Log N)
• 最佳案例表现O(1)
• 平均案例性能O(Log N)
• 最坏情况空间复杂度O(1)

ShellSort是插入排序的一种推广，允许交换相距很远的项。思路是安排元素列表，便于任何地方开始，考虑到每个第n个元素都会给出一个排序列表。这样的列表叫做h排序。等效地，可以被认为是h交错列表，每个元素都是单独排序的。

特性

• 最坏的性能O(Nlog 2 2n)
• 最佳情况性能O(N Log N)
• 平均病例性能取决于间隙序列

查看算法行动

与其他算法的链接

数据结构

• 袋

• 缓冲器

• HashMap

• 矩阵