C++ Bogosort 算法

2025年3月22日 | 阅读 13 分钟

Bogosort 是一种非常低效的排序算法，其工作原理是通过随机排列数组中的元素，直到数组有序。由于其平均和最坏情况下的时间复杂度非常糟糕，高达阶乘，因此在实际应用中不可行。

该算法通过反复随机打乱数组元素来工作，直到数组排序。 “Bogosort” 这个名字来源于“bogus”（假的）或“fake”（虚假的）这两个词。

虽然它可能不是最高效的，但 Bogosort 作为算法设计中随机性的隐喻，以及在实际实现中效率的重要性。由于它在处理大型数据集时性能极差，因此有时被用来说明在设计排序算法时应避免的做法。

方法一：基本实现

C++ 中给出的代码实现了 Bogosort 对给定整数数组的排序功能。Bogosort 是一种极其低效的算法，模拟了不断打乱数组内容直到其有序的状态。尽管 Bogosort 在现实生活中很不实用（想象一下所需的时间），但它是计算机科学中一个有趣的有趣概念，并经常被用来说明算法的防篡改性有多重要。

程序

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
//Function to check if the array is sorted
bool isSorted(const std::vector<int>& arr) {
    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    }
    return true;
}
//Function to shuffle the array randomly
void shuffleArray(std::vector<int>& arr) {
    std::random_shuffle(arr.begin(), arr.end());
}
//Function to perform Bogosort
void bogosort(std::vector<int>& arr) {
    // Seed the random number generator with the current time
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    // Repeat until the array is sorted
    while (!isSorted(arr)) {
        shuffleArray(arr); // Shuffle the array randomly
    }
}
int main() {
    // Example usage
    std::vector<int> arr = {5, 2, 7, 1, 9};   
    std::cout << "Original array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;   
    bogosort(arr); // Sort the array using Bogosort 
    std::cout << "Sorted array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

输出

说明

isSorted 函数
此过程用于验证数组是否为非递减顺序。它遍历数组，将当前处理的元素与其后续元素进行比较。如果任何一对元素不按正确顺序排列，则函数返回 false，但如果它们按正确顺序排列，则无论如何都返回 true。
shuffleArray 函数
此功能用于随机重排数组中元素的顺序。它使用 routines 头文件中的 `std::random_shuffle` 算法来实现随机打乱。
bogosort 函数
此函数实现了 Bogosort 算法。它将通过 `shuffleArray` 函数随机打乱数组，直到数组排序，并通过 `isSorted` 函数进行检查。
主函数
在 `main` 函数中，初始化了一个示例整数数组。首先打印原始数组。然后调用 `bogosort` 函数对数组进行排序。最后，显示排序后的数组，作为算法的最后阶段。

此代码中使用的 Bogosort 算法基于机会和蛮力。它实际上什么都不做，只是随机地反复打乱数组元素，直到最终找到一个排序的排列。由于 Bogosort 的工作方式，它效率低下且不适用于大型数据集，尤其是在所有方面。

复杂度分析

时间复杂度

isSorted 函数 遍历数组一次，并将每个元素与其下一个元素进行比较。它的时间复杂度为 O(n)，其中 n 是数组中的项目数。

shuffleArray 函数使用 std::random_shuffle 函数来打乱整个数组，其时间复杂度为 O(n)。在 bogosort 函数中，如果待排序数组未排序，则会重复执行此操作。由于 Bogosort 是一种时间复杂度没有上限的算法，并且基于随机打乱，因此其时间复杂度会高度变化，平均值也很高。在最极端的情况下，当它试图生成一个恰好排序的随机排列时，甚至可能接近无限。

然而，这里Bogosort 实现的总体时间复杂度也非常不稳定，并且由于 Bogosort 的特性，平均而言通常相当高。

空间复杂度

该算法的空间复杂度主要取决于存储数组和函数执行期间使用的数据结构所需的空间。

由于数组是此实现中最重要的数据结构，因此空间复杂度成为存储数组所需的内存空间量。因此，空间复杂度为 O(n)，其中 n 是数组中元素的总数。

方法二：使用链表

在此实现中，我们演示了如何将 Bogosort 应用于链表数据结构。链表是动态数据结构，由一系列链接在一起的元素组成，每个元素都有指向下一个项的指针。虽然由于其顺序访问特性，链表不是排序算法的首选，但链表提供了关于 BogoSort 如何应用于不同数据结构的另一种视角。

简报首先定义一个简单的链表结构，并检查排序、打乱链表以及使用链表应用 Bogosort。其中一项主要任务是演示如何使用这些函数通过 Bogosort 对整数链表进行排序。

另一方面，链表上的 Bogosort 表明该算法可以调整以适应任何数据结构，但代价是 Bogosort 本身不可避免的低效。Bogosort 在现实世界的排序项目中没有实际意义，仅用于学术目的。

程序

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm> // for std::shuffle
#include <random>    // for std::default_random_engine and std::mt19937
//definition of a simple linked list node
struct Node {
    int data;
    Node* next; 
    Node(int val) : data(val), next(nullptr) {}
};
//Function to check if the linked list is sorted
bool isSorted(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        return true; // A single node or an empty list is considered sorted
    }  
    Node* current = head;
    while (current->next != nullptr) {
        if (current->data > current->next->data) {
            return false; // If any adjacent pair is out of order, the list is not sorted
        }
        current = current->next;
    }
    return true;
}
//Function to shuffle the linked list randomly
Node* shuffleLinkedList(Node* head) {
    // Convert the linked list to a vector for shuffling
    std::vector<int> values;
    Node* current = head;
    while (current != nullptr) {
        values.push_back(current->data);
        current = current->next;
    }
    // Shuffle the vector
    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(values.begin(), values.end(), g);   
    // Reconstruct the linked list from shuffled values
    Node* newHead = nullptr;
    Node* tail = nullptr;
    for (int val : values) {
        Node* newNode = new Node(val);
        if (newHead == nullptr) {
            newHead = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = tail->next;
        }
    }    
    return newHead;
}
// Bogosort using a linked list
Node* bogosortWithLinkedList(Node* head) {
    while (!isSorted(head)) {
        head = shuffleLinkedList(head); // Shuffle the linked list
    }
    return head;
}
//Function to print the linked list
void printLinkedList(Node* head) {
    while (head != nullptr) {
        std::cout << head->data << " ";
        head = head->next;
    }
    std::cout << std::endl;
}
//Function to deallocate memory used by the linked list
void deleteLinkedList(Node* head) {
    while (head != nullptr) {
        Node* temp = head;
        head = head->next;
        delete temp;
    }
}
int main() {
    // Example usage
    Node* head = new Node(5);
    head->next = new Node(2);
    head->next->next = new Node(7);
    head->next->next->next = new Node(1);
    head->next->next->next->next = new Node(9);  
    std::cout << "Original Array: ";
    printLinkedList(head);  
    // Call Bogosort using a linked list
    head = bogosortWithLinkedList(head);    
    std::cout << "Sorted Array: ";
    printLinkedList(head);    
    // Deallocate memory used by the linked list
    deleteLinkedList(head);    
    return 0;
}

