程序员经验分享-hwhale

排序算法总结—时间复杂度O(n)—基数排序/计数排序小记

2023-10-27

排序算法总结—时间复杂度O(n)—基数排序

在这里插入图片描述

基数排序

分为最高位优先和最低位优先的算法。
找到最大值max，求出max的位数。在max位数max—length进行循环max-length趟。对于每一位进行排序，对于一个数字要会从低位一位一位取值，合理使用/10，%10。
（对于大于0的数据范围，通常是10位，如果数据中有负数，要取19位。
开辟一个计数数组count，对于出现几次就对应的数字count+1。
count对应的直接就是该数字对应的下标（后序放入数组），当后序放入数组时，我们将同样的数字对应的count值-1，便于存储下一个同样的数字，不会冲突或溢出。
下面有一个前序放入的计数排序代码，count值++操作；

以王道书为主：

  • 时间复杂度 O（d（n+r）） d趟分配和收集，一趟分配O（n），一趟收集O（r）
  • 空间复杂度（书中是采用了r个队列）O（r）
  • 稳定 稳定！老稳了！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

算法leetcode

LeetCode

c语言

数据结构

排序算法总结—时间复杂度O(n)—基数排序/计数排序小记 的相关文章

随机推荐

  • SpringMVC拦截器

    1 拦截器的三个抽象方法 SpringMVC中的拦截器有三个抽象方法 preHandle 控制器方法执行之前执行preHandle 其boolean类型的返回值表示是否拦截或放行 返回true为放行 即调用控制器方法 返回flse表示拦截

  • 【分享】原力计划的初衷 【探讨】新的一年，你对原力计划有哪些期待？

    课前小差 哈喽 大家好 我是几何心凉 这是一份全新的专栏 唯一得倒CSDN王总的授权 来对于我们每周四的绿萝时间 直达CSDN 直播内容进行总结概括 让大家能够省去看直播回放的时间也能够了解直播内容和官方的最新动态 希望大家给予凉哥最大的支

  • 【阿里三面】好险！本以为是场普通的阿里面试，没想到二面就迎来了P9大佬

    前言 阿里 我是在BOSS上投的简历 之前也投过一次 简历都没通过筛选 后来让前辈帮我改了一下简历 重新投另一个部门 获得了面试机会 5月15日 中午HR打电话过来预约了下午4点半面试 说会在线笔试 让我准备好 一面 70分钟 突击电话面试

  • 基于FPGA的正弦波发生器设计与实现

    基于FPGA的正弦波发生器设计与实现 摘要 本文介绍了一种基于FPGA的正弦波发生器的设计与实现 通过使用FPGA的数字信号处理功能 可以实现高精度 高性能的正弦波生成 文章首先介绍了DDS Direct Digital Synthesis

  • 大骗局星钻共享拍卖不为人知的的秘密

    钻石恒久远 一颗永流传 作为当之无愧的宝石之王 钻石从开采到初步打磨再到深层加工最后到售卖 需要经历无数道工序流程 平均每开采一克拉的钻石胚 需要至少处理250吨的矿石 而这一克拉的钻石胚还需要经过切磨雕琢 最后以闪耀动人的钻石成品面世时

  • vue自定义校验规则的动态必填字段

  • 10秒学会codeblocks里批量替换变量名

    10秒学会codeblocks里批量替换变量名 我想把下面代码所有的frontt改成front 应该怎么做呢 typedef struct QueueElementType element MAXSIZE int frontt int re

  • Latex基本使用

    一 文字 加粗 textbf 文字 加颜色 textcolor 颜色 文字 如 textcolor cyan TABLE II 一个单词的首字母下沉占用两行 单词剩余部分大写 IEEEPARstart 单词首字母 单词剩余部分 如 IEEE

  • Linux下的FILE*结构体

    FILE 结构体解析 struct file结构体定义在include Linux fs h中定义 文件结构体代表一个打开的文件 系统中的每个打开的文件在内核空间都有一个关联的 struct file 它由内核在打开文件时创建 并传递给在文

  • 笔记本网络计算机和设备不可见,xp电脑不显示无线网络的七种原因和解决方法...

    xp纯净版系统电脑打开后发现桌面右下角不显示无线网络 如果要设置无线网络都不知道从哪里下手 这到底是怎么回事 造成xp系统不显示无线网络的原因有很多种 下面和大家讲解一下xp电脑不显示无线网络的七种原因和解决方法 故障原因 一 无线网卡驱动

  • k8s config多集群管理

    k8s config多集群管理 contexts 查看 kubectl config get contexts 创建 kubectl config set context my context 修改 kubectl config set c

  • pycharm整体缩进，整体取消缩进

    整体缩进 tab 整体取消缩进 tab shift

  • [游戏商业化]一些基础概念点，做个记录

    A 商业化业务逻辑 核心 三者之间的关系 产品的最终目标是实现盈利 获取利润 产品的主要目标是发展用户 吸引用户 留下用户 通过投放产品广告为产品带来用户 变现 广告变现 是最简单 最有效且不存在领域限制的变现方式 通过在App上展示广告主

  • 数据结构--- 树

    一 知识补充 定义 树是一种数据结构 它是由n n 0 个有限节点组成一个具有层次关系的集合 把它叫做 树 是因为它看起来像一棵倒挂的树 也就是说它是根朝上 而叶朝下的 它具有以下的特点 每个节点有零个或多个子节点 没有父节点的节点称为根节

  • 独家专访BlockCity区块城市徐志翔：DAO是未来元宇宙的核心

    转载说明 最近随着ChatGPT的出圈 整个AIGC领域倍受关注 唱衰媒体人的声音也开始不绝于耳 但看到这样有质量的长文 我想也不是每个媒体人都将会被AI替代吧 本文来自前瞻 元宇宙观察 专栏记者采访 作者声明分享无版权限制 如下为全文内容

  • 基础算法题 —— 合唱队（最长递增子序列）

    题解 枚举每个位置左右侧分别所能站的做多人 自左向右递增 求每个位置左边最多可站多少人 含自己 dp1 自右向左递增 求每个位置右边最多可站多少人 含自己 dp2 选择第 i 个位置不移动的情况下 合唱队所能站的人数 dp1 i dp2 i

  • 学习文件day20--关于File

    java io File File的每一个实例用于表示硬盘上的一个文件或目录 实际上表示的是一个抽象路径 File可以 1 访问其表示的文件或目录的属性信息 名字 大小 修改时间等 2 操作文件或目录 创建 删除 3 访问一个目录中的所有子

  • Flutter之瀑布流效果——Flutter基础系列

    需求 相信android和ios的瀑布流效果大家都试过 网上有很多实现方法和开源库 今天我来为大家介绍一下如何在Flutter中实现瀑布流 整理一下方便以后学习 顺便分享给大家 一 生成二维码 1 导入依赖 在 pubspec yaml 中

  • R手册(Machine Learning)--mlr (Part 2)

    文章目录 Configuration 配置 Parallelization 并行 Imputation 插补 Feature Extraction 特征提取 1 Feature filtering 特征筛选 2 Feature select

  • 排序算法总结—时间复杂度O(n)—基数排序/计数排序小记

    排序算法总结 时间复杂度O n 基数排序 基数排序 分为最高位优先和最低位优先的算法 找到最大值max 求出max的位数 在max位数max length进行循环max length趟 对于每一位进行排序 对于一个数字要会从低位一位一位取值

热门标签