排序算法(Sorting Algorithms)

（仍在进行中；我想用直观的解释和扑克牌例子重新审视）

排序是计算机科学理论的关键，但容易遗忘。我一时兴起想复习一下维基百科中的算法（奇怪，我知道），以下是我的笔记：

高级思考

有些算法（选择排序、冒泡排序、堆排序）通过一次将一个元素移动到最终位置来工作。你对一个大小为N的数组排序，将一个元素放置到位，然后继续对大小为N-1的数组排序（堆排序略有不同）。
有些算法（插入排序、快速排序、计数排序、基数排序）将元素放入一个临时位置，靠近（更接近）它们的最终位置。你重新扫描，每次迭代将元素移得更接近最终位置。
一种技术是从一个元素的“已排序列表”开始，然后一次一个地将未排序的元素合并进去。
复杂度和运行时间
- 因素：算法复杂度、启动成本、额外空间需求、递归的使用（函数调用开销大且占用栈空间）、最坏情况行为、对输入数据的假设、缓存，以及在已排序或接近排序数据上的行为
- 最坏情况行为对于需要保证性能的实时系统很重要。在安全方面，你希望保证来自攻击者的数据没有能力压垮你的机器。
- 缓存——具有顺序比较的算法利用了空间局部性和预取，这对缓存有利。
- 算法时间与实际时间——简单算法可能是O(N^2)，但开销低。对于小数据集（<10个元素）排序可能更快。一种折衷是根据输入大小使用不同的排序方法。
- “比较排序”对数据不做假设，并将所有元素相互比较（大多数排序）。O(N lg N)时间是理想的“最坏情况”场景（如果这说得通——O(N lg N)是在最坏情况下你能期望的最小代价）。堆排序具有这种行为。
- 如果我们对数据做出假设并且不需要比较元素（即，我们知道数据落在某个范围内或具有某种分布），O(N)时间是可能的。O(N)显然是最小的可能排序时间，因为我们必须至少检查每个元素一次（你怎么能排序一个你甚至没有检查过的元素？）。

注释

假设我们在排序一个包含N个元素的列表或数组
排序后，较小的项在左侧（第一个项），较大的项在右侧（最后一个项）

冒泡排序 [最佳：O(n)，最差：O(N^2)]

从左边开始，比较相邻元素，不断将较大的元素“冒泡”到右边（它已到达最终位置）。对剩余的N-1个元素重复冒泡排序。

虽然“简单”，但我发现冒泡排序并不简单。通常，那些需要反向迭代（递减某个索引）的排序对我来说是反直觉的。对于冒泡排序，要么你从左到右“向前”冒泡，并向后移动终点（递减），要么从右到左“向后”冒泡，并递增左端点。无论哪种方式，总有一个索引在递减。
你还需要跟踪倒数第二个端点，以免与不存在的项进行交换。

选择排序 [最佳/最差：O(N^2)]

扫描所有元素，找到最小的。将其交换到第一个位置。对剩余的N-1个元素重复选择排序。

我发现这是最直观且最容易实现的——总是向前迭代（i从0到N-1），并与最小的元素（始终是i）交换。

插入排序 [最佳：O(N)，最差：O(N^2)]

开始时，左边有一个已排序的元素列表，右边有N-1个未排序的元素。取出第一个未排序的元素（第2个元素），将其插入已排序列表，必要时移动元素。现在我们有一个大小为2的已排序列表和N-2个未排序元素。对所有元素重复此过程。

像冒泡排序一样，我觉得这个反直觉，因为你要“向后”移动
这有点像冒泡排序在移动项，只不过当你遇到一个比你小的项时，你会停止。如果数据是逆序排序的，每个项必须移动到列表头部，这就变成了冒泡排序。
有多种方式将项向左移动——你可以在每次迭代中交换，或者将每个项复制到它的邻居位置

快速排序 [最佳：O(N lg N)，平均：O(N lg N)，最差：O(N^2)]

快速排序有多种版本，因其速度（平均O(N lgN)，最坏O(N^2)）而成为最流行的排序方法之一。以下是几种版本：

使用外部内存：

选择一个“枢轴”项
将其他项划分到“小于枢轴”子列表或“大于枢轴”子列表中
枢轴放在两个列表之间
在子列表上重复快速排序，直到得到大小为1的子列表（已经排序）。
合并列表——整个列表将被排序

使用原地内存：

