2010年6月8日（最后更新：2010年6月8日）

排序算法

评分：3.3/5（66 票）
*****
引言
 在常见的编程中，你通常不会发现自己需要直接进行排序。用户通常会希望按照给定的顺序获取信息，这是有原因的。但是，如果用户希望以某种特定的顺序进行排序，你该怎么做呢？

假设你有 1 美元、5 美元、10 美元、20 美元和 50 美元的钞票，顺序是 50 - 10 - 20 - 1 - 5。作为人类，我们可以很容易地将这些钱按从小到大或从大到小的顺序排列。但我们理所当然地认为这种常见做法的实际操作。

当我们尝试通过机器代码来实现一个时，我们会遇到代数方程、递归函数，以及我们从未见过的数字。我们不能像用我们的大脑那样简单地按顺序排列，即使这看起来很容易。但是，我们可以模拟我们如何整理我们的美元钞票。

例如，拿出美元钞票并尝试对它们进行排序。默认情况下，并且按照你的本性，你的大脑应该已经告诉你遵循某种模式。我的大脑告诉我最高的数字是 50 和 1，然后将它们放在各自的位置。然后我寻找相等或更低的值，并将其放在下面，然后继续迭代寻找更多相同值或更低的值，直到我找到最低的。然后我尝试迭代，寻找第二个最低的，然后是下一个最高的，依此类推，直到它被整理好。

在这方面实现它很容易，但说实话，它通常不是很有效。我们的大脑选择了一条简单的路线，因为它有能力在毫秒内计算出来，我们通常无法区分。如果我们的大脑选择了一种太难的模式来整理钞票，它会选择另一种更简单的路径，或者会以不同的方式继续按照相同的模式进行。但是，你永远不会通过数字排序来更改算法，并且你始终在尝试找到最优化和最快的编码方法。这就是算法文章存在的原因。它不仅展示了不同的算法，还展示了它背后的数学原理以及在哪里应用它们。


术语和概念
 你可能需要知道的一些术语和概念，我不会亲自解释，因为我不是真正教概念的人，而是更多地在我自己的小世界中理解它。相反，我将为你提供在哪里寻找对概念和术语的理解的方向，从大 O 符号开始。

大 O 符号只是用数学方法来表达函数完成所需的时间：http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/
你需要理解的另一个概念是算法复杂度，这是对算法难度的判断，通常衡量算法的空间和时间。维基百科上有一个更好的信息来源：http://en.wikipedia.org/wiki/Computational_complexity_theory#Machine_models_and_complexity_measures
我个人和诚实地说，我并不了解所有关于它的知识，只足以理解复杂性的衡量标准。另一篇值得一看的文章是：http://www.progressive-coding.com/tutorial.php?id=1
另一个要理解的概念是算法稳定性，它是算法保持排序数组中相同值的元素相对位置的能力。例如，你有两张 5 美元的钞票，它们需要被排序，一张上面有一个复选标记，另一张没有。在一个稳定的算法中，在前面的那个仍然会在排序后在前面。这被认为是拥有一个稳定的算法。在大多数情况下，它不是必需的，但是在你有一个附加到你想要排序的值数组的第二个值的情况下，必须理解算法稳定性以及它如何影响你。

最后但并非最不重要的是算法适应性。这是算法接受一个已经部分排序的数组，并能够从它离开的地方继续，并且比它没有预先排序的情况下更快完成的能力。这通常是一个很大的问题，因为它可以成倍地节省你的时间。

一旦你理解了这些术语和概念的基础知识，你就可以跟随和比较不同的算法，并理解为什么我选择一种算法而不是另一种。


比较排序算法
 现在最常用的算法类型称为比较排序，它是一个通用的算法类别。它所指的就是算法将一个元素与另一个元素进行比较，并根据该比较的结果做出反应以对数组进行排序。

一种常见的比较排序是冒泡排序，它是比较排序的一个子类，称为交换排序，它包括交换相邻的项直到排序完成

http://codepad.org/YeU6tmzB 稍微优化版本：http://codepad.org/YCJpEFMN
它通常效率低下，仅用于简单的教育目的。该算法的平均复杂度为 O(n^2)，这意味着它在较大的列表上非常糟糕。在数组已经排序的情况下，最佳情况下的复杂度为 O(n)。但是，它易于实现、稳定且具有适应性。

比这种排序更进一步的是插入排序，它本身就是一种类型和排序，并且有很多变体。它比冒泡排序效率更高，尽管复杂度通常为 O(n^2)，就像我们谈到的效率低下的冒泡排序一样。它比冒泡排序有很多优势，但其中大部分不足以在更大的列表上常用。它也更复杂一些。

http://codepad.org/UUZqOqC9
bbl，得早点起床。
它没有完成，但感谢你的直率 Bazzy。至少你给出了理由，不像有些人。

1) 我将描述它们的复杂性，可能还有大 O 符号......我遗漏了很多东西。
2) 我没有评论，因为我没找到在哪里评论。如果你能为我评论，那就太好了。
3) 我解释了它们是灵活的，并且可以与其他类型一起使用，这就是我使用模板来给出一个示例的原因。
4) 我使用了 codepad，这样我就可以给出带有结果的完整工作程序，而不使用我的措辞限制。

bbl，必须跑了。