C++ 中的鸽笼排序算法

2025年5月10日 | 阅读 16 分钟

鸽笼排序 是一种排序算法，适用于列表中的元素数量和元素的键值范围大致相同的场景。它基于“巢穴形成”（也称为“桶”）的概念，将元素根据其键值特征划分为几个鸽笼，然后在同一类别下进行排序，最后将这些值组合起来形成原始列表。当键值对的范围远小于元素的总数时，此算法特别有用。

鸽笼排序与广为人知的桶排序算法相对应，并且在实现上具有无与伦比的简洁性。它不像其他算法那样需要划分“桶的大小”，而是将每个键值对映射到一个鸽笼。分发过程意味着为每个元素分配一个与其键值相对应的箱子，从而使相似的项聚集在一起。后续的鸽笼用于交叉排序，通常使用插入排序，因为插入排序对小数据集非常高效。

通过线性鸽笼排序，在计数方面效果最佳，其计数几乎与元素数量和键值范围相同。但鸽笼排序的应用范围有限，随着范围的增加，性能可能会下降，导致内存消耗更高，效率降低。尽管存在这些限制，该技术在特定情况下的实际应用使其成为一种重要的排序方法，主要用于键值范围相对较小的一维数据。由于其易于实现，它完全可以在现实生活中使用，并且在利用数据集的特定特征进行排序方面具有优势。

方法一：基本鸽笼排序

用户基本鸽笼排序算法是原始鸽笼排序算法的一个变体，它是一种非比较排序方法。该方法最适用于输入变量中元素数组的宽度小于元素总数的情况。它的设置简单，易于使用，尤其适合初学者，也适用于约束数据集的排序任务。

用户基本鸽笼排序利用元素的值来首先将数据排序到各个“鸽笼”或“桶”中。然后，它对每个“鸽笼”中的元素进行排序，然后将它们连接回原始列表。然而，此版本通过数据结构和基本概念以更简单的方式保留了鸽笼排序算法的基本原理。

程序

