swift-algorithm-club-cn

Swift 数据结构与算法学院!翻译自https://github.com/raywenderlich/swift-algorithm-club

View project on GitHub

Swift Algorithm Club

欢迎来到 Swift 算法俱乐部!

注:本文译自 Swift Algorithm Club

注:由于早先swift-algorithm-club-cn 翻译不全且已经停止维护,本项目是在此基础上的进行的翻译和更新,感谢 ksco 及其小伙伴的先前付出

想体验更好的点这里

在这里,你可以找到很多流行的算法和数据结构的具体实现,使用的是大家最喜欢的新语言 Swift,并对他们的工作原理配有详细的解释。

如果你是一个计算机学院的学生,为了考试想学习一下算法;又或者你是一个自学成才的程序员,想提高一下自身的理论姿势水平--你真 TM 来对地方了!

这个项目的目的是解释各种算法的工作方式。所以我们主要关注代码的清晰性和可读性,而不是为了产出一个可复用的库,让读者可以直接拖进自己的工程使用。换句话说,绝大多数的代码都是可以用于实际的项目中的,不过需要你根据自己的项目需求进行一些修整。

所有的代码都是兼容 Xcode 10 以及 Swift 4.2 的。如果 Swift 有更新,我们也会及时跟进。 这个项目目前正在进行中。更多的算法将被加入,敬请期待。:-)

:heart_eyes:欢迎提供建议和贡献!:heart_eyes:

重要链接

什么是算法和数据结构?-做薄饼!

为什么要学习算法?-还在担心这不是你的菜吗?请读一下这篇文章。

大 O 表示法-我们经常会听到这样的话:“这个算法是 O(n) 的”。如果你不知道这是啥意思,请读读这篇文章。

*算法设计技巧-怎样设计自己的算法?

欢迎参与翻译!-如果有意参与翻译,请阅读注意事项!

从哪开始?

如果你之前没有接触过算法和数据结构,你可以从下面这些简单易懂的算法开始看起:

算法列表

搜索算法

字符串搜索算法

  • Brute-Force 算法-一个简单粗暴的方法。
  • Boyer-Moore 算法-一种高效的字符串子串搜索算法(BM算法)。它不需要对被搜索的字符串中的字符进行逐一比较,而是根据一个查找表跳过其中的某些部分。
  • Knuth-Morris-Pratt 算法 - 一个线性复杂度字符串搜索算法(KMP算法),通过模式字符进行匹配返回所有的字符串的位置
  • Rabin-Karp 算法 - 通过哈希算法快速搜索
  • 最长公共子序列算法-找到两个字符串中的最长公共子序列。
  • Z-Algorithm 在一个字符串中找到所有的模式字符,并返回模式字符在字符串中的开始位置

排序算法

探究排序算法的工作原理是非常有趣的,但在实际的编码中,你几乎永远也不会需要自己编写排序算法,Swift 自带的 sort() 函数已经非常够用了,但如果你还是好奇背后的原理,请继续阅读。

基本的排序算法:

快速的排序算法:

混合排序:

特殊的排序算法

不好的排序算法(知道就行了,不要用!):

压缩算法

杂项

机器学习

数据结构

对于特定的任务,数据结构的选择需要基于以下几点考量。

首先,你的数据是具有某种形态的,并且有一些必要的操作方法。如果你想基于关键字来查找对象,需要的是字典类型的数据结构;如果你的数据原生就是分层级的,就需要某种类型的树形结构;而如果你的数据是线性的,则你需要的是数据结构可能就是栈或队列等。

其次,具体的选择还与你在实际使用中最常用的操作方法有关,因为不同的数据结构都对不同的操作方法做了优化。举例来说,如果你经常需要获取集合中的某些较为重要的元素,那么使用堆或优先队列就比普通的数组要好很多。

绝大多数情况下,使用 Swift 内建的 ArrayDictinarySet 就足够高效了,但某些时候,可能还是需要某些更合适的数据结构…

数组变体

