排序算法的比较

在这里，我们将根据几个因素比较各种排序算法。

• 时间复杂度
• 空间复杂性
• 稳定/不稳定
• 实际测试

时间复杂度比较

一个表格，其中显示了一些最常用的 Sorting Algorithms（排序算法）的时间复杂度。时间复杂度是比较两种排序算法时需要检查的第一件事。时间复杂度越低越好。

排序算法	平均大小写	最佳案例	最坏情况
冒泡排序	O（n2)	O（n）	O（n2)
插入排序	O（n2)	O（n）	O（n2)
选择排序	O（n2)	O（n2)	O（n2)
快速排序	O（n.log（n））	O（n.log（n））	O（n2)
归并排序	O（n.log（n））	O（n.log（n））	O（n.log（n））
堆排序	O（n.log（n））	O（n.log（n））	O（n.log（n））
计数排序	O（n+k）	O（n+k）	O（n+k）
基数排序	O（n*k）	O（n*k）	O（n*k）
存储桶排序	O（n+k）	O（n+k）	O（n2)

我们使用了上表中的配色方案来帮助我们比较排序算法。红色是最差的，O（n2）算法位于红色之下。接下来是O（n.log（n））算法，它们是中间地带。最佳时间复杂度为O（n），这是算法所能达到的最快速度。

空间复杂度比较

虽然速度很重要，而且通常是您的首要任务，但有时在内存受限的地方，最好使用内存成本低的算法。

下表显示了各种 Sorting Algorithms（排序算法）的 Space Complexity（空间复杂度）。您可能会注意到，空间复杂度较高的算法是那些 “不合适” 的算法，而那些 最低的算法是就地的。这当然是因为 Out of Place 算法会创建额外的数组来存储数据，而 In-place 使用相同的数组。

不言而喻，最好的空间复杂度是 O（1）。

排序算法	空间复杂性
冒泡排序	O（1）
插入排序	O（1）
选择排序	O（1）
快速排序	O（对数 （n））
归并排序	O（n）
堆排序	O（1）
计数排序	O（k）
基数排序	O（n + k）
存储桶排序	O（n）

稳定和不稳定的算法

这是一个相当小众的用途，并且仅在某些类型的数据中产生实际差异。但是，它仍然是这些特定场景所需的重要要求。

排序算法	稳定排序？
冒泡排序	是的
插入排序	是的
选择排序	不
快速排序	不
归并排序	是的
堆排序	不
计数排序	是的
基数排序	是的
存储桶排序	是的

排序算法 – 字段测试

最后，我们将测量主要组件 performance。我们已经在各种情况下测试了此处介绍的 9 种算法。从 100 个数字到 10,000 个数字以及使用已排序数据的测试，这些测试将揭示相当多的信息。

测试方法

我使用 Google Collab 来运行这些测试，以确保一个持续和公平的测试环境。需要明确的是，这些排序算法的代码是用 Python 编写的，并且以相当标准的方式编写。没有应用大量优化，只使用了 Algorithms 的标准（经典）版本。

Python timeit 和 random 库用于生成随机数据，并对每个算法执行连续和重复测试。这又是为了确保公平的结果。Random 库用于生成从 1 到 10,000 的数字，timeit 库每次测试总共执行 5 次，并返回所有 5 次的列表。我们显示了 5 个测试的最大值和最小值，因此你可以看到时间的位移。

这 5 个测试中的每一个实际上都运行了代码 10 次（number 参数，默认值 1,000,000）。这通过进行大量测试并将值相加以平均来提高准确性。如果需要一次排序的单个时间，请将最小值/最大值除以 10。重复次数由 repeat 参数（默认值 5）控制。

您可以在下面的代码中看到 testing 函数的代码。如果您点击 timeit 和 random 库的链接，您可以在此处了解有关发生的事情的更多信息。

import random
import timeit
import sys
 
def test():
  SETUP_CODE = '''
from __main__ import sort
from random import randint'''
   
  TEST_CODE = '''
array = []
for x in range(1000):
  array.append(x)
sort(array)
  '''
  times = timeit.repeat( setup = SETUP_CODE,
                          stmt = TEST_CODE,  
                          number = 10,
                          repeat = 5) 
 
  print('Min Time: {}'.format(min(times)))
  print('Max Time: {}'.format(max(times)))