#include <iostream>
#include <vector>
#include <algorithm>
void userBasicPigeonholeSort(std::vector<int>& arr) {
    // Step 1: Find the minimum and maximum values in the array to determine the range.
    int min_val = *std::min_element(arr.begin(), arr.end());
    int max_val = *std::max_element(arr.begin(), arr.end());
    int range = max_val - min_val + 1; // Calculate the range of values
    // Step 2: Create an array of pigeonholes (buckets) initialized with zeros.
    std::vector<int> pigeonholes(range, 0);
    // Step 3: Place each element into its respective pigeonhole based on its value.
    for (int i = 0; i < arr.size(); ++i) {
        int index = arr[i] - min_val; // Calculate the index of the pigeonhole for the current element
        pigeonholes[index]++; // Increment the count in the corresponding pigeonhole
    }
    // Step 4: Retrieve the elements from the pigeonholes in order and place them back into the original array.
    int index = 0;
    for (int i = 0; i < range; ++i) {
        while (pigeonholes[i] > 0) {
            arr[index++] = i + min_val; // Adjust the index to the actual value and place it in the original array
            pigeonholes[i]--; // Decrement the count in the pigeonhole
        }
    }
}
int main() {
    // Example usage of User Basic Pigeonhole Sort
    std::vector<int> arr = {8, 3, 2, 7, 4, 6, 8};
    std::cout << "Original Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    // Sort the array using User Basic Pigeonhole Sort
    userBasicPigeonholeSort(arr);
    std::cout << "Sorted Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

输出

Original Array: 8 3 2 7 4 6 8 
Sorted Array: 2 3 4 6 7 8 8

解释

将元素放入鸽笼：我们遍历输入数组中的所有元素，然后找出每个鸽笼对应的位置索引。然后，我们移动该鸽笼并增加其计数。

按顺序检索元素：我们遍历鸽笼数组，并按排序顺序提取元素。我们将每个正计数的值（最大值 - 最小值）放入第一个数组。

主函数：启动一个示例数组，并写入原始数组。在下一步中，UserBasicPigeonholeSort函数对数组进行排序，然后打印排序后的数组。

该算法可以通过根据元素的函数将其分配到鸽笼，然后在每个鸽笼内进行排序，最后重构最终数组来完成此操作。它适用于数值范围明显小于元素数量的情况。提供的编码程序是一种实际且简短的排序方法，其中包含解释每个阶段的注释。

复杂度分析

时间复杂度

用户基本鸽笼排序算法的时间复杂度为 O(n + range)，其中 n 是输入数组的大小，“range”是数组中的最大值和最小值之间的绝对差。在消除数组中的最小值和最大值的第一个步骤中，需要 O(n) 的时间，因为它涉及遍历整个数组。

创建鸽笼数组并将所有元素从输入数组插入到其中，也需要 O(n) 的时间，因为需要访问数组中的每个元素一次。在最后一步，当所有元素从鸽笼中取出并放回原始数组时，仍然需要 O (n) 的时间。可以推断，当考虑时间复杂度时，范围 (range) 是最重要的因素，因为该因素可能会根据输入数据而变化。

空间复杂度

用户基本鸽笼排序方法的空间复杂度为 O(n+range)，其中 n 是输入数组中的元素数量，而“range”是数组的最大值和最小值之间的差值。鸽笼排序的空间复杂度取决于鸽笼数组的大小，该大小与输入数组中值的范围成比例。

此外，还为循环计数器等其他因素分配了单独的空间，但其影响远不如广为人知的鸽笼。范围空间是重要的竞争者，范围的空间复杂度太小，而数组的元素则太多。

方法二：原地鸽笼排序

鸽笼排序算法的修改版本，称为原地鸽笼排序，允许在不消耗任何额外内存资源存储单独鸽笼的情况下对数组元素进行排序。虽然鸽笼排序使用辅助数组来包含鸽笼，但原地鸽笼算法直接在同一数组中对元素进行排序。这种策略带来了内存管理性能提高的可能性，但缺点是实现可能很复杂。

直接地址映射通过更改元素所在的初始数组来提高内存效率。另一方面，复杂的实现是鸽笼排序在处理冲突之外的额外挑战。

程序

#include <iostream>
#include <vector>
#include <algorithm>
void inPlacePigeonholeSort(std::vector<int>& arr) {
    // Step 1: Find the minimum and maximum values in the array to determine the range.
    int min_val = *std::min_element(arr.begin(), arr.end());
    int max_val = *std::max_element(arr.begin(), arr.end());
    int range = max_val - min_val + 1; // Calculate the range of values
    // Step 2: Place each element into its respective pigeonhole based on its value.
    for (int i = 0; i < arr.size(); ++i) {
        int index = arr[i] - min_val; // Calculate the index of the corresponding pigeonhole
        while (index < arr.size() && arr[index] == arr[i]) {
            ++index; // Handle collisions by moving to the next available slot
        }
        std::swap(arr[i], arr[index]); // Swap the elements to place them in their correct positions
    }
}
int main() {
    // Example usage of In-Place Pigeonhole Sort
    std::vector<int> arr = {3, 2, 7, 4, 6, 8};
    std::cout << "Original Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    // Sort the array using In-Place Pigeonhole Sort
    inPlacePigeonholeSort(arr);
    std::cout << "Sorted Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

输出

Original Array: 3 2 7 4 6 8 
Sorted Array: 2 3 4 7 6 8

解释

查找范围

算法将首先找到输入数组中的最小值和最大值。这是算法确定数组中可能存在的值的范围的点，这当然是进一步计算的前提条件。

将元素放入鸽笼

遍历这些数组的每一步都会进行。由于从元素值中减去最小值，因此确定了“鸽笼”或“桶”的索引。这提供了所需数组元素的索引。

如果索引被具有相似值的另一个项目占用，则算法会丢弃当前正在处理的项目，然后继续处理数组中的下一个元素，直到找到一个空位。这是因为要确保每个方面都正确地放置在数组内是至关重要的。

元素将被翻转，以便它们可以正确地定向以占据数组中的特定位置。这种过程确实改变了元素的位置；因此，我们可以说它有效。

主函数

在主函数中，我们首先初始化示例数组，然后输出原始数组。

最后，调用inPlacePigeonholeSort函数进行最后一步，该函数通过指定的算法（原地鸽笼排序）对数组进行排序。排序完成后，显示排序后的数组以说明排序算法相关性的结果。

因此，利用这种原地鸽笼排序变体不需要使用额外的内存来生成辅助数组，因此与同类算法相比，原地版本更节省内存。尽管给定的算法可能看起来很简单，但它可以在原地对数组元素进行排序，完美地展示了鸽笼排序的原理。

复杂度分析

时间复杂度

原地鸽笼排序算法的时间复杂度为 O(n + range)，其中 n 是输入数组的大小，而“range”是数组中的最大值减去最小值。首先，需要 O(n) 的时间来查找最小值和最大值，在这个过程中需要遍历整个数组。

遍历所有数组需要 O(n) 的时间，因为输入数组中的所有元素都被访问一次，并逐一放入相应的立方体中并处理冲突。元素的实现也与其在数组中的可识别位置相关，也需要 O(n) 的时间。因此，时间复杂度的主要特征是值的范围（range），它决定了整体算法的效率，并影响值作为变量的范围。

空间复杂度

原地鸽笼排序算法没有空间复杂度，因为它保持在 O(1)，这意味着它使用常数空间。与其他需要额外内存数组来存储鸽笼的鸽笼排序变体不同，该算法在原地内存中对元素进行排序，没有任何副作用。所提出的算法使用恒定内存，因此只有循环计数器和临时存储等变量需要恒定空间，并且它们不依赖于输入数组的大小。因此，无论输入数组的大小如何，空间复杂度都保持在恒定值。

方法三：带计数数组的鸽笼排序

这种技术使用计数数组，用于存储输入数组中每个元素的频率。计数数组最初为空，然后填充输入数组中每个元素的出现次数。通过遍历计数数组来组装排序后的数组，然后根据每个元素的计数将其放置在正确的位置。

这种编码方法在输入值的范围较小且值是离散的情况下非常有用，因为不需要单独创建鸽笼。它需要与输入值范围成比例的额外内存大小，但与简单方法相比，其时间复杂度可能更快。

程序

#include <iostream>
#include <vector>
#include <algorithm>
// Function to perform Pigeonhole Sort with Counting Array
void pigeonholeSortWithCountingArray(std::vector<int>& arr) {
    // Step 1: Find the range of values in the input array
    int min_val = *std::min_element(arr.begin(), arr.end());
    int max_val = *std::max_element(arr.begin(), arr.end());
    int range = max_val - min_val + 1;
    // Step 2: Initialize the counting array with zeros
    std::vector<int> count(range, 0);
    // Step 3: Count the frequency of each element in the input array
    for (int num : arr) {
        count[num - min_val]++;
    }
    // Step 4: Reconstruct the sorted array using the counting array
    std::vector<int> result;
    for (int i = 0; i < range; ++i) {
        // For each non-zero count, append the corresponding value to the result array
        while (count[i] > 0) {
            result.push_back(i + min_val);
            count[i]--;
        }
    }
    // Step 5: Copy the sorted result back to the original array
    arr = result;
}
int main() {
    // Example usage of Pigeonhole Sort with Counting Array
    std::vector<int> arr = {8, 3, 2, 7, 4, 6};
    // Display the original array
    std::cout << "Original Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    // Sort the array using Pigeonhole Sort with Counting Array
    pigeonholeSortWithCountingArray(arr);
    // Display the sorted array
    std::cout << "Sorted Array: ";
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    return 0;
}

输出

Original Array: 8 3 2 7 4 6 
Sorted Array: 2 3 4 6 7 8

解释

查找范围

使用计数数组进行鸽笼排序的第一步是确定输入数组中的最小值和最大值。此分辨率也很重要，因为它为数组中值的计数奠定了基础。通过范围，算法可以确定在排序过程中需要权衡和考虑的值。

初始化计数数组

在确定了值的数组之后，将创建计数数组。该数组充当过程的底线，生成输入中每个元素的频率。初始化时，计数器数组将为空，从而便于后续操作。

计数元素的频率

接下来，算法遍历输入数组并进行计数，对每个元素进行分类，结果累积在计数数组中。对于输入数组中的每个元素，计数数组中的相应计数都会增加。这些记录充当元素值与其频率计数之间的链接，提供了一个有组织的跟踪机制。

重构排序数组

在执行完每个元素的频率计数后，算法继续进行有序列表的重构。在这一点上，我们搜索计数数组，对于每个非零计数，将关联的元素值附加到结果数组。通过这个过程，机器建立了一个序列，其中组件根据从低到高的值进行添加。

将结果复制回去

在上述排序过程的最后阶段，排序后的数组被平滑地替换回原始输入数组。这种原地排序机制也说明了鸽笼排序与计数数组方法的优雅和实用性。

复杂度分析

时间复杂度

在第一个数组中查找最小值和最大值的成本高达 O(n)，其中 n 是数组中的元素数量。另外，O(range) 的时间用于通过将元素初始化为零来设置计数数组。在这里，range 表示数组中的最大值和最小值之间的差距。

遍历每个元素以计算其频率需要对整个数组进行一次循环，因此结果为 O(n) 复杂度。为了使用累积频率数组创建新的排序数组，您应该控制整个值的范围。这需要 O(range) 时间。

因此，算法的总时间复杂度为 O(n + range)。

空间复杂度

算法的空间复杂度与其计数数组的大小成正比。计数器数组取决于输入数组中值的范围大小。在最坏情况下，当值的范围等于元素的数量时（即，每个元素具有唯一值），复杂度为 O(n)。

最坏情况下的复杂度可能会导致 range（可能等于）等于元素数量的情况，因此空间复杂度为 O(range)。因此，空间复杂度可能在 O(n) 到 O(range) 之间变化，因为输入数组中的值排列可能不同。

方法四：带链表的鸽笼排序

带链表的鸽笼排序是鸽笼排序算法的一种变体，它使用链表来保持鸽笼的顺序。这种方法提供了各种好处，尤其是在处理大型数据集且数组的内存分配效率低下时。

链表作为鸽笼

基于这种技术，每个鸽笼将通过链表表示。链表的连接点（节点）取决于数组元素。

链表只是内存中任意位置节点的逻辑流。这种数据结构提供了动态内存分配的概念，使得读写数据操作更有效，尤其适用于大型数据集。

将元素放入链表

输入数组元素根据其值放置到链表中。这些值中的每一个都链接到其自己的链表。

每当在输入数组中检测到一个元素时，它就会被附加到与该值对应的链表中。这使得下一步变得简单，即通常将元素划分为桶或鸽笼，每个链表包含相同值的元素。

合并链表

一旦元素被分发到各个链表中，接下来的过程就是最终合并所有链表，使它们形成排序后的数组。

这是一个从最低值到最高值遍历链表的过程，并将每个链表中的元素放入排序后的数组。

遍历完每个链表后，其元素就会附加到排序后的数组中。这保证了每个元素最终都根据其值进行排序。

程序

#include <iostream>
#include <vector>
// Node structure for linked list
struct Node {
    int data;     // Data of the node
    Node* next;   // Pointer to the next node
    Node(int val) : data(val), next(nullptr) {} // Constructor to initialize node with data
};
// Function to perform Pigeonhole Sort with Linked Lists
void pigeonholeSortWithLinkedLists(std::vector<int>& arr) {
    const int RANGE = 10; // Assuming the range of values is known
    // Step 1: Initialize an array of linked lists for pigeonholes
    std::vector<Node*> pigeonholes(RANGE, nullptr);
    // Step 2: Distribute elements into pigeonholes
    for (int num : arr) {
        int index = num % RANGE; // Calculate the index of the pigeonhole  
        // Check if the pigeonhole is empty
        if (pigeonholes[index] == nullptr) {
            pigeonholes[index] = new Node(num); // Create a new node if pigeonhole is empty
        } else {
            // Traverse to the end of the linked list and append the new node
            Node* current = pigeonholes[index];
            while (current->next != nullptr) {

输出

Original Array: 8 3 2 7 4 6 
Sorted Array: 2 3 4 6 7 8

解释

节点结构

链表中的节点是通过 Node 结构创建的，它标识了节点的创建方式。每个节点包含两个字段：包含存储元素值的信息数据和一个指向列表中下一个节点的 next 指针。

鸽笼排序函数

pigeonholeSortWithLinkedLists() 函数实际上是算法中实际排序过程发生的地方。此过程将数组（int 向量 arr）作为参数，并使用由链表表示的鸽笼对其所有元素进行排序。

函数首先定义RANGE，这是一个数组，对象将存储在相应的鸽笼中（单独的链表）。当提供信息值时，即当计算输入数组中 posited 的值时，情况就是如此。

下一步是创建一个指针数组（鸽笼），并为每个元素分配一个不同的头节点（链表）。首先，标志将设置为 0。

接下来，创建循环，该循环随后连续扫描所有数组元素 (arr)。对于每个元素，它会计算与索引和模运算% RANGE相关的孔洞的位置。

如果与计算出的索引相关联的值为空（即，元素的指针为 nullptr），则创建一个带有其他值的新节点。通过这样做，函数只需遍历链表直到末尾，附加一个带有该值的新节点。

该函数将所有已排序的元素排序到它们各自的槽中，然后再将已合并的列表连接回原始数组。该函数遍历数组的各个桶，遍历其每个链表，并使用已排序的元素更新原始数组，同时为每个链表节点分配内存。

主函数

pigeonholeSortWithLinkedLists() 函数用于说明名为pigeonholeSort()的数组排序算法，并分别显示输入数组、原始数组和排序后的数组。

复杂度分析

时间复杂度

将元素分发到鸽笼

用于将输入数组元素分组到鸽笼中的过程，遍历输入数组的每个元素，并遍历链表以根据需要附加/添加项。第二步在 O(n) 时间内运行，n 是初始数组中的元素数量。

合并链表

将链表与原始数组重新连接的过程也为每个列表的线性扫描做出了贡献。此外，此步骤的复杂度为 O(n)。

最后，算法的复杂度为 O(n)，其中 n 是输入数组中的元素数量。

空间复杂度

算法的空间复杂度很大程度上取决于用作存储已排序字符串的鸽笼的链表。输入数组的每个项目都放入其中一个链表的节点中。值得注意的是，它占用了等于数组中元素数量的额外内存空间。

此链表是动态创建的，因此允许在与输入数组的其余部分合并后取消分配节点，因此 O(n)，其中 n 是输入数组中的总元素数量。

下一个主题Compare-and-swap-in-cpp

← 上一个下一个 →

C++ 中的鸽笼排序算法

方法一：基本鸽笼排序

程序

解释

复杂度分析

方法二：原地鸽笼排序

程序

解释

复杂度分析

方法三：带计数数组的鸽笼排序

程序

解释

复杂度分析

方法四：带链表的鸽笼排序

链表作为鸽笼

将元素放入链表

合并链表

程序

解释

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

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++ 中的鸽笼排序算法

方法一：基本鸽笼排序

程序

解释

复杂度分析

方法二：原地鸽笼排序

程序

解释

复杂度分析

方法三：带计数数组的鸽笼排序

程序

解释

复杂度分析

方法四：带链表的鸽笼排序

链表作为鸽笼

将元素放入链表

合并链表

程序

解释

复杂度分析

相关帖子

C++ 中的施泰纳树近似