队列

  • -后进先出!
  • 队列-先进先出!
  • *双端队列
  • *优先队列-一个保持最重要的元素总是在最前面的队列。
  • *环形缓冲区-一个语义上的固定大小的环形缓冲区,实际使用的是一维序列头尾相接实现。

列表

  • *链表-链接起来的数据序列。包含单向和双向链表。
  • *跳跃表- 跳跃表是一种随机化的数据结构与AVL/红黑树有着相同的时间复杂度O(logN),并且更新和搜索更加高效简单。

  • *树-通用目的的树形结构。
  • *二叉树-一种节点最多有两个孩子节点的树形结构。
  • 二叉搜索树(BST)-以某种方式组织自己的节点的二叉树,以求较快的查询速度。
  • *红黑树 - 自平衡二叉搜索树
  • *AVL 树-一种通过旋转来维持平衡的二叉搜索树。
  • *伸展树- 自平衡二叉搜索树允许快速检索最近更新的节点
  • *线索二叉树 - 一种二叉搜索树通过额外的数据加快遍历并降低消耗
  • *线段树-能够快速地对某区间进行计算。
  • k-d 树
  • 稀疏表 又一个可以对数组部分做计算的数据结构,但是这次可以更快!
  • *堆-存储在一维数组中的二叉树,所以它不需要使用指针。很适合做为优先队列使用。
  • 斐波那契堆
  • *字典树 - 一种特殊类型的树结构用来保存关联数据的结构
  • *B 树 - 自平衡搜索树,每个节点可以超过两个子节点
  • *基数树是将指针与long整数键值相关联的机制,它存储有效率,并且可快速查询
  • *四叉树
  • *八叉树

哈希

  • *哈希表-允许你通过一个关键词来存取数据。字典通常都是基于哈希表实现的。
  • 哈希函数

集合

  • *布隆过滤器-一个常量内存数据结构,用于概率性的检测某个元素是否在集合中。
  • *哈希集合-使用哈希表实现的集合。
  • *多重集 - 可以重复添加元素的集合
  • *有序集-很看重元素顺序的集合。

智力题

很多程序员在面试时都会被问到一些算法性质的智力题。这里只囊括了一点比较有趣的。想了解更多的智力题(及答案),请浏览这里,还有这里

Raywenderlich 书籍推荐

喜欢本系列?可以购买 Swift 算法学院出品的 Data Structures & Algorithms in Swift

Data Structures & Algorithms in Swift Book

你可以从像链表,队列,栈这些基本的数据机构开始,学习如何用 Swift 语言的方式实现他们。然后进阶实现各种类型的树,以及各种特定用途的树如二叉树, AVL 树,二分查找树和字典树等。

学习比冒泡,插入排序更好的算法,如归并排序、基数排序、堆排序和快速排序。学习构建有向图和无向图以及带权重的图来表示现世界中的模型,用广度优先算法、深度优先算法、Dijkstra Prim 算法高效的遍历图和树,在网络中找出最短路径和使用最低代价。

在书的最后,用数据结构和算法实战解决一些通用问题,这样你就踏上自己开发高效算法的历程啦!

放个链接在此,raywenderlich.com store.

学无止境!

请参阅以下书籍获取更多内容:

下面的书籍均可在网上免费阅读:

其它关于算法的资源:

声明

Swift算法俱乐部最初是由 Matthijs Hollemans 创建的。 现在由 Vincent Ngo, Kelvin LauRichard Ash 进行维护.

Swift算法俱乐部由 算法贡献者raywenderlich.com社区大力支持。 我们一直在寻找联盟者,为什么不加入呢?:]

许可(License)

本项目(包括原项目)都是基于 MIT 协议的

我们所有提交的 pull request 都是通过这个平台,所有代码和文章因此都是遵循该许可的。 根据该许可,Razeware, LLC 和其他人都对相关的文档保留权利。你可以这里找到许可文档。

所有中文文档的翻译来自Swift 算法学院,因此也将遵循原项目协议