C++ 串排序算法

Strand Sort 简介

Strand Sort 是一种相对简单但高效的排序算法，属于基于比较的排序算法。它最早由 Anne R. Cool 于 **1985** 年提出。Strand Sort 的工作原理是从未排序的列表中反复提取已排序的子列表，并将它们与结果合并，直到原始列表为空。该算法不需要额外的 **内存分配** 来存储临时数组或列表，因此具有空间效率。

Strand Sort 首先获取一个未排序的元素列表。然后它 **遍历** 这个列表，沿途形成已排序的子列表（strand）。这个过程包括反复从 **未排序列表** 中取元素，如果它们大于子列表中的最后一个元素，就将它们 **追加** 到一个临时子列表中。子列表形成后，将其与结果合并。

Strand Sort 基本上是一次构建一个已排序列表（一个 strand）。它利用了这样一个性质：如果一个元素大于一个 strand 的最后一个元素，就可以将它添加到该 strand 中 **而不会违反** 排序顺序。这个过程一直持续到没有更多元素可以添加到该 strand 中为止，此时它将被合并到结果列表中。然后，算法会用剩余的 **未排序元素** 重复此过程，直到所有元素都排序完成。

虽然 Strand Sort 的时间复杂度为 O(n^2)，但它在小型到 **中等大小的列表** 上表现相对较好，并且由于使用了链表来存储临时子列表，因此具有 **空间效率** 的优点。

方法一：链表方法

实现 Strand Sort 的链表方法利用了 **链表** 的灵活性和动态性来高效地排序元素列表。在这种方法中，原始未排序列表和 **临时子列表**（strands）都用链表表示。

链表方法提供了一种直接且高效的方式来实现 **Strand Sort 算法**。它利用链表的强大功能来创建和操作子列表，从而实现了一种既有空间效率又易于实现的排序算法。

链表方法的优点

动态内存分配：链表允许动态内存分配，可以 **高效地** 添加或删除元素，而无需预先分配或调整大小。这种动态性使得 **链表适合** 数据结构大小可能经常改变的情况，就像 Strand Sort 中形成和合并子列表一样。

高效的插入和删除：链表提供高效的插入和删除操作，通常以常数时间完成。这种 **效率** 对于 Strand Sort 的子列表形成和合并步骤至关重要，因为在排序过程中需要从子列表中添加或删除元素。 **与数组不同**，在数组中插入或删除元素可能需要移动其他元素，而链表只需调整指针，从而实现更快的操作。

无需额外的内存分配：Strand Sort 的链表方法利用了链表中已分配的内存，无需为临时 **数组或列表** 进行额外的 **内存分配**。这使得该算法在内存使用上非常高效，尤其适用于 **大型数据集**，因为它最小化了内存开销。

易于实现：链表为实现 Strand Sort 提供了一种直观的方式，因为它们自然支持子列表的形成和合并操作。 **链表** 的动态性简化了添加和删除元素的过程，降低了 **实现** 的复杂性。此外，链表中指针的易于操作促进了子列表的有序合并。

程序

输出

Original array: 12 11 13 5 6 
Sorted array: 5 6 11 12 13

说明

• 函数定义

strandSort：此函数实现了 Strand Sort 算法。它接受一个整数列表的引用（输入）作为参数，并返回一个包含已排序元素的 **新列表**。

printList：此函数负责将列表的内容打印到控制台。它接受一个整数列表（lst）的 **常量引用** 作为参数，并遍历其元素，在每个元素后打印一个空格。

• 主函数

在 main 函数内部，初始化了一个示例未排序列表（arr），其中包含整数值 {12, 11, 13, 5, 6}。使用 printList 函数打印 **原始未排序列表** 以显示其内容。

• Strand Sort 算法

strandSort 函数开始时初始化一个名为 sorted 的空列表，该列表将保存已排序的元素。使用一个 while 循环进行迭代，直到 **原始输入** 列表（input）变为空。此循环一直运行，直到输入列表中的所有元素都已排序并移至 sorted 列表。

在循环内部，创建一个 **临时子列表**（sublist）来存储构成 strand 的元素。将输入列表的第一个元素推入此子列表，然后将其从输入列表中删除。

算法然后使用迭代器 **遍历** 输入列表中剩余的元素。对于每个元素，如果它大于当前子列表的最后一个元素，则将其添加到子列表中，并从输入列表中删除该元素。此过程一直持续到没有更多元素可以添加到 **当前子列表** 为止。

