swift-algorithm-club的翻译。使用Swift学习算法和数据结构。
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
3Sum and 4Sum upate Nov 13, 2018
AVL Tree update Sep 26, 2018
All-Pairs Shortest Paths
Array2D
B-Tree B树 Sep 27, 2018
Binary Search Tree 把翻译完的修改README.markdown,未翻译的是README_en.markdown Sep 16, 2018
Binary Search
Binary Tree 校对 二叉树 Oct 10, 2018
Bit Set
Bloom Filter
Bounded Priority Queue
Boyer-Moore-Horspool 把翻译完的修改README.markdown,未翻译的是README_en.markdown Sep 16, 2018
Breadth-First Search 广度优先搜索(BFS) Sep 18, 2018
Brute-Force String Search
Bubble Sort 校对 冒泡排序 Oct 1, 2018
Comb Sort
Combinatorics
Convex Hull upate Nov 13, 2018
Count Occurrences 校对 统计出现次数(Count Occurrences) Sep 23, 2018
Counting Sort 校对 计数排序(Counting Sort) Nov 6, 2018
Depth-First Search 深度优先搜索(DFS) Sep 20, 2018
Deque 双端队列 Sep 23, 2018
Dijkstra Algorithm update Nov 8, 2018
DiningPhilosophers upate Nov 13, 2018
Egg Drop Problem
Encode and Decode Tree upate Nov 13, 2018
Fixed Size Array 固定长度数组 和 有序数组 Oct 6, 2018
Fizz Buzz upate Nov 13, 2018
GCD Greatest Common Divisor Nov 4, 2018
Graph
Hash Set 哈希集合 Nov 8, 2018
Hash Table 校对 哈希表 Nov 10, 2018
HaversineDistance upate Nov 13, 2018
Heap Sort
Heap update Nov 8, 2018
Huffman Coding 哈夫曼编码 Sep 21, 2018
Images mix Aug 27, 2017
Insertion Sort
Introsort update Nov 8, 2018
K-Means
Karatsuba Multiplication
Knuth-Morris-Pratt 把翻译完的修改README.markdown,未翻译的是README_en.markdown Sep 16, 2018
Kth Largest Element
Linear Search
Linked List 校对 链表 Nov 8, 2018
Longest Common Subsequence
Merge Sort
Miller-Rabin Primality Test
Minimum Spanning Tree (Unweighted)
Minimum Spanning Tree 最小生成树 Nov 8, 2018
MinimumCoinChange upate Nov 13, 2018
Monty Hall Problem
Multiset
Naive Bayes Classifier upate Nov 13, 2018
Octree 八叉树 Oct 22, 2018
Ordered Array 固定长度数组 和 有序数组 Oct 6, 2018
Ordered Set
Palindromes upate Nov 13, 2018
Priority Queue 优先队列 Sep 24, 2018
QuadTree QuadTree Nov 4, 2018
Queue
Quicksort update Nov 8, 2018
Rabin-Karp 把翻译完的修改README.markdown,未翻译的是README_en.markdown Sep 16, 2018
Radix Sort update Nov 8, 2018
Red-Black Tree 红黑树 Sep 26, 2018
Ring Buffer
Rootish Array Stack update Oct 8, 2018
Run-Length Encoding
Segment Tree
Select Minimum Maximum
Selection Sampling
Selection Sort
Shell Sort
Shortest Path (Unweighted)
Shuffle
Shunting Yard Shunting Yard Nov 11, 2018
Single-Source Shortest Paths (Weighted)
Skip-List
Slow Sort
Sparse Table Sparse Table Oct 31, 2018
Splay Tree
Stack 把翻译完的修改README.markdown,未翻译的是README_en.markdown Sep 16, 2018
Strassen Matrix Multiplication
Threaded Binary Tree
Topological Sort
Tree update Sep 24, 2018
Trie
Two-Sum Problem
Union-Find 把翻译完的修改README.markdown,未翻译的是README_en.markdown Sep 16, 2018
Z-Algorithm Z-Algorithm Sep 17, 2018
.gitignore
Algorithm Design.markdown
Big-O Notation.markdown
README.markdown
Schedule.markdown
Under Construction.markdown 初始一些翻译 Aug 26, 2017
What are Algorithms.markdown 一些校对 Sep 14, 2018
Why Algorithms.markdown

