C++ 中的愚蠢排序算法

Stooge sort 是一种递归算法，它利用分治的原理。然而，它不像快速排序或归并排序那样常用。Stooge sort 的实现很简单，使其成为演示递归排序方法的一个有趣技术。它是由 Steve Abbott 于 1975 年提出的。之所以命名为 Stooge sort，是因为它看起来效率很低。

该方法通过反复将数组划分为更小的子数组进行排序，这通过递归完成，然后合并结果数组。采用的思路是通过检查两个给定元素的相对位置来匹配它们，并在它们失序时交换它们。通过这种方式，Stooge sort 首先将前三分之二和后三分之二的元素进行排序，然后继续排序过程，将其划分为前三分之二。通过这个过程，元素将被放置在适当的顺序。

Stooge sort 的大 O 复杂度为 O(n^(log3 / log1.5)) ≈ O(n^2.7095)，这意味着时间复杂度约为 O(n^2.7095)。在效率方面，其时间复杂度为 O(n^2)，并且被证明比快速排序或归并排序（分别为 O(n log n) 和 O(n^2)）效率低。

Stooge sort 的另一个特点是其效率低下，因为它试图处理大型数据集。由于该算法是递归的，因此它必须按照特定顺序比较元素，对于包含许多整数元素的数组，这样的程序会变得缓慢。此外，静态排序不具有稳定性。由于这个原因，同一数组中元素的顺序可能会被打乱。

尽管 Stooge sort 有些效率低下，但由于其递归性质和独特的排序方法，它仍然很有趣。尽管它可能不是用于生产环境中排序大量数据的最佳选择，但由于其简单性，它仍然是排序算法列表中的一个不错的补充。

方法一：使用 vectors。

在 C++ 中使用 std::vector 容器实现 Stooge Sort 可以帮助您健壮地实现排序。在此方法中，我们利用 C++ STL 库中的 std::vector 容器的动态数组功能。std::vector 动态调整大小，并能提供快速索引；因此，普通的向量排序是高效的。

程序

输出

Original vector: 5 8 2 6 1 9 3 7 4 
Sorted vector: 1 2 3 4 5 6 7 8 9

说明

头文件和命名空间

代码包含 <iostream> 和 <vector> 头文件，以启用输入输出操作并利用 std::vector 容器。std 命名空间是使用标准库函数和类的一种方式。

Swap 函数

该函数通过接收两个整数作为引用变量来交换它们。在排序过程中，当元素被移入和移出向量时，它充当元素的占位符。

Stooge Sort 函数

StoogeSort 函数实现了 StoogeSort 算法。它接受三个参数：将要排序的 arr，以及指向将要排序的元素范围的 low 和 high。基本情况描述了 low>= high 成立时，这意味着子向量不包含单个元素以上，或者元素已按升序排列。然后，该函数确定子向量的第一个和最后一个元素是否已按相反的顺序排列，并在必要时交换它们。

当子向量大小大于 2 时，该函数计算一个变量 t，该变量占子向量大小的三分之一。该过程会反复调用自身，通过将子向量划分为前三分之二和后三分之二，然后分别对这两个子向量进行排序，从而将这些最大的元素放置到它们应该在的位置。

最后，它对子向量的前三分之二进行快速排序，以细化排序顺序。

Print Vector 函数

printVector 函数接收一个指向向量的 const& 数组，并打印向量中的每个元素。

主函数

在 main 函数中，将使用一些值初始化一个向量 arr。原始向量将通过 printVector 函数打印。将执行 stoogesSort 函数以使用Stooge Sort 方法对向量进行排序。最后，将使用 printVector 函数打印排序后的向量。

复杂度分析

时间复杂度

Stooge Sort 的时间复杂度高于 Quicksort 或 Mergesort，它们的时间性能更好，但以牺牲排序速度为代价。Stooge Sort 的时间复杂度为 O(n(log 3) / (log 1.5))，大约为O(n^2.7095)。这意味着随着元素数量的增加，Stooge Sort 处理 n 大小的数组所需的时间将不断增加。因此，对于具有速度问题的大型数据集的数组，Stooge Sort 的可行性较低。

空间复杂度

Stooge Sort 算法的空间复杂度在执行原地排序时为O(1)。这是因为它直接在输入数组上操作，并且不涉及任何其他结构。但它取决于堆栈是否为了其递归函数调用或其他需求而消耗空间，那么空间复杂度可能会增加。总的来说，Stooge Sort 相对于其时间复杂度具有较低的空间复杂度，这导致了一个内存高效但耗时的过程。

方法二：使用链表。

程序

输出

Original linked list: 5 3 7 1 9 
Sorted linked list: 1 3 5 7 9

说明

节点结构

SinglyLinkedListstruct 由一个 Node 结构组成，这是一个单向链表中的节点。它包含一个整数数据来保存节点的值或属性，以及一个 next 指针，该指针指向链表中的下一个元素。当调用构造函数时，它使用给定值调用函数成员，并将"next 指针 = nullptr"，这是列表的最后一个节点。

Merge 函数

combine 函数将两个已排序的链表合并成一个有序的链表。在合并过程中，使用名为 l1 和 l2 的合并列表指针指向它们的头部。如果任一列表的输入指针确实为 nullptr，则函数返回另一个列表（因为它已按排序顺序排列）。

该函数通过重复合并其余部分并保持列表顺序不变来比较头部节点的数据组件。

链表的 Stooge Sort 函数

stoogeSortLinkedList() 函数接受一个列表参数，并使用 Stooge Sort 算法对其进行排序。它通过将列表拆分为多个子列表，对它们进行排序，然后合并来实现。

