共计 2752 个字符，预计需要花费 7 分钟才能阅读完成。
作者 | George Dvorsky
编译 | 深度学习这件小事
1 排序算法
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。
稳定的
- 冒泡排序（bubble sort）— O(n^2）
- 鸡尾酒排序 (Cocktail sort，双向的冒泡排序) — O(n^2）
- 插入排序（insertion sort）— O(n^2)
- 桶排序（bucket sort）— O(n); 需要 O(k) 额外空间
- 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外空间
- 合并排序（merge sort）— O(nlog n); 需要 O(n) 额外空间
- 原地合并排序— O(n^2)
- 二叉排序树排序（Binary tree sort）— O(nlog n) 期望时间；O(n^2) 最坏时间；需要 O(n) 额外空间
- 鸽巢排序 (Pigeonhole sort)— O(n+k); 需要 O(k) 额外空间
- 基数排序（radix sort）— O(n·k); 需要 O(n) 额外空间
- Gnome 排序— O(n^2)
- 图书馆排序— O(nlog n) withhigh probability，需要（1+ε)n 额外空间
不稳定的
- 选择排序（selection sort）— O(n^2)
- 希尔排序（shell sort）— O(nlog n) 如果使用最佳的现在版本
- 组合排序— O(nlog n)
- 堆排序（heapsort）— O(nlog n)
- 平滑排序— O(nlog n)
- 快速排序（quicksort）— O(nlog n) 期望时间，O(n^2) 最坏情况；对于大的、乱数列表一般相信是最快的已知排序
- Introsort—O(nlog n)
- Patience sorting— O(nlog n+k) 最坏情况时间，需要额外的 O(n+ k) 空间，也需要找到最长的递增子串行（longest increasing subsequence）
不实用的
- Bogo 排序— O(n× n!) 期望时间，无穷的最坏情况。
- Stupid sort— O(n^3); 递归版本需要 O(n^2) 额外存储器
- 珠排序（Bead sort）— O(n) or O（√n)，但需要特别的硬件
- Pancake sorting— O(n)，但需要特别的硬件
- stooge sort——O（n^2.7）很漂亮但是很耗时
2 傅立叶变换与快速傅立叶变换
傅立叶是一位法国数学家和物理学家，原名是 JeanBaptiste Joseph Fourier(1768-1830), Fourier 于 1807 年在法国科学学会上发表了一篇论文，论文里描述运用正弦曲线来描述温度分布，论文里有个在当时具有争议性的决断：任何连续周期信号都可以由一组适当的正弦曲线组合而成。当时审查这个论文拉格朗日坚决反对此论文的发表，而后在近 50 年的时间里，拉格朗日坚持认为傅立叶的方法无法表示带有棱角的信号，如在方波中出现非连续变化斜率。直到拉格朗日死后 15 年这个论文才被发表出来。谁是对的呢？拉格朗日是对的：正弦曲线无法组合成一个带有棱角的信号。但是，我们可以用正弦曲线来非常逼近地表示它，逼近到两种表示方法不存在能量差别，基于此，傅立叶是对的。为什么我们要用正弦曲线来代替原来的曲线呢？如我们也还可以用方波或三角波来代替呀，分解信号的方法是无穷多的，但分解信号的目的是为了更加简单地处理原来的信号。用正余弦来表示原信号会更加简单，因为正余弦拥有原信号所不具有的性质：正弦曲线保真度。一个正余弦曲线信号输入后，输出的仍是正余弦曲线，只有幅度和相位可能发生变化，但是频率和波的形状仍是一样的。且只有正余弦曲线才拥有这样的性质，正因如此我们才不用方波或三角波来表示。
3 Dijkstra 算法
Dijkstra 算法是典型的算法。Dijkstra 算法是很有代表性的算法。Dijkstra 一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用 OPEN, CLOSE 表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。
4 RSA 算法变换
RSA 是目前最有影响力的公钥加密算法，它能够抵抗到目前为止已知的绝大多数密码攻击，已被 ISO 推荐为公钥数据加密标准。今天只有短的 RSA 钥匙才可能被强力方式解破。到 2008 年为止，世界上还没有任何可靠的攻击 RSA 算法的方式。只要其钥匙的长度足够长，用 RSA 加密的信息实际上是不能被解破的。但在分布式计算和量子计算机理论日趋成熟的今天，RSA 加密安全性受到了挑战。
5 安全哈希算法
一种对输入信息（例如消息）进行摘要的算法。摘要过程能够完成下列特点：不同的输入信息绝对不会具有相同的指纹：相近输入信息经过摘要之后的输出信息具有较大的差异，同时计算上很难生产一个与给定输入具有相同指纹的输入。（即不可逆）。
6 整数因式分解
这是在计算机领域被大量使用的数学算法，没有这个算法，信息加密会更不安全。该算法定义了一系列步骤，得到将一合数分解为更小因子的质数分解式。这被认为是一种 FNP 问题，它是 NP 分类问题的延伸，极其难以解决。许多加密协议（如 RSA 算法）都基于这样一个原理：对大的合数作因式分解是非常困难的。如果一个算法能够快速地对任意整数进行因式分解，RSA 的公钥加密体系就会失去其安全性。量子计算的诞生使我们能够更容易地解决这类问题，同时它也打开了一个全新的领域，使得我们能够利用量子世界中的特性来保证系统安全。
7 链接分析
链接分析，源于对 Web 结构中超链接的多维分析。当前其应用主要体现在网络信息检索、网络计量学、数据挖掘、Web 结构建模等方山。作为 Google 的核心技术之一，链接分析算法应用已经显现出 j 惊人的商业价值。
8 比例积分微分算法
你是否曾经用过飞机、汽车、卫星服务或手机网络？你是否曾经在工厂工作或是看见过机器人？如果回答是肯定的，那么你应该已经见识过这个算法了。大体上，这个算法使用一种控制回路反馈机制，将期望输出信号和实际输出信号之间的错误最小化。无论何处，只要你需要进行信号处理，或者你需要一套电子系统，用来自动化控制机械、液压或热力系统，这个算法都会有用武之地。可以这样说，如果没有这个算法，现代文明将不复存在。
9 数据压缩算法
在现今的电子信息技术领域，正发生着一场有长远影响的数字化革命。由于数字化的多媒体信息尤其是数字视频、音频信号的数据量特别庞大，如果不对其进行有效的压缩就难以得到实际的应用。因此，数据压缩技术已成为当今数字通信、广播、存储和多媒体娱乐中的一项关键的共性技术。
10 随机数生成
在统计学的不同技术中需要使用随机数，比如在从统计总体中抽取有代表性的样本的时候，或者在将实验动物分配到不同的试验组的过程中，或者在进行蒙特卡罗模拟法计算的时候等等。
