C++ 实现桶排序的示例代码

 更新时间:2021年7月12日 15:00  
桶排序或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子,本文详细的介绍了如何实现,感兴趣的可以了解一下

桶排序:整数 

原理

原理简述:按照需要排序数组的实际情况,生成一个一定长度的一维数组,用于统计需要排序数组的不同数值的重复次数,完成统计后,再按顺序重复输出该数值

实现步骤:

  • 确定需要排序数组的最大值和最小值
  • 生成桶数组,并初始化
  • 对需要排序数组进行统计,统计结果放入相应的桶中
  • 循环输出桶,并替换原序列

模拟生成整数随机数

#include <random>
#include <ctime>
 
// 传入空数组arr[]以及它的长度len,填入[min, max]区间内的随机整数
void getRand(int arr[], int len, int min, int max) {
    std::default_random_engine e;
    e.seed(time(0));
    std::uniform_int_distribution<int> u(min,max);
    for (int i = 0; i < len; i++) arr[i] = u(e);
}

桶排序实现

#include <climits>
 
void bucketSort(int arr[], int len) {
    // 确定最大值和最小值
    int max = INT_MIN; int min = INT_MAX;
    for (int i = 0; i < len; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
 
    // 生成桶数组
    // 设置最小的值为索引0,每个桶间隔为1
    int bucketLen = max - min + 1;
    // 初始化桶
    int bucket[bucketLen];
    for (int i = 0; i < bucketLen; i++) bucket[i] = 0;
 
    // 放入桶中
    int index = 0;
    for (int i = 0; i < len; i++) {
        index = arr[i] - min;
        bucket[index] += 1;
    }
 
    // 替换原序列
    int start = 0;
    for (int i = 0; i < bucketLen; i++) {
        for (int j = start; j < start + bucket[i]; j++) {
            arr[j] = min + i;
        }
        start += bucket[i];
    }
}

完整版可运行程序

#include <iostream>
#include <random>
#include <ctime>
#include <climits>
 
// 一些参数
const int MAX = 30;
const int LEN = 64;
 
void bucketSort(int arr[], int len);
void getRand(int arr[], int len, int min, int max);
 
int main() {
    int arr[LEN] = {0};
 
    // 产生随机值
    getRand(arr,LEN,0,MAX);
 
    // 打印随机值
    std::cout << "Before sorted:" << std::endl;
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << "" << std::endl;
 
    // 排序
    bucketSort(arr,LEN);
 
    // 打印输出值
    std::cout << "After sorted:" << std::endl;
    for (int i : arr) {
        std::cout << i << " ";
    }
}
 
void getRand(int arr[], int len, int min, int max) {
    std::default_random_engine e;
    e.seed(time(0));
    std::uniform_int_distribution<int> u(min,max);
    for (int i = 0; i < len; i++) arr[i] = u(e);
}
 
void bucketSort(int arr[], int len) {
    // 确定最大值和最小值
    int max = INT_MIN; int min = INT_MAX;
    for (int i = 0; i < len; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }
 
    // 生成桶数组
    // 设置最小的值为索引0,每个桶间隔为1
    int bucketLen = max - min + 1;
    // 初始化桶
    int bucket[bucketLen];
    for (int i = 0; i < bucketLen; i++) bucket[i] = 0;
 
    // 放入桶中
    int index = 0;
    for (int i = 0; i < len; i++) {
        index = arr[i] - min;
        bucket[index] += 1;
    }
 
    // 替换原序列
    int start = 0;
    for (int i = 0; i < bucketLen; i++) {
        for (int j = start; j < start + bucket[i]; j++) {
            arr[j] = min + i;
        }
        start += bucket[i];
    }
}

结果 

时间复杂度计算

分析算法步骤:

  • 确定需要排序数组的最大值和最小值 - 循环len次
  • 生成桶数组,并初始化 - 循环bucketLen次
  • 对需要排序数组进行统计,统计结果放入相应的桶中 - 循环len次
  • 循环输出桶,并替换原序列 - 循环bucketLen+len次

总时间复杂度为 O(3*len + 2*bucketLen) .

P.S. 浮点型的桶排序,由于考虑到每个桶之间区间间隔难以确定、每个桶内储存的值数量不定等情况,笔者目前尚无法通过基础的C++运算来实现,使用一些高级功能又怕时间复杂度爆炸,最终得不偿失,不如转而研究其他类型的排序方法更值得。如果有大佬写出来浮点型桶排序,可以评论或者私信我,感谢!

** 参考书籍:啊哈!算法

到此这篇关于C++ 实现桶排序的示例代码的文章就介绍到这了,更多相关C++ 桶排序内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!

相关文章

  • 深入学习C++智能指针之shared_ptr与右值引用的方法

    智能指针的核心实现技术是引用计数,每使用它一次,内部引用计数加1,每析构一次内部的引用计数减1,减为0时,删除所指向的堆内存,今天通过本文给大家分享C++智能指针之shared_ptr与右值引用的方法,需要的朋友跟随小编一起看看吧...2021-07-13
  • C++字符串的处理详解

    这篇文章主要介绍了C++ string字符串类,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-08-13
  • 浅谈C++类型转换几种情况

    本文主要介绍了几种C++类型转换,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-08-05
  • C++实现LeetCode(37.求解数独)

    这篇文章主要介绍了C++实现LeetCode(37.求解数独),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-14
  • C++ const关键字分析详解

    C++中的const关键字的用法非常灵活,而使用const将大大改善程序的健壮性。这篇文章主要介绍了C/C++ 中const关键字的用法,需要的朋友可以参考下...2021-08-29
  • C/C++中虚基类详解及其作用介绍

    这篇文章主要介绍了C/C++中虚基类的详解及其作用介绍,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-04
  • C++变量引用的概念介绍

    这篇文章主要介绍了C++变量引用的概念介绍,简单提到了与指针概念的不同,通过代码场景分析给大家介绍的非常详细,需要的朋友可以参考下...2021-08-04
  • 一文搞懂C++中的四种强制类型转换

    很多朋友向小编了解C语言中怎么进行强制类型转换呢?在这小编告诉大家强制类型转换可以分为两种,一种是隐式类型转换一种是显示类型转换,下面通过示例代码给大家介绍下,需要的朋友参考下吧...2021-07-07
  • C++中char[]能修改char*却不行

    本文主要介绍了C++中char[]能修改char*却不行,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-13
  • C++:构造函数,析构函数详解

    今天小编就为大家分享一篇关于C++构造函数和析构函数的文章,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧...2021-09-01
  • 一篇文章带你了解C++智能指针详解

    这篇文章主要介绍了c++ 智能指针基础的相关资料,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下,希望能给你带来帮助...2021-08-13
  • C++实现矩阵对称正交化的示例代码

    这篇文章主要介绍了C++实现矩阵对称正交化,分为python代码和C++的eigen库实现代码,代码简单易懂,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-09-15
  • C++ 约瑟夫环问题案例详解

    这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
  • 结构体对齐的规则详解及C++代码验证

    在c语言的结构体里面一般会按照某种规则去进行字节对齐。本文就来介绍一下如何实现,具有一定的参考价值,感兴趣的可以了解下...2021-08-17
  • 线段树详解以及C++实现代码

    线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中,这篇文章主要给大家介绍了关于线段树以及C++实现的相关资料,需要的朋友可以参考下...2021-07-19
  • C++实现LeetCode(51.N皇后问题)

    这篇文章主要介绍了C++实现LeetCode(51.N皇后问题),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-14
  • 从c++标准库指针萃取器谈一下traits技法(推荐)

    本篇文章基于gcc中标准库源码剖析一下标准库中的模板类pointer_traits,并且以此为例理解一下traits技法,对c++ traits技法源码分析感兴趣的朋友跟随小编一起看看吧...2021-07-14
  • C++手写内存池的案例详解

    这篇文章主要介绍了C++手写内存池的案例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-08-08
  • C/C++实现快速排序(两种方式)图文详解

    这篇文章主要介绍了C/C++实现快速排序的方法,这几天在找工作,被问到快速排序,结果想不出来快速排序怎么弄的;回来搜索了一下,现在记录下来,方便以后查看...2021-08-13
  • C++ 实现桶排序的示例代码

    桶排序或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子,本文详细的介绍了如何实现,感兴趣的可以了解一下...2021-07-12