说明

链表节点定义 (struct Node)
形成一个通用的链表节点结构，它包括数据字段 (int data) 并定义一个指向下一个节点的指针 (Node* next)。
isSorted 函数
检查链表是否按排序或非递减顺序排列。它像遍历链表一样遍历链表，并将每个元素与下一个元素进行比较。是否可以比较任何不匹配的相邻对？它返回 false。另一方面，任何相邻对是否都按顺序排列？它返回 true。
shuffleLinkedList 函数
通过一个“plunger”（可能指的是某种机制）随机打乱链表。通过一个“randomize”方法，该方法将链表转换为向量，从而使打乱变得容易。接下来是使用另一个算法对向量进行打乱，该算法也用于“de-link”列表的元素。打乱后的向量会生成一个链表，然后可以正确地重建该链表。
bogosortWithLinkedList 函数
链表将被用于实现 Bogosort 算法。因此，虽然 O(n^2) 排序算法首先尽快将链表分成两部分，直到达到一个元素，插入排序算法会不断改变所选元素的位置，直到列表排序，正如 isSorted 所确定的那样。
printLinkedList 函数
将链表的元素显示到标准输出。它从头部到尾部进行遍历，并打印每个元素，后面跟着一个空格。
deleteLinkedList 函数
将“null”赋值为链表的最后一个节点。它像之前一样一次遍历链表中的一个节点，但不是替换列表的头部，而是将要删除的节点与每个节点一起丢弃，直到达到列表的最后一个指针。
主函数
展示了给定函数的使用。使用我们的人工智能为任何主题写作！无论您是想写一篇艺术史论文还是关于自然的诗歌，AI 都可以帮助您开始。创建具有整数值列表的单向链表示例。然后，使用 printLinkedList 打印给定数组。

