每种排序算法的适用范围

任何在计算机科学学校学习过或学习过排序算法的人都应该清楚，如今最受认可的算法是快速排序，因为它的平均O(n log n)运行时间很短。一些效率低得多的算法，例如插入排序，其平均运行O(n * n)时间可能不太理想。然而，在许多极端情况下，每种算法都可能比其他算法更出色。

快速排序

快速排序是一种基于Go-to算法的排序算法，其效率取决于两个因素：其主元（或分区元素）和源数组的熵。如果数组部分或基本已排序，并且/或者主元的选择方式使其更接近数组的首尾，则其效率很容易降低到O(n * n)。

插入排序

虽然插入排序看起来很慢，但在处理小规模数据时却非常高效。它的O(n * n)平方运行时间可以提升到相当可观的O(n * k)，其中k是它需要遍历数组来交换前一个元素和当前元素的步骤。此外，如果数组部分或已经基本排序，插入排序会比快速排序更加出色，后者在这种情况下表现会相当糟糕。之所以k很少提到 ，是因为它不需要经常遍历数组。

选择排序

这是一个非常简单的算法，具有相当整洁的O(1)常数空间复杂度。虽然它的运行时间是二次方的，但它有一个神奇的特性：在数组上运行 N 次后，会保留前 N 个已排序的元素。这意味着什么？这意味着，如果你要对已排序的数据（例如搜索结果）进行分页和排序，你只需要运行选择排序算法的那么多次。当你需要下一组结果时，你可以从上次中断的地方继续执行，依此类推。