swift-algorithm-club-cn

by ksco

中文版:使用 Swift 语言实现的数据结构和算法,有详细的讲解!

229 Stars 50 Forks Last release: Not found MIT License 52 Commits 0 Releases

Available items

No Items, yet!

The developer of this repository has not created any items for sale yet. Need a bug fixed? Help with integration? A different license? Create a request here:

欢迎来到 Swift 算法俱乐部!

注:本文译自 Swift Algorithm Club

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

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

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

所有的代码都是兼容 Xcode 7.3 以及 Swift 2.2 的。如果 Swift 有更新,我们也会及时跟进。

这个项目目前正在进行中。更多的算法将被加入,敬请期待。:-)

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

重要链接

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

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

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

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

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

从哪开始?

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

算法列表

搜索算法

字符串搜索算法

  • *Brute-Force 算法-一个简单粗暴的方法。
  • *Boyer-Moore 算法-一种高效的字符串子串搜索算法。它不需要对被搜索的字符串中的字符进行逐一比较,而是根据一个查找表跳过其中的某些部分。
  • Rabin-Karp 算法
  • *最长公共子序列算法-找到两个字符串中的最长公共子序列。

排序算法

探究排序算法的工作原理是非常有趣的,但在实际的编码中,你几乎永远也不会需要自己编写排序算法,Swift 自带的

sort()
函数已经非常够用了,但如果你还是好奇背后的原理,请继续阅读。

基本的排序算法:

快速的排序算法:

特殊的排序算法

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

压缩算法

杂项

数学向算法

机器学习

  • *k-Means 聚类算法-无监督的分类器,将数据聚类为 K 个簇。
  • K-近邻算法
  • 线性回归
  • 逻辑回归
  • 神经网络
  • 网页排名算法

数据结构

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

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

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

绝大多数情况下,使用 Swift 内建的

Array
Dictinary
Set
就足够高效了,但某些时候,可能还是需要某些更合适的数据结构...

数组变体

  • *二维数组-固定尺寸的二维数组,可用于棋盘游戏。
  • *比特集n 位大小固定尺度的序列。
  • *固定长度数组-如果你确切的知道数据的大小,使用老式的固定长度的数组会更加高效。
  • *有序数组-一个永远有序的数组。

队列

列表

  • *链表-链接起来的数据序列。包含单向和双向链表。
  • 跳跃列表

  • *树-通用目的的树形结构。
  • *二叉树-一种节点最多有两个孩子节点的树形结构。
  • *二叉搜索树(BST)-以某种方式组织自己的节点的二叉树,以求较快的查询速度。
  • *AVL 树-一种通过旋转来维持平衡的二叉搜索树。 :construction:
  • 红黑树
  • 伸展树
  • 线索二叉树
  • *线段树-能够快速地对某区间进行计算。
  • k-d 树
  • *堆-存储在一维数组中的二叉树,所以它不需要使用指针。很适合做为优先队列使用。
  • 斐波那契堆
  • 字典树(Trie)
  • B 树
  • *基数树 :construction:

哈希

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

集合

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

智力题

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

学无止境!

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

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

其它关于算法的资源:

  • EKAlgorithms-非常棒的使用 Objective-C 编写的算法集合。
  • @lorentey-使用 Swift 实现的产品级质量的常用算法和数据结构实现。
  • Rosetta Code-提供了很多中语言的算法实现。
  • AlgorithmVisualizer-在浏览器中的图形化算法演示。

许可(License)

本项目(包括原项目)都是基于 MIT 协议的,请随意使用!

We use cookies. If you continue to browse the site, you agree to the use of cookies. For more information on our use of cookies please see our Privacy Policy.