选择一个枢轴项并与最后一个项交换。我们希望像上面那样划分数据，需要先把枢轴移开。
从左到右扫描项，将大于枢轴的项与最后一个项交换（并递减“最后一个”计数器）。这会把“重”项放到列表末尾，有点像冒泡排序。
即使之前位于末尾的项大于枢轴，它也会在下次迭代中再次被交换。
继续扫描项，直到“最后一个项”计数器与正在检查的项重叠——这意味着所有超过“最后一个项”计数器的项都大于枢轴。
最后，将枢轴放到它正确的位置。我们知道“最后一个项”计数器处有一个大于枢轴的项，所以我们把枢轴交换到那里。
呼！现在，对左右子列表再次运行快速排序。我们知道枢轴已经在它的最终位置（左边的所有项都更小；右边的所有项都更大），所以可以忽略它。

使用带两个指针的原地内存：

选择一个枢轴并将其交换出去
从左到右，找到一个大于枢轴的异常项
从右向左走，找到一个小于基准的异常元素
如果找到就交换这两个元素，然后继续直到指针交叉——重新插入基准
对左右分区进行快速排序
注意：当需要跟踪指针位置以及基准在哪里交换时，这个算法会变得令人困惑

注释

如果选到了不好的基准，可以想象“较小”子集总是空的。这意味着我们每次只创建比前一个子集少一个元素的子集，最坏情况下时间复杂度为O(N^2)。
如果选择第一个元素，它可能是已排序列表中最小的元素，导致最坏情况。可以选择随机元素，或者三数取中（前、中、后）。
快速排序是快速因为它利用了空间局部性——它遍历相邻元素，将它们与基准值（可以保存在寄存器中）进行比较。它非常有效地利用了缓存。
基准通常被交换到前面，以便在枢轴操作期间不受干扰。之后，它被交换到正确的位置（与一个小于或等于它的基准项交换，从而保留了基准）。
快速排序算法很复杂，需要传递左右边界变量。

堆排序 [最佳/平均/最差：O(N lg N)]

将所有元素加入堆中。从堆中弹出最大元素，插入到末尾（最终位置）。对所有元素重复此过程。

堆排序就像选择排序，但有更好的方式来获取最大元素。它通过堆来获取最大值，而不是扫描所有元素。堆的性质使得堆排序可以原地工作，无需额外内存。
建堆的时间复杂度为O(N lg N)。弹出元素是O(1)，弹出后修复堆是O(lg N)。共有N次弹出，因此又有O(N lg N)的因子，整体为O(N lg N)。
堆排序在最坏情况下也是O(N lg N)，这使得它适用于实时应用。

计数排序 [最佳/平均/最差：O(N)]

假设数据是0-k范围内的整数。创建一个大小为K的数组，用于记录每个值出现的次数（例如，3个值为0的元素，4个值为1的元素等）。有了这个计数，你可以知道元素的位置——所有1必须排在0之后，而0有3个，因此1从第4个元素开始。这样，我们可以扫描元素并将它们插入到正确的位置。

创建计数数组是O(N)
将元素插入到正确位置是O(N)
这里我过度简化了——实际上需要计算累计计数，并从大到小排序以保持排序的稳定性。

基数排序 [最佳/平均/最差：O(N)]

获取一系列数字，每次按一位数字排序（例如，将所有千位数移动到两千位数之前等）。对每一组数字重复排序。

基数排序使用计数排序对各位数字（k=0...9）进行高效O(N)排序。
实际上，基数排序是从最低有效位（个位）到最高有效位，原因我会稍后解释（参见CLRS书）。
基数排序和计数排序很快，但需要结构化数据、外部内存，并且没有快速排序的缓存优势。

实际执行排序

为了练习，我根据伪代码用C语言实现了上述大部分排序。发现

即使是像冒泡排序这样的“简单”排序也会变得复杂，涉及递减、差一错误、> vs >=，因为你试图避免在交换时越界。
在纸上模拟问题至关重要，就像编写交换链表项的代码一样。不要把所有内容都记在脑子里。
我发现了所有初始排序中的错误并修复了它们。创建一个好的测试框架，使其简单易于测试。
- 我将排序例程分离到一个DLL中（我正在学习如何进行Windows编程——它与Unix有很大不同）。
- 我创建了一个简单的命令行.exe程序，它接收数字列表，将其转化为数组，并调用我的排序函数，打印结果。这种测试方式得到了Kernighan的鼓励——测试简单，不需要编译（例如硬编码一个“测试”程序）。
因为测试很容易，我创建了所有我能想到的测试用例：正序排序、反序排序、1个元素、2个元素、偶数个和奇数个项目等等。
为了调试，我在排序的每个阶段打印中间数组。