README.markdown

注:本项目翻译自Swift Algorithm Club
欢迎有兴趣学习算法和数据结构,有时间的小伙伴一起参与翻译,欢迎issue,或者直接提交pull request。
说明和翻译进度


以下是原项目的README.markdown翻译部分(译注:表示还未翻译)

Swift算法俱乐部

欢迎来到Swift算法俱乐部!

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

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

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

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

😍 欢迎提供建议和贡献! 😍

重要链接

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

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

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

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

欢迎参与贡献 - 通过留下issue反馈,或者提交pull request。

从哪开始?

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

算法列表

搜索算法

字符串搜索算法

  • 暴力字符串搜索算法 一个简单粗暴的方法。
  • Boyer-Moore算法 一种高效的字符串子串搜索算法。它不需要对被搜索的字符串中的字符进行逐一比较,而是根据一个查找表跳过其中的某些部分。
  • Knuth-Morris-Pratt(KMP)算法 一种线性时间字符串算法,它获得字符串出现的已经给定模型字符串的索引。
  • [Rabin-Karp 算法] 使用哈希的快速搜索
  • 最长公共子序列算法 找到两个字符串中的最长公共子序列。
  • Z-Algorithm 在String中查找模式的所有实例,并返回模式在String中开始的索引。

排序算法

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

基本的排序算法:

快速的排序算法:

混合排序算法:

特殊的排序算法

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

压缩算法

杂项

数学算法

机器学习

数据结构

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

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

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

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

数组变体

队列

列表

  • 链表-链接起来的数据序列。包含单向和双向链表。
  • 跳跃列表 —— 跳过列表是一种概率数据结构,具有与AVL/或红黑树相同的对数时间限制和效率,并提供了有效支持搜索和更新操作的巧妙折衷。

  • -通用目的的树形结构。
  • 二叉树-一种节点最多有两个孩子节点的树形结构。
  • 二叉搜索树(BST)-以某种方式组织自己的节点的二叉树,以求较快的查询速度。
  • AVL树-一种通过旋转来维持平衡的二叉搜索树。 🚧
  • 红黑树. A self balancing binary search tree.
  • 伸展树. A self balancing binary search tree that enables fast retrieval of recently updated elements.
  • 线索二叉树. A binary tree that maintains a few extra variables for cheap and fast in-order traversals.
  • 线段树-能够快速地对某区间进行计算。
  • k-d 树
  • ST(稀疏表)算法. Another take on quickly computing a function over a portion of an array, but this time we'll make it even quicker!.
  • -存储在一维数组中的二叉树,所以它不需要使用指针。很适合做为优先队列使用。
  • 斐波那契堆
  • 字典树(Trie). A special type of tree used to store associative data structures.
  • B 树. A self-balancing search tree, in which nodes can have more than two children.
  • 四分树. A tree with 4 children.
  • 八叉树. A tree with 8 children.

哈希

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

集合

  • 布隆过滤器-一个常量内存数据结构,用于概率性的检测某个元素是否在集合中。
  • 哈希集合-使用哈希表实现的集合。
  • 多重集. A set where the number of times an element is added matters. (Also known as a bag.)
  • 有序集-很看重元素顺序的集合。

智力题

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

贡献者

Swift算法俱乐部最初是由Matthijs Hollemans 创建。

现在主要是Vincent NgoKelvin Lau 维护。

Swift算法俱乐部是来自raywenderlich.com社区的许多数算法成员的一起合作努力的成果。

许可(License)

所有内容均根据MIT开源许可条款获得许可。

通过在此发布或通过此论坛提交任何pull request,即表示您同意您提交或创建的所有内容(包括代码和文本)均受此许可证的约束。 Razeware,LLC和其他人将拥有许可中描述的有关此内容的所有权利。 可以在此处找到许可的准确条款。

Build Status