实现的技巧是使用慢指针和快指针来查找中点。它通过典型地将列表分成两半，然后由 stoogeSortLinkedList 函数进一步排序来实现。在连接两个数组后，division merger 函数使用合并操作合并数组，以获得最终的排序数组。

Print 函数

printLinkedList 代表链表上的此操作，它将头部作为起点，沿直线移动直到末尾，并沿途打印每个节点的数据。它在列表排序之前和之后进行检查。

主函数

在 main 函数中，创建了一个初始包含一些成员的链表引用。使用 'printLinkedList' 函数打印原始链表。相同的函数 stoogeSortLinkedList 使用 Stooge Sort 算法对链表进行排序。现在再次调用printLinkedList 函数来打印排序后的链表。

复杂度分析

时间复杂度

链表的 Stooge Sort

对于在链表上操作的 Stooge Sort 算法，需要考虑的复杂度是递归的深度和合并函数的复杂度。在最坏情况下，列表会被递归地分成其一半，直到达到单个节点。因此，递归的搜索深度为O(log n)，其中 n 是链表中节点的数量。

此外，每次请求合并时，它最坏情况下的复杂度为线性 O(n)，如果 n 表示正在合并的节点总数。因此，对于链表，Stooge Sort 的总复杂度最终为O(n log n)，其中 n 是链表中的节点数。

Merge 函数

merge 函数处理两个已排序的链表，其中 m 和 n 分别是正在合并的两个列表的大小，m 和 n 分别是列表的长度。该函数仅遍历两个列表一次，执行比较操作，最终合并列表，因此实现的时间复杂度为O (m + n)。然而，正在合并的列表的长度不是恒定的，因此 merge 函数可能根据输入长度产生可变的时间复杂度。

空间复杂度

该代码程序的空间复杂度主要取决于存储链表地理元素的内存以及递归函数调用所需的内存。链表为O(n)，与 n 相同，其中 n 是列表中节点的数量。

此外，在 stoogeSortLinkedList() 函数中，递归调用会占用与递归深度成比例的堆栈空间（在最坏情况下为 O(log n)）。

因此，上述总空间复杂度为O(n + log n) 类型，其中 n 是链表中节点的数量，log n 是 stoogeSortLinkedList 函数的递归深度。

方法三：递归函数与交换

“带交换的递归函数”意味着 Swap Sort 算法是通过递归函数实现的，该函数负责排序的数组元素以及在必要时进行重新排列的交换操作。

程序

输出

Original array: 5 8 2 6 1 3 7 4 
Sorted array: 1 2 3 4 5 6 7 8

说明

头文件和命名空间

该程序链接了 <iostream> 头文件，使得输入输出操作成为可能，并且 std 命名空间也用于标准库特性操作。

Swap 函数

swap 函数包含两个 int 地址作为输入，它们将分别被交换。这种操作类型通过其值交换数组的元素，以保持其排序，同时将其按升序或降序排列。

Stooge Sort 函数

stoogeSort 函数实现了 Stooge Sort 算法——一种专门用于处理大型数据集的排序算法。它接受三个参数：一个指向 arr 的指针，以及 low 和 high 作为元素范围的参数。基本情况值描述为 low>= high，这些是零个或一个元素的子数组，它们已经排序。

一种根据数字的自然排列顺序对数字数组进行排序的方法称为快速排序，它基于选择枢轴元素（称为分区方法）的机制，然后检查子数组的第一个和最后一个元素是否被交换，如果被交换，则执行交换。

当子数组的长度大于 2 时，我们创建一个变量 t，该变量占子数组长度的三分之一。

该过程重复进行，因为函数一遍又一遍地调用自身，分别对子数组的前三分之二和后三分之二进行排序，直到最大的元素被移动到其逻辑位置。最重要的是，它会再次对子数组的前三分之二进行排序，以获得排序顺序的更精细细节。

Print Array 函数

printArray 函数以数组 arr[] 及其长度作为参数。其目的是显示属于数组的所有项。

主函数

在 main 函数内部，将一个 int 数组 arr[] 填充了几个值。数组大小 n 通过将 sizeof 运算符与单个元素的大小除以数组中的总元素数量相乘而获得。使用printArray 函数，将原始数组的所有数字打印在屏幕上。

调用 stoogeSort 函数，以便通过 Stooge Sorting 对数组进行排序。接下来，它使用 printArray 函数显示最终数组。

复杂度分析

时间复杂度

这是因为 Stooge Sort 主要受到排序过程中进行的比较和交换次数的影响。在每次stoogesort 方法调用中，算法会进行两次比较，以查看子集的第一和最后一个元素以及它们是否处于正确顺序。接下来，算法将进行两次额外的递归调用，分别对数组的前三分之二和后三分之二进行排序。

因此，Stooge Sort 的时间复杂度可以通过以下递归关系表示：

t(n)=3T(2n/3) + O(1)，其中 n 是数组的大小。

随后的公式给出了 O(n^(log 3 / log 1.5)) 的时间复杂度，在最坏情况下，这大约等于O(n^2.7095)。

因此，与 Quicksort 或 Mergesort 等排序算法相比，Stooge Sort 具有相当高的时间复杂度，后者的时间复杂度值较低。

空间复杂度

Stooge Sort 算法的空间复杂度主要与排序过程中进行的递归调用以及用于存储变量和 Stooge 调用栈的额外空间有关。

我们将递归调用所需的空间视为O(log n)，因为递归深度在最坏情况下评估为O(log n)。此外，由于它在原地对输入数组进行排序，因此无需为任何数据结构或辅助数组分配额外空间。

因此，在O(log n) 中，Stooge Sort 实现的空间复杂度，其中 n 是数组的大小。