形成 **子列表** 后，将其与 sorted 列表合并。如果 sorted 列表为空，则直接将子列表插入其中。否则，将子列表中的每个元素与 **sorted 列表** 中的每个元素进行比较，并将它们按排序顺序插入。循环继续，直到输入列表中的所有元素都已排序并移至 sorted 列表。

• 打印排序后的列表

最后，使用 printList 函数打印 **排序后的列表（sortedArr）** 以显示排序后的元素。

最终，此实现 **有效地** 使用 C++ 中的链表演示了 Strand Sort 算法。它形成临时子列表，将它们与结果列表合并，并重复此过程直到所有元素都排序完成。使用函数进行排序和打印可以提高代码的 **模块化和可读性**。

复杂度分析

时间复杂度分析

形成子列表

在 **最坏情况下**，输入列表的每个元素都正好被访问一次以形成一个子列表。此操作需要遍历 *input list*，其时间复杂度为 *O(n)*，其中 n 是输入列表中元素的数量。

将子列表与结果合并

将子列表与结果列表合并涉及将子列表的每个元素与结果列表的每个元素进行比较，直到所有元素都 **合并**。在最坏情况下，如果两个列表分别有 m 和 n 个元素，则此操作的时间复杂度为 **O(m * n)**，其中 m 是子列表的大小，n 是 **结果列表** 的大小。

由于我们反复将子列表合并到结果列表中，直到所有元素都排序完成，因此合并所有子列表的总时间复杂度是所有单独合并的时间复杂度的总和。在最坏情况下，这是 **O(n^2)**，其中 n 是输入列表中的总元素数。

使用链表的 Strand Sort 算法的总体时间复杂度为 **O(n^2)**，其中 n 是输入列表中的总元素数。此时间复杂度源于与结果列表 **反复合并子列表**。

空间复杂度分析

输入列表和临时子列表

存储输入列表和临时子列表的空间复杂度为 **O(n)**，其中 n 是输入列表中的总元素数。输入列表的每个元素仅存储一次，每个子列表由输入列表的 **元素** 形成。

结果列表

存储结果列表的空间复杂度也为 **O(n)**，其中 n 是 **输入列表** 中的总元素数。结果列表包含所有按 **升序** 排序的元素。使用链表的 Strand Sort 算法的总空间复杂度为 **O(n)**，其中 n 是输入列表中的总元素数。

此空间复杂度源于存储输入列表、临时子列表和结果列表。

方法二：基于数组的方法

实现 **Strand Sort** 的基于数组的方法涉及使用数组而不是链表来表示原始未排序列表和临时子列表（strands）。此方法旨在 **提高性能**，尤其是在具有高效数组处理功能的语言中。通过利用数组，我们可以获得直接访问元素的优势，并可能降低与链表相比的内存开销。但是，实现此方法需要更 **复杂的数组** 操作，包括在需要时调整数组大小、合并子数组以及管理索引来跟踪元素。

基于数组方法的优点

高效访问：数组提供对元素的直接访问，允许高效的随机访问操作。这意味着按索引 **访问元素** 比链表更快，链表需要遍历。

潜在的性能提升：在数组处理高效的语言中，例如 C++ 或 Python，基于数组的方法可能提供 **更好的性能**，因为开销减少且 **访问速度更快**。这对于链表的开销可能很显著的大型数据集尤其有利。

内存效率：与链表相比，数组可能需要更少的内存开销，尤其是在大型数据集的情况下。这是因为数组只存储数据元素本身，而链表还需要 **额外的内存** 来存储连接元素的指针。

挑战与注意事项

调整大小的开销：**动态调整数组大小** 可能会带来开销，尤其是在频繁调整大小时。调整大小需要分配一个更大、更新的数组，将元素从旧数组复制到新数组，然后释放旧数组。这可能会影响性能，尤其是在频繁插入或删除的情况下。

复杂性：**数组操作**，如调整大小和合并，可能比链表更复杂。管理索引和内存分配需要仔细注意，以避免错误和低效率。此外，合并子数组以排序顺序涉及比链表遍历更复杂的逻辑。因此，实现 **复杂性可能会增加**，需要彻底的测试和调试。

程序

输出

