详解C++ 桶排序（BucketSort）

一、思路

是将[0,1]区间划分为n个等长的子区间。然后，将各个元素按照自己所属的区间放入相应的桶中，只需要将每个桶的元素排好序，依次输出各个桶内的元素，就得到了有序的元素序列。

二、实现程序：

#include <iostream>
using namespace std;

const int offset = 105; // 为桶的边界
const int maxSize = 100; // 数组的最大存储范围

// 桶排序
template <typename T>
void BucketSort(T arr[], int n);
// 输出数组
template <typename T>
void Print(T arr[], int n);

int main(int argc, const char * argv[]) {
    int n, i, arr[maxSize];
    
    cout << "请输入要排序的数的个数：";
    cin >> n;
    srand((int)time(NULL)); // 设置时间为随机点
    for(i = 0; i < n; i++) // 产生n个随机数
        arr[i] = rand() % 100;
    cout << "排序前：";
    Print(arr, n);
    BucketSort(arr, n); // 调用桶排序
    std::cout << "排序后：";
    Print(arr, n);
    return 0;
}

template <typename T>
void BucketSort(T arr[], int n) {
    int i, j;
    T buckets[offset];
    
    for(i = 0; i < offset; i++) // 清零
        buckets[i] = 0;
    // 1.计数,将数组arr中的元素放到桶中
    for(i = 0; i < n; i++)
        buckets[arr[i]]++; // 将arr[i]的值对应buckets数组的下标，每有一个就加1
    // 2.排序
    for(i = 0, j = 0; i < offset; i++) {
        while(buckets[i] > 0) { // 说明存有元素,相同的整数，要重复输出
            arr[j] = i;
            buckets[i]--;
            j++;
        }
    }
}

// 输出数组
template <typename T>
void Print(T arr[], int n) {
    int i;
    
    for(i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

测试结果：

以上所述是小编给大家介绍的C++桶排序详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

  • c++编写String类代码实例

    本文实例为大家分享了c++编写String类的具体代码,供大家参考,具体内容如下 class String { public: String(const char* = nullptr); //普通构造函数 String(const String& other); //拷贝构造函数 ~String(void); //析构函数 String& operator = (const String& other); //赋值函数 private: char* m_data; }; //普通

  • C++中rapidjson组装继续简化的方法

    rapidjson组装继续简化------人生苦短,我用rapidjson 看最简单的: #include <iostream> #include <stdio.h> #include<unistd.h> #include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> #include<sstream> // 请自己下载开源的rapidjson #includ

  • C++堆和栈的区别与联系讲解

    C++中,内存分为5个区:堆.栈.自由存储区.全局/静态存储区和常量存储区. 栈:是由编译器在需要时自动分配,不需要时自动清除的变量存储区.通常存放局部变量.函数参数等. 堆:是由new分配的内存块,由程序员释放(编译器不管),一般一个new与一个delete对应,一个new[]与一个delete[]对应.如果程序员没有释放掉,        资源将由操作系统在程序结束后自动回收. 自由存储区:是由malloc等分配的内存块,和堆十分相似,用free来释放. 全局/静态存储区:全局变量和静态变量

  • C++与namespace有关的两个编译错误的讲解

    某次,在大型的工程代码中,我这样调用: #include <iostream> using namespace std; namespace A { void fun() { printf("aaa\n"); } } namespace B { void fun() { printf("bbb\n"); } } int main() { fun(); return 0; } 编译出错:error: 'fun' was not declared in th

  • C++中rapidjson将嵌套map转为嵌套json的讲解

    rapidjson将嵌套map转为嵌套json------人生苦短,我用rapidjson 看代码: #include <iostream> #include <map> // 请自己下载开源的rapidjson #include "rapidjson/prettywriter.h" #include "rapidjson/rapidjson.h" #include "rapidjson/document.h" #incl

  • strings命令分析浅谈Go和C++编译时的一点小区别

    最近查一个bug, 用strings命令分析, 竟然出乎意料地没有结果, 非常纳闷. 最后根据这个线索查出了bug的根本原因. 1.  在C++中, 即使函数在代码层面没有被调用, 也会最终编译到二进制中, 用strings可以分析.  #include <iostream> using namespace std; void fun() { printf("hello world\n"); // strings分析有结果 } int main() { return 0;

  • C++直接cout指针名的含义?

    C++直接cout指针名的含义?

    首先看下面这个代码实例: #include <iostream> using namespace std; int main() { char *str = "this is a test"; cout << "str=" << str << endl; cout << "*str=" << *str << endl; cout << "&a

  • C++基类指针和派生类指针之间的转换方法讲解

    函数重载.函数隐藏.函数覆盖 函数重载只会发生在同作用域中(或同一个类中),函数名称相同,但参数类型或参数个数不同. 函数重载不能通过函数的返回类型来区分,因为在函数返回之前我们并不知道函数的返回类型. 函数隐藏和函数覆盖只会发生在基类和派生类之间. 函数隐藏是指派生类中函数与基类中的函数同名,但是这个函数在基类中并没有被定义为虚函数,这种情况就是函数的隐藏. 所谓隐藏是指使用常规的调用方法,派生类对象访问这个函数时,会优先访问派生类中的这个函数,基类中的这个函数对派生类对象来说是隐藏起来的.

  • C++类中变量也可以是引用的代码实例

    C++类中变量也可以是引用哈------要用初始化列表来初始化(因为C++引用一旦绑定,就无法更换,有点类似const) #include <iostream> using namespace std; class A { public: int &x; int &y; A(int &tmpX, int &tmpY):x(tmpX), y(tmpY){} }; int main() { int tmpX = 1; int tmpY = 2; A a(tmpX,

  • C++中rapidjson将map转为json的方法

    rapidjson将map转为json------人生苦短,我用rapidjson 直接撸代码: #include <iostream> #include <map> // 请自己下载开源的rapidjson #include "rapidjson/prettywriter.h" #include "rapidjson/rapidjson.h" #include "rapidjson/document.h" #includ

随机推荐