排序算法 – 性能比较

我们将进行三组测试。第一个将有 100 个随机数，第二个将有 1000 个，第三个将有 10,000。仔细查看表格，比较时间复杂度，并做出自己的观察。在此之后，我将立即分享我的观察结果。

排序算法	测试 1 （100）	测试 2 （1000）	测试 3 （10000）
冒泡排序	最小值：0.01008 秒 最大值：0.0206 秒	最小值：1.0242 秒 最大值：1.0558 秒	最小值：100.922 秒 最大值：102.475 秒
插入排序	最小值：0.00306 秒 最大值：0.00650 秒	最小值：0.0369 秒 最大值：0.0562 秒	最小值：100.422 秒 最大值：102.344 秒
选择排序	最小值：0.00556 秒 最大值：0.00946 秒	最小值：0.4740 秒 最大值：0.4842 秒	最小值：40.831 秒 最大值：41.218 秒
快速排序	最小值：0.00482 秒 最大值：0.01141 秒	最小值：0.0370 秒 最大值：0.0383 秒	最小值：0.401 秒 最大值：0.420 秒
归并排序	最小值：0.00444 秒 最大值：0.00460 秒	最小值：0.0561 秒 最大值：0.0578 秒	最小值：0.707 秒 最大值：0.726 秒
堆排序	最小值：0.00489 秒 最大值：0.00510 秒	最小值：0.0704 秒 最大值：0.0747 秒	最小值：0.928 秒 最大值：0.949 秒
计数排序	最小值：0.01929 秒 最大值：0.02052 秒	最小值：0.0354 秒 最大值：0.0400 秒	最小值：0.195 秒 最大值：0.203 秒
基数排序	最小值：0.00315 秒 最大值：0.00394 秒	最小值：0.0294 秒 最大值：0.0309 秒	最小值：0.313 秒 最大值：0.338 秒
存储桶排序	最小值：0.00225 秒 最大值：0.00241 秒	最小值：0.0335 秒 最大值：0.0369 秒	最小值：1.854 秒 最大值：1.892 秒

本想进行 100,000 和 1,000,000 个数字的测试，但 O（n²） 算法需要很长时间才能完成，所以放弃了。

观察

1. The O(n²） 算法（冒泡和插入排序）的反应非常糟糕，因为测试数量增加到 10,000 次。在 10,000 个数字时，其他算法的平均速度提高了 100 倍以上。
2. 在只有 100 个数字的测试用例上，O（n²） 算法比 O（n.log（n）） 算法更快。
3. 数字数量每增加 10 倍，O（n²） 算法完成时间增加了 100 倍。
4. 平均而言，Radix Sort 和 Counting Sort 是最快的算法。
5. Heapsort 是最快的算法，空间复杂度为 O（1）

排序数据比较

另一个非常有趣的情况是使用 Sorted Data 而不是 random 数据。此测试主要是为了显示哪些 Sorting Algorithms 对已排序/部分排序的数据执行，哪些性能更差。

排序算法	已排序数据 （1000）
冒泡排序	最小值：0.542 秒 最大值：0.556 秒
插入排序	最小值：0.790 秒 最大值：0.821 秒
选择排序	最小值：0.434 秒 最大值：0.464 秒
快速排序	最小值：0.812 秒 最大值：0.872 秒
归并排序	最小值：0.0289 秒 最大值：0.0364 秒
堆排序	最小值：0.0604 秒 最大值：0.0661 秒
计数排序	最小值：0.0055 秒 最大值：0.0124 秒
基数排序	最小值：0.0119 秒 最大值：0.0145 秒
存储桶排序	最小值：0.0183 秒 最大值：0.0247 秒

观察

1. 惊喜，惊喜。快速排序算法名副其实，对于上述 1000 个排序数字，它是上述所有算法中最慢的。这是因为 Quick Sort 对此类退化情况的响应不佳，并且需要特殊优化，例如 “randomized pivots”。
2. 除 Quick Sort 外，所有 Algorithms（算法）所需的时间均减少。
3. Counting Sort 性能最佳，其次是 Radix 和 Bucket Sort。