Original array: 12 11 13 5 6 
Sorted array: 5 6 11 12 13 

说明

函数定义

strandSort：此函数实现了 Strand Sort 算法。它接受一个整数向量（输入）的引用作为参数，并返回一个包含已排序元素的 **新向量**。

printVector：此函数负责将向量的内容打印到控制台。它接受一个整数向量（vec）的 **常量引用** 作为参数，并遍历其元素，在每个元素 **后面** 打印一个空格。

• Strand Sort 算法

strandSort 函数开始时初始化一个名为 sorted 的空向量，该向量将保存已排序的元素。使用一个 while 循环进行迭代，直到原始输入向量（input） **变为空**。此循环一直运行，直到输入向量中的所有元素都已排序并移至 sorted 向量。

• 主函数

在 main 函数内部，初始化了一个示例未排序向量（arr），其中包含整数值 {12, 11, 13, 5, 6}。使用 printVector 函数打印原始未排序向量以显示其内容。

在循环内部，创建一个临时子列表（sublist）来存储构成 strand 的元素。将输入向量的第一个元素推入此子列表，然后将其从输入向量中删除。

算法然后使用 for 循环 **遍历** 输入向量的 **剩余元素**。对于每个元素，如果它大于当前子列表的最后一个元素，则将其添加到子列表中，并从输入向量中删除该元素。此过程一直持续到没有更多元素可以添加到当前子列表为止。

形成 **子列表** 后，将其与 **sorted 向量** 合并。如果 sorted 向量为空，则直接将其赋值给它。否则，将子列表和 sorted 向量的每个元素进行比较，并将它们按排序顺序合并到一个名为 merged 的新向量中。最后，sorted 被赋值为 merged 的 **值**。

循环继续，直到 **输入向量** 中的所有元素都已排序并移至 sorted 向量。

• 打印排序后的向量

最后，使用 printVector 函数打印 **排序后的向量**（sortedArr）以显示排序后的元素。此实现有效地使用 C++ 中的数组演示了 Strand Sort 算法。它形成 **临时子列表**，将它们与结果向量合并，并重复此过程直到所有元素都排序完成。

复杂度分析

时间复杂度分析

形成子列表

在最坏情况下，输入向量的每个元素都正好被访问一次以形成一个子列表。此操作需要遍历 **输入向量**，其时间复杂度为 **O(n)**，其中 n 是输入向量中的元素数量。

将子列表与结果合并

将子列表与结果向量合并涉及将子列表的每个元素与结果向量的每个元素进行比较，直到所有元素都合并。在最坏情况下，如果两个向量分别有 m 和 n 个元素，则此操作的时间复杂度为 **O(m * n)**，其中 m 是 **子列表的大小**，n 是结果向量的大小。

由于我们反复 **合并子列表** 到结果向量中，直到所有元素都排序完成，因此合并所有子列表的总时间复杂度是所有单个合并的时间复杂度的总和。在最坏情况下，这是 **O(n^2)**，其中 n 是输入向量中的总元素数。

总体时间复杂度

使用数组的 Strand Sort 算法的总体时间复杂度 **为 O(n^2)**，其中 n 是输入向量中的总元素数。此时间复杂度源于与 **结果向量** 反复合并子列表。

空间复杂度分析

输入向量和临时子列表

存储输入向量和临时子列表的空间复杂度为 **O(n)**，其中 n 是 **输入向量** 中的总元素数。输入向量的每个元素仅存储一次，每个子列表由输入向量的元素形成。

结果向量

存储结果向量的空间复杂度也为 **O(n)**，其中 n 是输入向量中的总元素数。结果向量包含所有按 **升序** 排序的元素。

总空间复杂度

使用数组的 Strand Sort 算法的总空间复杂度为 **O(n)**，其中 n 是输入向量中的总元素数。此空间复杂度源于存储输入向量、临时子列表和结果向量。

结论

使用数组的 Strand Sort 算法由于反复合并子列表而表现出 O(n^2) 的 **时间复杂度**。

空间复杂度为 O(n)，其中 n 是输入向量中的总元素数，因为它需要存储输入向量、**临时子列表** 和结果向量的空间。

尽管 Strand Sort 简单且 **空间效率高**，但由于其二次时间复杂度，它可能不是大型数据集最高效的排序算法。但是，它适用于小型到中型数组，或者在空间效率是优先考虑的情况下。