最简单的排序算法示例 - 为什么有人会使用它？

啊，排序算法……

这是一个如此简单的问题，却又如此难以快速完成……让我换一种说法，这是一个如此简单的问题，但要快速处理大量需要排序的东西却非常困难。这个问题的解决方案有简单的，也有复杂的，但你将要学习的是所有排序算法中最简单的，冒泡排序。

冒泡排序算法一直是讨论中一个有趣（有时是痛苦）的话题。有些人刚接触编程、算法和数据结构，根本不知道什么是冒泡排序；有些人则认为冒泡排序是“计算机编程界的耻辱，在任何情况下都不应该使用，上帝保佑！”……然后是介于两者之间的大多数人。无论你属于光谱的哪个区域，我都欢迎你来我这里简要讨论这种迷人且迷人地简单的排序方法。

所以，对于新入门的你，冒泡排序是什么？冒泡排序是一种最古老、最简单的排序算法，用于对给定的一组信息进行排序。在这个算法中，你比较数组中相邻的两个值，如果第二个值小于第一个值，你就交换这两个值的位置。本质上，小值会“冒泡”进入数组的顶部/前面，而大值会“沉入”底部。你还记得三年级/四年级科学课上，老师把不同粘度的液体放进一个容器里摇晃吗？冒泡排序就像那样工作。较轻的值/液体会浮到顶部，而较重的值/液体会沉到底部。这种比较和交换值的过程将继续在冒泡排序算法中进行，直到你得到一个排序好的列表。

听起来不错，对吧？嗯，难怪有一群人比讨厌 Windows ME 更讨厌它。冒泡排序是性能最差的排序算法，遥遥领先。我不会详细介绍时间复杂度，但万一你在团队问答中遇到这个问题，冒泡排序的时间复杂度是 O(n^2)。这很糟糕。当你回想冒泡排序的做法时，正如前面所讨论的，很容易看出为什么这不是排序列表的最佳方法。但不要完全抛弃冒泡排序，这个算法确实有一些很好的用途，但首先，让我们看看这个例子程序。

瞧，就是这样。八行优美的代码。如果你是编程新手，这可能看起来很陌生，所以我给你简单介绍一下。`arrayToSort` 数组非常直观，而 `temporaryInt` 变量是我们用于在需要时存储将要交换的一个值的变量。外部 `for` 循环跟踪程序已经循环了多少次数据。在此冒泡排序实现中，我们循环数据的次数将始终等于我们要排序的数组的长度减一（给定这些迭代次数，我们知道数组将被排序……为什么？嗯，就信我吧）。内部 `for` 循环是我们遍历要排序的数组的地方，从索引 0（数组中的第一个值）开始，一直到倒数第二个值。这个循环一直到倒数第二个值，因为如果它一直到最后一个值，那么当我们比较最后一个值和下一个值时……嗯，没有下一个值，对吧？对。这就是我们这样做的原因。在内部 `for` 循环中，是冒泡排序所有实际工作完成的地方。`if` 语句表示，如果索引 `i` 处的值小于索引 `i + 1` 处的值，我们就交换它们。这就是 `temporaryInt` 变量发挥作用的地方，很容易看出为什么它需要。在程序当前的设置中，没有输出，但如果有，它看起来会是这样的：

多么好看的列表！那么，这不禁让人提出疑问，除了在你的第一个本科数据结构或算法课上，你什么时候会使用它？这种排序算法的优点在于它简单、简短，并且易于实现。我可以闭着眼睛在十秒钟内编写一个冒泡排序程序。我广泛使用冒泡排序的一个场景是在测试大型程序的各个部分时。与其花大量时间让一个更复杂的排序算法与我的数据一起工作，我快速编写冒泡排序，然后继续处理程序中更重要的部分。这使我能够更快地构建原型并测试代码片段。当我让程序工作起来时，我再回去将其更改为更快的排序算法。由于给定排序算法的输出是相同的（如果它工作正常），所以它一开始是否快速确实无关紧要。就像俗话说，“罗马不是一天建成的”，从小处着手，牺牲效率，在你的程序工作起来后，再用更有效的排序算法进行优化，可能会非常有益。相信我，这可以为你省去很多麻烦，尤其是在处理大型项目时。

除此之外，冒泡排序在你知道你将始终需要排序的元素数量很少，或者你知道元素总是几乎排好序的情况下也可能很有用。在这种情况下，更快的排序算法可能仍然更快，但鉴于这些信息，实现它们是毫无意义的。它要么不值得程序空间，不值得程序员的时间，要么你根本注意不到时间差异。想想看……如果你离商店只有几个街区远，你会买一辆法拉利来缩短你的行程吗？不会，你不会（普通人不会）。即使你的本田思域比法拉利慢得多，这也不值得投资……而且说实话，你也不会真正注意到时间上的差异。

简单的事情可能有很多美妙之处，冒泡排序也不例外。我编程多年，仍然发现很多情况冒泡排序都可以派上用场。尽管它不是最有效的排序算法，但了解它并知道如何应用它仍然很重要。

如果你读到这里，谢谢你。这是我的第一篇文章，也是未来的许多文章之一。主题包括算法、机器学习、计算机视觉等。我感谢所有反馈，并且我总是喜欢与新朋友进行愉快的交谈。