迹忆客 专注技术分享

本文将解释哪种排序算法在什么条件下表现最好。 条件包括数据结构的类型、排序数据的大小、数据排列和数据元素的范围。

我们先解释一下排序算法； 然后，我们将解释各种算法在不同数据结构下的性能。

C++ 中最快的排序算法

排序算法是一种对存储在任何数据结构中的元素进行排列的方法。

任何排序算法的适用性取决于输入数据大小、数据结构类型、数据排列、时间和空间复杂性以及数据范围。

有些排序算法在数组数据结构上表现更好，而有些则在堆上表现更好。 此外，如果记录的最重要的整数键远小于记录的数量（例如，计数排序），某些算法会很快。

那么，哪一种算法是最快的呢？ 尽管答案看起来很简单，但请查看复杂度表并选择时间复杂度最低的一个（即渐近增长）。

然而，实际上，在没有看到底层数据的结构属性的情况下，我们不能直接说算法 A 在给定数据上比算法 B 表现更好，反之亦然。

因此，我们将尝试通过讨论排序算法及其在给定底层数据结构的不同场景中的特殊适用性来找到答案。

数据结构 - 链表

链表是一种在节点中存储数据的线性数据结构。 节点是链接列表的基本构建块，其中包含数据和指向下一个节点的指针。

对链接列表进行排序的最佳排序算法是合并排序。 合并排序在链表上比在数组上表现更好，因为不需要辅助数组来存储合并操作的输出。

与数组不同，链表节点不必在内存中连续。 相反，节点可以分散在不同的内存位置。

此外，与数组相比，我们可以在 O(1) 额外空间和 O(1) 时间内将一个值放在链表的中心。

因此，在对链表进行排序的同时，不需要额外的渐近增长空间来实现归并排序的合并操作。 因此，归并排序会对(nlog n)中的链表进行排序。

数据结构 - 数组

数组是将数据存储到连续内存位置的线性数据结构。 数组中的数据类型必须相同。

以下是各种排序算法及其适用性的列表。

• 当数组接近排序时可以选择插入排序，因为在数组的已排序区域添加新项目时它很少移动任何项目。

  对已排序数组进行插入排序的时间复杂度为 O(n)，但对同一数组进行快速排序的时间复杂度为 O(n^2)。 您可以在这里找到更多信息。

   

• 由于快速排序是就地排序，因此它适用于数组。 此外，快速排序算法在排序过程中不需要额外的空间。

• 在合并排序的情况下，必须获取和释放额外的空间。 因此，归并排序算法的执行时间将会增加。

  平均而言，合并和快速排序的时间复杂度为 O(nlogn)，但合并排序需要额外的 O(n) 空间。 这里的n是要排序的数组的大小。 您可以在这里找到更多相关信息。

   

• 当我们想要按字典顺序对数组中存储的数据（例如整数、单词和固定大小字符的字符串）进行排序时，我们会使用基数排序。使用并行机时执行基数排序。

• 当记录的最大整数键远小于记录数时，使用计数排序。

• 当存储在数组中的数据在一定范围内公平分布时，桶排序是最有效的。

数据结构-树

树是一种在节点中存储数据的非线性数据结构。 最顶层的节点称为根节点。 根节点进一步附加到子节点。

树的类型有很多种，但这里我们只讨论二叉搜索树（BST）。

树排序被认为是 BST 的最佳排序算法。 此外，BST 的中序遍历为我们提供了按排序顺序排列的元素。 同样，堆排序最适合对存储在堆中的元素进行排序。

请记住，我们还可以分析其他类型数据结构（例如哈希表、红黑树等）上的所有排序算法。

以下部分提供了一个备忘单，描述了各种排序算法的复杂性和稳定性。

算法复杂性备忘单

在查看该表之前，我们先讨论一下与排序算法相关的常见术语。

稳定排序

如果在密钥之间存在平局的情况下，算法保持密钥的原始顺序，则该算法是稳定的。 例如，假设 S 序列具有以下对：

S = <(1,"Alex"), (3,"Bill"),(2,"Ananth"), (1, "Jack")>

现在，假设我们要按整数键对上述序列进行排序。 那么，稳定的排序算法会将上述序列排序为：

Stably Sorted S = <(1,"Alex"),(1, "Jack"),(2,"Ananth"),(3,"Bill")>

看，稳定排序保留了 (1, “Alex”) 和 (1, “Jack”) 对的原始顺序。 然而，不稳定的排序并不能保证这一点。

原地排序

如果排序占用固定量的辅助内存，则排序为就地排序。 这意味着额外的内存需求不会随着问题规模的增加而增加。

例如，下面备忘单中空间复杂度为 O(1) 的所有排序都是就地的。

在对基本排序术语有足够的背景知识后，让我们看一下排序算法的复杂度表。 该表可以帮助我们决定在特定问题上下文中选择最合适的排序算法。