我们将调用 bogosortWithLinkedList 来执行 Bogosort 排序。此方法将排序数组并通过调用 printLinkedList 显示结果。通过执行 deleteLinkedList() 函数销毁先前分配的内存。

复杂度分析

时间复杂度

isSorted 函数的时间复杂度为 O(n)，其中 n 是链表中的元素数量。它通过链表查找排序错误来实现这一点。shuffleLinkedList 函数首先将链表转换为向量，其时间复杂度为 O(n)，其中 n 是列表中元素的数量。接下来，向量打乱需要 O(n) 时间复杂度。最后，我们从刚刚打乱的向量中构建链表，耗时 O(n)，因为这是它包含的元素数量。因此，shuffleListedList 的最终时间复杂度为O(n)。

bogosortWithLinkedList 函数不断调用 shuffleLinkedList 来对链表进行排序。BogosortWithLinkedList 的渐近最坏时间复杂度过高，可能达到非常高的值，因为 Bogosort 没有时间复杂度的上限。平均而言，冒泡排序的时间复杂度为 O((n+1)!)，其中 n 是链表中的元素数量。这是因为 Bogosort 是一种随机搜索，涉及列表元素的多次排列，直到找到排序的排列。printLinkedList 函数的时间复杂度为 O(n)，其中 n 是链表节点的数量。这是因为整个链表将被遍历一次以打印每个元素。

deleteLinkedList 函数在此处表现出 O(n) 的时间复杂度，其中 n 是链表中的元素数量。这是因为它对所有必须单独删除的链表执行此步骤。

整个函数的复杂度是 bogosortWithLinkedList 函数的复杂度，但由于主函数趋近于无界，平均时间复杂度非常高。

空间复杂度

给定算法的空间复杂度主要取决于存储链表和函数运行时使用的任何其他数据结构所需的空间。代码的空间复杂度也为O(n)；这是因为存储链表所需的空间优先于空间复杂度。链表中每个链接所占用的空间的大小等于所有项的大小。

方法三：使用 BST

使用二叉搜索树 (BST) 的 BogoSort 的做法是根据给定的元素构建 BST，并检查生成的树是否为有效的二叉搜索树。如果是，则认为元素已排序；否则，过程会重新运行，直到获得有效的 BST。

程序

#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <algorithm> // for std::random_shuffle
#include <limits>    // for std::numeric_limits
// Definition of Binary Search Tree (BST) node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
//Function to check if a binary tree is a valid BST
bool isBST(TreeNode* root, int minVal, int maxVal) {
    if (root == nullptr) {
        return true;
    }
    if (root->data <= minVal || root->data >= maxVal) {
        return false;
    }
    return isBST(root->left, minVal, root->data) && isBST(root->right, root->data, maxVal);
}
//Function to shuffle elements of a vector randomly
void shuffleVector(std::vector<int>& vec) {
    std::random_shuffle(vec.begin(), vec.end());
}
//Function to insert a value into a BST
TreeNode* insertIntoBST(TreeNode* root, int val) {
    if (root == nullptr) {
        return new TreeNode(val);
    }
    if (val < root->data) {
        root->left = insertIntoBST(root->left, val);
    } else {
        root->right = insertIntoBST(root->right, val);
    }
    return root;
}
//Function to construct a BST from a vector of elements
TreeNode* constructBST(const std::vector<int>& elements) {
    TreeNode* root = nullptr;
    for (int elem : elements) {
        root = insertIntoBST(root, elem);
    }
    return root;
}
//Function to perform an inorder traversal of a BST (printing the sorted elements)
void printInorder(TreeNode* root) {
    if (root != nullptr) {
        printInorder(root->left);
        std::cout << root->data << " ";
        printInorder(root->right);
    }
}
//Function to delete a BST (freeing memory)
void deleteBST(TreeNode* root) {
    if (root != nullptr) {
        deleteBST(root->left);
        deleteBST(root->right);
        delete root;
    }
}
//Function to perform Bogosort with a BST
void bogosortWithBST(std::vector<int>& elements) {
    while (true) {
        shuffleVector(elements);          // Shuffle the elements randomly
        TreeNode* root = constructBST(elements); // Construct a BST from the shuffled elements
        if (isBST(root, std::numeric_limits<int>::min(), std::numeric_limits<int>::max())) {
            printInorder(root);           // Print the sorted elements
            std::cout << std::endl;
            deleteBST(root);              // Delete the constructed BST to prevent memory leaks
            break;
        }
        deleteBST(root); // Delete the constructed BST to prevent memory leaks
    }
}
int main() {
    // Example usage
    std::vector<int> elements = {5, 2, 7, 1, 9};
    std::cout << "Original elements: ";
    for (int elem : elements) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    std::cout << "Sorted elements: ";
    bogosortWithBST(elements);
    return 0;
}

