考研算法32天:桶排 【桶排序】

这篇具有很好参考价值的文章主要介绍了考研算法32天:桶排 【桶排序】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法介绍

桶排

举个例子,一个数组中的数是:4 1 2 3 5,

然后桶排的顺序是:将每个数应该在的下标算出来,咋算呢?这我们就得考虑两种情况:假设我们设现在这个需要找到自己在数组里位置的数是x。

1.比x小的数有多少个

2.和x一样大并且原先就排在自己前面的数有多少个。

如果只考虑第一种情况很简单,但是如果两种情况都考虑呢?

那么我们就需要其他的东西来保证第二个相等的元素不改变位置了。那么这个东西是啥呢?很简单,一个前缀和:如何操作呢?还是举个例子:比如一个数列:3 2 2 1 5。我们求出其前缀和(这里的前缀和是其数字出现的个数的叠加并不是数的叠加),如下图

考研算法32天:桶排 【桶排序】

然后我们从后往前开始,(又因为其数列的数如果自己是x(n-1)那么自己的位置一定是x(n)-1)所以我们每个数的位置就是在其后面那个数的前面,因为我们序列最大的数是5所以从5开始我们发现其s5(序列和)=5并且数组中有这个数所以它应该放在下标为5的位置,然后向前遍历,1应该放在s1的位置=1,所以放在最开始的位置。以此类推。

算法题目

考研算法32天:桶排 【桶排序】

#include <iostream>

using namespace std;

const int N = 1000010;
int q[N], w[N];
int s[N];
void bucket_sort(int n){
    for(int i=0;i<n;i++){
        s[q[i]]++; 
    }
    for(int i=1;i<N;i++){
        s[i] = s[i-1] + s[i];
    }
    for(int i=n-1;i>=0;i--){
        w[--s[q[i]]] = q[i]; 
    }
    for(int i=0;i<n;i++){
        q[i] = w[i];
    }
    return;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    bucket_sort(n);
    for(int i=0;i<n;i++)printf("%d ",q[i]);
    return 0;
}

acwing上面这段代码可以过10个数据。

算法复杂度

空间复杂度:O(n + m)

时间复杂度:O(n + m)

稳定性:稳定文章来源地址https://www.toymoban.com/news/detail-506485.html

到了这里,关于考研算法32天:桶排 【桶排序】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 考研算法第十三天:二叉排序树 【二叉排序树的插入和遍历】

    这道题很妙。题目给的二叉排序树好像没学过其实就是二叉查找树。然后这道题主要的就是思路     1.先找到那个要删除节点所在处     2.找到之后处理分三种情况     删除的节点是叶节点,直接删除即可     删除的节点只有右节点或者左节点 将左节点或者右节点删除即可

    2024年02月05日
    浏览(46)
  • 【数据结构入门精讲 | 第九篇】考研408排序算法专项练习(一)

    前面几篇文章介绍的是排序算法,现在让我们开始排序算法的专项练习。 1.希尔排序是稳定的算法。(错) 解析:稳定性是指如果两个元素在排序前后的相对顺序保持不变,那么这个排序算法就是稳定的。对于具有相同的元素,排序后它们的相对位置应该保持不变。

    2024年02月03日
    浏览(46)
  • 【排序算法】排序算法介绍及插入排序 ( 直接插入排序 && 希尔排序 )

    ​ ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯 长路漫漫浩浩,万事皆有期待 排序 :所谓排序,就是将一串数据,按照某种规律,或者以某种特性或,将数据按照递增或者递减,将数据从 无序转变为有序

    2023年04月21日
    浏览(40)
  • 十大排序算法之冒泡排序、快速排序的介绍

    个人主页:平行线也会相交 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 平行线也会相交 原创 收录于专栏【数据结构初阶(C实现)】 说起来冒泡排序,是我们接触到的最早的一个排序算法了,这次就当进行一个巩固提升了。冒泡排序还被称为 交换排序 。 冒泡排序: 它重

    2024年02月07日
    浏览(42)
  • 【数据结构】常见排序算法——常见排序介绍、插入排序、直接插入排序、希尔排序

      在计算机科学中,排序是将一组数据按照指定的顺序排列的过程。排序算法由于执行效率的不同可以分为多种不同的算法。   通常情况下,排序算法可以分为两类,即 内部排序和外部排序 。内部排序是指数据全部加载到内存中进行排序,适用于数据量较小的情况,而

    2024年02月08日
    浏览(60)
  • 选择排序算法介绍

    选择排序(Selection Sort)是一种简单直观的排序算法。它的基本思想是每次从待排序的元素中选取最小(或最大)的元素,放到已排序部分的末尾,直到全部元素排序完毕。 以下是选择排序的详细步骤: 首先,在待排序序列中找到最小(或最大)的元素,并将它与序列的第一

    2024年02月16日
    浏览(24)
  • 【数据结构】常见排序算法——常见排序介绍、选择排序(直接选择排序、堆排序)交换排序(冒泡排序)

      选择排序是一种简单但不高效的排序算法,其基本思想是从待排序的数据中选择最小(或最大)的元素放到已排序的数据末尾。具体操作步骤如下: (1)找到数据中最小的元素,并把它交换到第一个位置; (2)在剩下未排序的元素中找到最小的元素,并把它交换到已排

    2024年02月04日
    浏览(52)
  • 介绍java中的常见排序算法

    Java中的排序算法主要包括以下几种: 冒泡排序(Bubble Sort) 选择排序(Selection Sort) 插入排序(Insertion Sort) 快速排序(Quick Sort) 归并排序(Merge Sort) 堆排序(Heap Sort) 下面分别进行详细介绍。

    2024年02月08日
    浏览(47)
  • C++基础-介绍·数据结构·排序·算法

    C++是一门风格严谨又不失自由的开发语言,提供了完整的内存管理、支持函数式编程和面向对象编程,支持模板、多继承、多实现、重载、重写等多态特性。 优势在于目前90%的操作系统、数据库、应用基础架构、硬件嵌入式等都是使用C/C++制作的,而C++是对C的标准扩展,掌握

    2024年02月03日
    浏览(43)
  • 【数据结构】- 排序(详细介绍几种排序算法!!!*直接插入排序,*希尔排序,*选择排序,*堆排序,*冒泡排序,*快速排序,*归并排序)

    排序无处不在,所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 内部排序 :数据元素全部放在内存中的排序。 外部排序 :数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。 今天

    2024年01月20日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包