《Grocking Algorithms》一书的评论。一点个人看法，举几个例子。我希望这篇评论能帮助您了解您是否想读这本书，或者它是否不会在您的书架上占据一席之地。警告：大量文字）
![“摸索算法”或简单的算法介绍 - 1]()
![“摸索算法”或简单的算法介绍 - 2]()
算法通常以伪代码描述，例如在维基百科上。我们的代码并不完全是伪代码，稍后会详细介绍。现在让我们看看：
![“摸索算法”或轻松介绍算法 - 3]()
老实说，我错过了书中的一些细节，比如这个视频：“信息学。算法理论。欧几里得算法。” 例如，如果 a 小于 b，则在第一次运行期间 b 和 a 将交换位置，第二次时较大的值将除以较小的值。因此，参数的顺序并不重要。像往常一样，首先我们可以在一张纸上“感受”算法：
![“摸索算法”或轻松介绍算法 - 4]()
现在我们看一下代码：
![Java-университет]()
这里的一切都超级简单。如果我们有一个包含 0 或 1 个元素的数组，则无需对其进行排序。如果它更大，我们就取出数组的第一个元素并将其视为“枢轴元素”。我们创建 2 个新数组 - 第一个包含比主元大的元素，第二个包含比主元小的元素。我们递归地重复。这不是最好的选择，但还是最好记住。让我们用 Java 实现这个算法，但更正确。评论“ JavaScript 中的计算机科学：快速排序”中的材料将帮助我们解决这个问题。在写代码之前，我们再画一下来“感受一下”算法：首先，我们在一张纸上再画一下，来理解一下算法：
![“摸索算法”或轻松介绍算法 - 5]()
在我看来，最危险的时刻之一就是彻底解决问题。因此，我们将分几个小步骤来进行实施：
![“摸索算法”或轻松介绍算法 - 6]()
不好的（也就是我不喜欢的）是这本书顺便提到了合并排序，但没有提供任何示例或代码。更多详细信息可以在这里找到：“信息学。搜索和排序算法：归并排序”。因此，为了保持一致性，我们还是自己来做吧。当然，算法本身本质上是简单明了的：
![“摸索算法”或轻松介绍算法 - 7]()
书中指出队列会对我们有所帮助。此外，我们可以将元素添加到末尾并从头开始处理队列。这样的队列称为双向队列，英文称为Deque。书中建议使用一种数据结构——哈希表。将名称和邻居关联起来。对于编号的顶点，您可以简单地使用数组。这种顶点存储称为“相邻顶点列表”，书中没有提及。这对他们来说是一个缺点。让我们用 Java 来实现这个：
![“摸索算法”或轻松介绍算法 - 8]()
首先，我们需要了解如何表示我们的图表。我们可以将其表示为矩阵。关于 Habré 的文章将对我们有所帮助：Dijkstra 算法。在图表上寻找最佳路线。让我们使用邻接矩阵：
![“摸索算法”或简单的算法介绍 - 9]()
我们有一个 4 磅的袋子。您需要找到给定重量下最赚钱的商品。首先，让我们列出一个项目清单：
![“摸索算法”或轻松介绍算法 - 10]()
并给出计算公式：
![“摸索算法”或简单的算法介绍 - 11]()
“增长算法”或轻松介绍算法
介绍
几乎所有初级职位空缺都有“数据结构和算法知识”等要求。对于受过专业教育的人来说，算法属于普通课程，应该没有问题。但如果这些发展是从其他草原引入的呢？剩下的就是自己学习了。“谁该责备”这个问题是有答案的，但“该做什么”这个问题必须寻求答案。我们去书本上看看吧。我想告诉你一个。Grok 算法
在所有的著作中，我看到了《Grocking Algorithms》这样一本书。您可以在这里找到更多信息：“ 《增长算法。为程序员和好奇者提供的图解指南》一书。” 我很久以前就注意到这本书了，但是臭氧价格是680卢布。贵还是便宜——每个人自己决定。我已经以一半的价格购买了关于 Avito 的第二本书。所以我在圣彼得堡找到了它，买了它，然后去探索。这就是我决定与大家分享的内容。是的，书中没有 Java 代码，但有……其他代码，稍后会详细介绍。算法简介（选择排序）
因此，以一种简单的叙述形式，我们达到了表演的第一个排序。这就是选择排序。它的本质是我们从左到右（从0个元素到最后一个）遍历元素，并在剩余元素中寻找最大的。如果找到它，那么我们就交换现在所在的元素和最大的元素。首先想到数组的最简单的方式是：[5, 3, 6, 2, 10]。拿一张纸，一支笔（最简单、最便宜的方式），想象一下我们如何有一个左边框（左），一个当前索引（或右边框），有一个最小元素的索引。以及我们如何使用它。例如：
def selectionSort(array):
for left in range(0, len(array)):
minIndex = left
for right in range (left+1, len(array)):
if array[right] < array[minIndex]:
minIndex = right
if minIndex != left:
temp = array[left]
array[left] = array[minIndex]
array[minIndex] = temp
return array
print(selectionSort([5, 3, 6, 2, 10]))public static void selectionSort(int[] array) {
for (int left = 0; left < array.length; left++) {
int minIndex = left;
for (int right = left+1; right < array.length; right++) {
if (array[right] < array[minIndex]) {
minIndex = right;
}
}
if (minIndex != left) {
int temp = array[left];
array[left] = array[minIndex];
array[minIndex] = temp;
}
}
}递归
接下来我们被告知有递归这样的东西。首先，存在一个关于拥有 AxB 大小田地的农民的问题。有必要将这个领域分成相等的“正方形”。然后提到欧几里得算法。我不喜欢的是他们没有尝试编写其代码。但欧几里得算法简单有效：
def euclidean(a, b):
if a == 0 : return b
if b == 0 : return a
return euclidean (b, a % b)public static int euclid(int a, int b) {
if (a == 0) return b;
if (b == 0) return a;
return euclid(b, a%b);
}快速排序
快速排序是一个相当有趣的算法。书中并没有过多关注他。此外，仅给出最坏情况（当选择第一个元素时）的代码。然而，也许对于第一次认识的人来说这个例子会更容易记住。写一个糟糕的快速排序比根本不写要好。这是书中的一个例子：
def quicksort(array):
if len(array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
-
我们需要能够交换数组中的元素：
private static void swap(int[] array, int firstIndex, int secondIndex) { int temp = array[firstIndex]; array[firstIndex] = array[secondIndex]; array[secondIndex] = temp; } -
我们需要一个方法，将指定区间内的数组分为 3 部分
private static int partition(int[] array, int left, int right) { int pivot = array[(right + left) / 2]; while (left <= right) { while (array[left] < pivot) { left++; } while (array[right] > pivot) { right--; } if (left <= right) { swap(array, left, right); left++; right--; } } return left; }详情见上面的链接。简而言之，我们移动左光标，直到该元素小于枢轴。同样，从另一端移动右光标。如果光标不匹配，我们会进行交换。我们继续直到光标收敛。我们返回一个索引，将进一步处理分为两部分。
-
有一个分离，我们需要排序本身：
public static void quickSort(int[] array, int left, int right) { int index = 0; if (array.length > 1) { index = partition(array, left, right); if (left < index - 1) { quickSort(array, left, index - 1); } if (index < right) { quickSort(array, index, right); } } }也就是说，如果数组至少包含两个元素，那么它们就已经可以排序了。首先，我们将整个数组分为两部分，小于主元的元素和大于主元的元素。然后我们对每个结果部分执行类似的操作。
对于测试：
public static void main(String []args){ int[] array = {8,9,3,7,6,7,1}; quickSort(array, 0, array.length-1); System.out.println(Arrays.toString(array)); }
public static void mergeSort(int[] source, int left, int right) {
if ((right - left) > 1) {
int middle = (right + left) / 2;
mergeSort(source, left, middle);
mergeSort(source, middle + 1, right);
}
merge(source, left, right);
}public static void merge(int[] array, int from, int to) {
int middle = ((from + to) / 2) + 1;
int left = from;
int right = middle;
int cursor = 0;
int[] tmp = new int[to - from + 1];
while (left < middle || right <= to) {
if (left >= middle) {
tmp[cursor] = array[right];
System.out.println("Остаток справа: " + array[right]);
right++;
} else if (right > to) {
tmp[cursor] = array[left];
System.out.println("Остаток слева: " + array[left]);
left++;
} else if (array[left] <= array[right]) {
tmp[cursor] = array[left];
System.out.println("Слева меньше: " + array[left]);
left++;
} else if (array[right] < array[left]) {
tmp[cursor] = array[right];
System.out.println("Справа меньше: " + array[right]);
right++;
}
cursor++;
}
System.arraycopy(tmp, 0, array, from, tmp.length);
}println一切都清楚了。好吧，检查一下：
int array[] = {1, 7, 3, 6, 7, 9, 8, 4};
mergeSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));哈希表
本书还涉及哈希表。您不必自己实现它，哈希表的本质非常简单。毕竟Java也有哈希表的实现，java.util.HashTable。如果我们查看 HashTable 设备，我们会看到 Entry 数组位于其中。Entry是一个由Key-Value组合而成的记录。HashTable有initialCapacity——即初始大小。loadFactor——负载因子。默认值为 0.75。这个数字告诉您在数组负载达到什么程度（元素数/总量）时需要增加大小。在Java中它增加了2倍。书中解释说，哈希表之所以称为哈希表，是因为基于哈希函数，其中的数组单元（篮子）Entry。您还可以在这里阅读更多内容：图片中的数据结构。HashMap和LinkedHashMap。你也可以在书上读到。例如这里：“哈希表基础知识”
图，广度优先搜索（最短路径搜索）
图表可能是最有趣的主题之一。公平地说，本书对它们给予了很多关注。也许这就是这本书值得一读的原因。虽然也许可以说得更清楚一些））但是，我们有互联网，除了这本书之外，您还可以查看这个关于“那些第一次听说图表的人”的理论的播放列表。 ” 嗯，自然地，在本书的一开始，breadth-first-search就给出了广度优先搜索算法，也称为 BFS。书中包含以下图表：
private Map<String, String[]> getGraph() {
Map<String, String[]> map = new HashMap<>();
map.put("you", new String[]{"alice", "bob", "claire"});
map.put("bob", new String[]{"anuj", "peggy"});
map.put("alice", new String[]{"peggy"});
map.put("claire", new String[]{"thom", "jonny"});
map.put("annuj", null);
map.put("peggy", null);
map.put("thom", null);
map.put("johny", null);
return map;
}private String search() {
Map<String, String[]> graph = getGraph();
Set<String> searched = new HashSet<>();
Deque<String> searchQue = new ArrayDeque<>();
searchQue.add("you");
while (!searchQue.isEmpty()) {
String person = searchQue.pollFirst();
System.out.println(person);
if (personIsSeller(person)) {
return person;
} else {
String[] friends = graph.get(person);
if (friends == null) continue;
for (String friend : friends) {
if (friend != null && !searched.contains(friend)) {
searchQue.addLast(friend);
}
}
}
}
return null;
}图，Dijkstra 算法
或多或少了解了 BFS，本书作者邀请我们了解 Daysktra 算法和加权图。建议下图作为解决方案：
public Integer[][] getGraphMatrix(int size) {
Integer[][] matrix = new Integer[size][size];
matrix[0][1] = 6;
matrix[0][2] = 2;
matrix[2][1] = 3;
matrix[1][3] = 1;
matrix[2][3] = 5;
return matrix;
}@Test
public void dijkstra() {
Integer[][] graph = getGraphMatrix(); // Данные графа
Integer[] costs = new Integer[graph.length]; // Стоимость перехода
Integer[] parents = new Integer[graph.length]; // Родительский узел
BitSet visited = new BitSet(graph.length); // "Ферма" маркеров посещённости
Integer w = 0;
do {
System.out.println("-> Рассматриваем вершину: " + w);
Integer min = null;
for (int i = 0; i < graph.length; i++) { // Обрабатываем каждую дугу
if (graph[w][i] == null) continue; // Дуги нет - идём дальше
if (min == null || (!visited.get(i) && graph[w][min] > graph[w][i])) {
min = i;
}
if (costs[i] == null || costs[i] > costs[w] + graph[w][i]) {
System.out.print("Меням вес с " + costs[i]);
costs[i] = (costs[w] != null ? costs[w] : 0) + graph[w][i];
System.out.println(" на " + costs[i] + " для вершины " + i);
parents[i] = w;
}
}
System.out.println("Вершина с минимальным весом: " + min);
visited.set(w);
w = min;
} while (w != null);
System.out.println(Arrays.toString(costs));
printPath(parents, 3);
}
public void printPath(Integer[] parents, int target) {
Integer parent = target;
do {
System.out.print(parent + " <- ");
parent = parents[parent];
} while (parent != null);
}贪心算法
下一节专门讨论“贪婪算法”。本节很有趣，因为它使用了集合（java.util.Set）。最后我们可以明白为什么需要它。我们使用状态列表作为输入：Set<String> statesNeeded = new HashSet();
statesNeeded.addAll(Arrays.asList("mt", "wa", "or", "id", "nv", "ut", "ca", "az" ));Map<String, Set<String>> stations = new HashMap<>();
stations.put("kone", new HashSet(Arrays.asList("id", "nv", "ut")));
stations.put("ktwo", new HashSet(Arrays.asList("wa", "id", "mt")));
stations.put("kthree", new HashSet(Arrays.asList("or", "nv", "ca")));
stations.put("kfour", new HashSet(Arrays.asList("nv", "ut")));
stations.put("kfive", new HashSet(Arrays.asList("ca", "az")));Set<String> finalStations = new HashSet();
while (!statesNeeded.isEmpty()) {
String bestStation = null;
Set<String> statesCovered = new HashSet();
for (String station: stations.keySet()) {
Set covered = new HashSet(statesNeeded);
covered.retainAll(stations.get(station));
if (covered.size() > statesCovered.size()) {
bestStation = station;
statesCovered = covered;
}
}
statesNeeded.removeAll(statesCovered);
finalStations.add(bestStation);
}
System.out.println(finalStations);动态规划
本书还描述了应用“动态规划”方法的问题。任务给出：
List<Thing> things = new ArrayList<>();
things.add(new Thing("guitar", 1, 1500));
things.add(new Thing("tape recorder", 4, 3000));
things.add(new Thing("notebook", 3, 2000));int bagSize = 4;
int cell[][] = new int[things.size()][bagSize];
// Заполняем первую строку без условий
for (int i = 0; i < bagSize; i++) {
cell[0][i] = things.get(0).cost;
}
// Заполняем оставшиеся
for (int i = 1; i < cell.length; i++) {
for (int j = 0; j < cell[i].length; j++) {
// Если вещь не влезает - берём прошлый максимум
if (things.get(i).weight > j+1) {
cell[i][j] = cell[i - 1][j];
} else {
// Иначе текущая стоимость + предыдущий максимум оставшегося размера
cell[i][j] = things.get(i).cost;
if (j + 1 - things.get(i).weight > 0) {
cell[i][j] += cell[i-1][j + 1 - things.get(i).weight];
}
}
}
}
System.out.println(Arrays.deepToString(cell));搜索最近的邻居
书中还非常清楚地讲了k近邻算法：
GO TO FULL VERSION