输出

Original elements: 5 2 7 1 9 
Sorted elements: 1 2 5 7 9

说明

结构定义
对于 BST，定义了捕获 BST 节点的 `TreeNode` 结构。每个节点包含整数信息、指向左子节点的地址和指向右子节点的另一个地址。
辅助函数
isBST：此函数旨在检查特定的二叉树，以识别它是否为有效的二叉搜索树节点 (BST)。它反复遍历树并使根节点确保每个节点元素都在其在树中的数字范围内。

shuffleVector：这是一个过程，其中向量元素使用 <algorithm> 头文件中的std::random_shuffle算法随机合并。

insertIntoBST：此开关允许将值插入 BTS。此外，它还有一个算法，可以递归地遍历树并将值插入到正确的位置，同时确保BST 属性。

Construct BST：此函数的作用是从可变数量的对象创建 BST。它遍历每个元素，并使用insertIntoBST函数将每个项放入 BST。

printInorder：该函数遍历二叉搜索树，生成中序遍历，以排序顺序打印元素。

deleteBST：此函数递归地删除每个 BST，从而导致内存泄漏。

BST 版 Bogosort
BogosortWithBST 函数使用 BST 作为其数据结构来实现 Bogosort 算法效率。它重复打乱元素、创建 BST，并使用 BST 检查它是否是有效的 BST。打印顺序方法用于打印 BST 的排序元素。
主函数
main 函数模块提供了示例。它创建并分配数组中的元素，显示原始元素，调用 bogosortWithBST 进行排序并查看结果。

复杂度分析

时间复杂度

BST 操作下的 BogoSort 的时间复杂度显示出高度可变和无界行为。在最坏的情况下，算法可能会永远运行或永不终止。当打乱过程未产生有效组合时，就会发生这种情况。

时间复杂度取决于找到导致有效 BST 的正确排列的几率。虽然发生的可能性接近零，但由此产生的预期时间复杂度非常高。

平均时间复杂度可以粗略估计为 O(n! \* h)，其中 n 是元素数量，h 是生成的二叉搜索树的高度。此估计通过避免对所有可能的排列进行详尽搜索来计算验证每个排列的时间复杂度。

空间复杂度

使用 BST 的 Bogosort 的空间复杂度为 O(n)，其中 n 是元素数量。这种空间复杂度是因为输入向量中存储的元素占用的空间以及BST 结构的空间。

BST 的每个节点不仅占用内存为其分配的数据值，还占用其指向左子节点和右子节点的父指针。该算法使用基于给定元素的最终 BST 创建，其空间复杂度直接与输入向量中的元素数量成正比。

下一主题C++ 中 std::atomic 与 volatile 的区别

C++ Bogosort 算法

方法一：基本实现

程序

说明

复杂度分析

方法二：使用链表

程序

说明

复杂度分析

方法三：使用 BST

程序

说明

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ Bogosort 算法

方法一：基本实现

程序

说明

复杂度分析

方法二：使用链表

程序

说明

复杂度分析

方法三：使用 BST

程序

说明

复杂度分析

相关帖子

C++ 中基于范围的 for 循环和基于迭代器的 for 循环之间的区别

C++ 与 Prolog 的区别

C++ 莫兰数

C++ 中的 std::midpoint

C++ 中的莫比乌斯函数计算

C++ 中的双基半完全数

在 C++ 中使用 Shanks Tonelli 算法在模 p 下查找平方根

C++ 零和博弈策略