在这里，你能找到各种知名算法和数据结构的 Swift 版本实现（对，就是那个深受大家喜爱的编程语言），并附带了详细的说明来解释它们是如何运作的。
如果你是一名需要这类知识来应付考试的计算机科学系学生，或者你是一名想要夯实理论基础的自学型程序员，那你就算来对地方了！
这个项目的目标是 解释算法的实现原理。关注点在于让代码更加清晰易读，而不是实现一个可以直接用在你自己项目里的依赖库。也就是说，虽然这里的大多数代码都是可以在实际场景中使用的，但是在你粘贴过去之后千万要注意检查它们是不是真的合适。
这里的代码基于 Xcode 10 和 Swift 4.2 编写。
欢迎留下你的建议或参与共建！
什么是算法和数据结构？ 看菜谱做菜！
为什么要学习算法？ 如果你在犹豫这些内容是否适合自己，来看看这个。
算法复杂度的标记方法。我们经常说“这个算法的复杂度是O(n)”。如果你不太清楚这是什么意思，看看这个。
算法设计的技巧。如何创造一个新的算法？
欢迎参与共建。你可以通过创建 issue 或 Pull Request 的方式给这个项目提供帮助。
如果你刚刚入门算法和数据结构，可以先从下面几个知识点开始了解：
- 线性查找。在一个数组里查找某个元素。
- 二分查找。在一个有序数组中快速查找元素。
- 计算出现次数。计算某个值在数组中出现的次数。
- 查找最小值/最大值。计算数组中的最小值/最大值。
- 第 k 大的元素。查找数组中第k大的元素，比如中位数。
- 选择抽样。在集合中随机选取一批元素。
- 查找集合。跟踪集合间不重复的元素，以便能快速合并多个集合。
- 穷举法。一种简单直白的方法。
- 摩尔字符串搜索。一种快速搜索子串的方法。它借助一张查询表来跳过某些字符，从而避免对每个字符都进行处理。
- KMP 算法。一种有着线性时间复杂度的算法，可以返回给定规律的子串的出现下标。
- Rabin-Karp 算法。一种基于哈希的更快的查询方法。
- 最长相同子串。在不同字符串中，找寻最长的相同部分。
- Z 算法。在字符串中找到所有具有特定排列模式的子串，并返回这些子串的起始位置下标。
了解排序算法的实现是很有意思的，但在实际使用过程中你很少需要自己写排序流程。Swift 提供的 sort() 方法已经完全可以胜任这个工作了。但是如果你对实现感到好奇，那么请继续往下看...
基础排序：
快速排序：
动态排序：
出于特殊目的的排序：
不太好的排序算法（别用！）：
- “洗牌”（Shuffle）。随机打乱一个数组。
- 梳排序。冒泡排序的优化版。
- 凸包。
- 米勒-拉宾素性检验。这个数字是素数吗？
- 最少硬币兑换。动态编程的一个示例。
- 遗传算法。参考生物进化理论实现的一个数值最佳化的简单例子。 A simple example on how to slowly mutate a value to its ideal form, in the context of biological evolution.
- Myers 差分算法。找寻两个序列中的最长相同子序列。
- 最大公约数（GCD）。附加奖励：最小公倍数。
- 排列组合。组合数学启动！
- 调度场算法。将中缀表达式转换为后缀表达式的经典算法。
- 卡拉楚巴算法。另一种快速乘法算法。
- 半正矢公式。计算圆上两点距离的方式。
- 施特拉森矩阵乘法。一种高效的矩阵乘法算法。
- 逆时针算法。计算简单多边形的面积。
- k 平均算法。把点划分到 k 个聚类中的算法。
- k 邻近算法
- 线性回归。对一个（或多个）变量之间关系进行建模的一种回归分析。
- 逻辑回归
- 神经网络
- 网页排名算法
- 朴素贝叶斯分类器
- 模拟退火。一种在很大搜寻空间中寻找近似最优解的通用概率算法。
为特定任务挑选合适的数据结构取决于下面几件事情。
第一，数据组成形式选择与你使用它们的方式相关。如果你想通过关键字去查找对象，那么你需要一个字典（dictionary）；如果你的数据可以被组成上下级，那么你大概会用到某种树型结构；如果你的数据是有序的，那么也许栈或队列更适合你。
第二，考虑最频繁的使用方式是什么，因为某些数据结构是针对特定动作进行过优化的。比方说，如果你经常要在某个集合里找到最重要的某个元素，那么堆或者优先队列会比一个普通的数组性能更好。
大多数时候，使用内置的 Array、Dictonary 和 Set 已经足够了，但有些时候你可能想要用一些更酷炫的方式...
- 二维数组。一种维度固定的二维数组。棋牌类游戏中常常会用到。
- 比特位集合。 一种保存了 n 个比特位的定长序列。
- 定长数组。当你提前知道要存储的数据长度时，用复古的固定长度的数组也许会更加高效。
- 有序数组。一种一直保持某种顺序的数组。
- Rootish Array Stack。一种时间和空间上都更高效的 Swift 数组变体。
- 树。一种常规概念上的树型结构。
- 二叉树。一种每个节点最多只能有两个子节点的树。
- 二叉搜索树（BST）。一种经过特殊排序的二叉树，能用于更快速的查询。
- 红黑树。一种自平衡的二叉搜索树。
- AVL 树。一种自平衡的二叉搜索树。
- 伸展树。一种自平衡的二叉搜索树，能快速找回最近更新的元素。
- 线索二叉树。一种维护了少量额外变量的二叉树，能在节点间进行快速的有序移动。
- 线段树。可以快速查询结构内包含某一点的所有区间。
- kd 树
- 稀疏表。与线段树的功效相同，但这次会更快！
- 堆。一种以数组形式保存的二叉树，所以它不需要用到指针。是一种很好的优先队列。
- 斐波那契堆
- 前缀树。一种用于保存关联数据结构的特殊的树。
- B 树。一种自平衡搜索树，每个节点可以拥有2个以上的子节点。
- 四叉树。每个节点正好有4个子节点的树。
- 八叉树。每个节点正好有8个子节点的树。
- 哈希表。让你能够用关键字来存取对象。字典通常就是基于哈希表实现的。
- 散列函数
- 图
- 广度优先搜索（BFS）
- 深度优先搜索（DFS）
- 最短路径，在非平衡树上实现。
- 单源最短路径
- 最小生成树，在非平衡树上实现。
- 最小生成树
- 任意两点之间的最短路径
- 迪杰斯特拉算法
- A*算法
许多软件开发岗位的面试都有做算法题的环节。这里列举了一小部分有趣的题目。想找更多算法题（或答案）可以来这里和这里。
- Two-Sum Problem
- Three-Sum/Four-Sum Problem
- Fizz Buzz
- Monty Hall Problem
- Finding Palindromes
- Dining Philosophers
- Egg Drop Problem
- Encoding and Decoding Binary Tree
- Closest Pair
对上面的内容还满意吗？那就来看看 Data Structures & Algorithms in Swift，这是 Swift 算法俱乐部团队官方出版的书籍。
你会从基础的数据结构开始，例如链表、队列、栈，学习如何用 Swift 的语法形式来实现它们。接着会学习各种类型的树结构，包括一些具有特定目标的树，比如二叉树、AVL 树、二叉搜索树和前缀树。
你还能看到一些比冒泡排序和插入排序性能更好的算法，比如归并排序、基数排序、堆排序和快速排序。你还可以学习到：如何构造有向、无向和加权图，用以表示现实世界中的模型；使用广度优先、深度优先、迪杰斯特拉和普林姆算法来高效地遍历图或树，用以解决类似最短路径或最低成本网络的问题。
读完这本书，你就拥有了使用数据结构和算法解决常见问题的实操经验，而且你还拥有了创造属于自己的高效算法的能力。
你可以在 raywenderlich.com 商城里找到这本书。
Swift 算法俱乐部最初由 Matthijs Hollemans 创建。
现在由 Vincent Ngo、 Kelvin Lau 和 Richard Ash 共同维护。
Swift 算法俱乐部是 raywenderlich.com 社区中的众多算法同好们一起努力的成果。期待你的参与——加入俱乐部？:]
本翻译页面由 David Lee 创建与维护。
All content is licensed under the terms of the MIT open source license.
By posting here, or by submitting any pull request through this forum, you agree that all content you submit or create, both code and text, is subject to this license. Razeware, LLC, and others will have all the rights described in the license regarding this content. The precise terms of this license may be found here.