当前位置: 首页 > news >正文

数据结构-基数排序

基数排序

基本思想

基数排序其实就是依靠多位关键字进行排序,现在我们有一个数据为101,那么“101”就是一个三位

关键字,分别为:“百位->1”、“十位->0”、“个位->1”。

此时我们就可以按照三位关键字进行排序,一般而言,排序有:“最高位优先(MSD)”、“

低位优先(LSD)”。

名词概念

基数

还是对于上面的数据101,它是一个三位关键字,分别为:“1”、“0”、“1”,对于每一位关键字,它

的取值范围为:“0->9”,共十种可能,我们把这些可能性称为:“基数”(简写为r),因此可以说,

101基数为10(r=10)。

关键字位数

仍然对于数据101来说,共有三位,因此它的关键字位数就是三位,分别为:“百位”、“十位”、“个

位”。

代码思路

基数排序精髓在于:“分配”、“收集”

每次按关键字进行分配,当前趟数的关键字相同的数据分配到一个队列中

每次分配完毕后,都需要将不同队列的数据连接在一起,形成一个新的链表。

我们需要使用链式结构来存储数据,同时创建r(基数)个队列,用来辅助存储我们交换中的数

据。

代码实现

#include<stdio.h>
#include<math.h>
#define MAX_KEY 8	//关键字最大位数 
#define RADIX 10	//关键字基数 
#define MAX_SPACE 100	//数据单元大小
typedef struct{int keys;	//关键字 int next;	//下一个数据位置 
}SLnode;	//静态链表单元 
typedef struct{SLnode R[MAX_SPACE+1];	//R[0]做哨兵单元 int length;		//静态链表中数据长度 int keynum;		//关键字位数 
}SLList;
typedef int Queue[RADIX];	//静态队列void InitMySLList(SLList *L)
{int Sample_Data[10] = {614,738,921,485,637,101,215,530,790,306};int i;L->length = 10;		//链表长度 L->keynum = 3;		//关键字位数for(i=1;i<=L->length;i++){L->R[i].keys = Sample_Data[i-1];	//初始化数据 }for(i=0;i<L->length;i++){L->R[i].next = i + 1;		//修改next域,组建成一个静态链表. } L->R[L->length].next = 0;		//尾结点指向0 
}int GetKey(int n,int i)		//求第i位关键字,n为数据 
{int k;k = ((int)(n / pow(RADIX,i))) % RADIX;return k;	
}void Distribute(SLList *L,int i,Queue f,Queue e)		//第i趟分配函数 
{//静态链表中的0->i-1位关键字已经有序//队列中存储的是数据在静态链表中的位置(索引)//实现按第i位关键字有序,建立RADIX个队列.//f,e分别代表队头指针和队尾指针int j,p;for(j=0;j<RADIX;j++){		//初始化队列 f[j] = 0;e[j] = 0;}for(p=L->R[0].next;p;p=L->R[p].next){j = GetKey(L->R[p].keys,i);		//求第i位关键字 if(f[j] == 0)		//队列为空时,直接从队头入第一个数据 f[j] = p;else		//队列不为空,需要从队尾入数据,也就是队列中最后一个元素的next域 L->R[e[j]].next = p;e[j] = p;		//队尾指针存储队列中的最后一个数据. }	
}void Collections(SLList *L,int i,Queue f,Queue e)		//第i趟收集
{int j,t;for(j=0;f[j]==0;j++);	//找到第一个非空队列L->R[0].next = f[j];	//R[0].next	指向第一个非空队列队头t = e[j];		//t指向第一个非空队列队尾while(j<RADIX){for(j++;j<RADIX-1&&!f[j];j++);if(f[j] && j<RADIX){	//j<RADIX不能漏 L->R[t].next = f[j];		//当前队尾和下一个队头相连接 t = e[j];		//t存储最新队列的队尾 }}L->R[t].next = 0;		//队尾指向0 
}void RaDixSort(SLList *L)		//基数排序 
{Queue f,e;int i;for(i=0;i<L->keynum;i++){Distribute(L,i,f,e);Collections(L,i,f,e);}
}void OutPutMyRadix(SLList *L)	//打印结果
{int i;for(i=L->R[0].next;i;i=L->R[i].next){printf("%d ",L->R[i].keys);} 
} int main()
{SLList L;InitMySLList(&L);RaDixSort(&L);OutPutMyRadix(&L);return 0;
}

相关文章:

数据结构-基数排序

基数排序 基本思想 基数排序其实就是依靠多位关键字进行排序&#xff0c;现在我们有一个数据为101&#xff0c;那么“101”就是一个三位 关键字&#xff0c;分别为&#xff1a;“百位->1”、“十位->0”、“个位->1”。 此时我们就可以按照三位关键字进行排序&…...

基于ASP.NET MVC技术的图书管理系统的设计与实现

基于ASP.NET MVC技术的图书管理系统的设计与实现 摘要&#xff1a;图书管理系统是一套高新科学技术和图书知识信息以及传统历史文化完美结合的体现。它改变了传统图书收藏的静态书本式图书服务特征&#xff0c;实现了多媒体存取、远程网络传输、智能化检索、跨库无缝链接、创造…...

C++17中的结构化绑定

C17中的结构化绑定(structured binding):将指定名称绑定到初始化程序的子对象或元素。简而言之&#xff0c;它们使我们能够从元组或结构中声明多个变量。与引用一样&#xff0c;结构化绑定是现有对象的别名&#xff1b;与引用不同&#xff0c;结构化绑定不必是引用类型(referen…...

Mover Creator 用户界面

1 “开始”对话框 首次打开 Mover Creator 时&#xff0c;出现的第一个页面是“开始”对话框&#xff0c;如下所示。从这里开始&#xff0c;用户可以选择开始设计飞机、武器或发动机。在上述每种情况下&#xff0c;用户都可以创建新模型或编辑现有模型。 1.1 新建模型 如果用…...

『Nginx安全访问控制』利用Nginx实现账号密码认证登录的最佳实践

&#x1f4e3;读完这篇文章里你能收获到 如何创建用户账号和密码文件&#xff0c;并生成加密密码配置Nginx的认证模块&#xff0c;实现基于账号密码的登录验证 文章目录 一、创建账号密码文件1. 安装htpasswd工具1.1 CentOS1.2 Ubuntu 二、配置Nginx三、重启Nginx 在Web应用程…...

MongoDB导入导出命令

&#xff08;1&#xff09;mongoexport命令 例如&#xff1a; mongoexport --db testdb --collection person --out person.json mongoexport --db testdb --collection person --fields name,age --out person.json mongoexport --db testdb --collection person --query {&qu…...

软件工程期末复习(1)

学习资料 软件工程知识点总结_嘤桃子的博客-CSDN博客 软件工程学习笔记_软件工程导论第六版张海藩pdf-CSDN博客 【软件工程】软件工程期末试卷习题课讲解&#xff01;&#xff01;_哔哩哔哩_bilibili 【拯救者】软件工程速成(期末考研复试软考)均适用. 支持4K_哔哩哔哩_bil…...

nextjs入门

创建项目 npx create-next-app 项目名 体验文件路由 nextjs提供了文件路由的功能, 根据文件系统的目录结构, 可以识别为对应的页面路由 创建页面 首先, 在src下创建pages目录, 然后创建一个about文件(对应about页面)和main/index.js文件(对应首页) pages/main/index con…...

【C语言】字符串函数strlen #strcpy #strcmp #strcat #strstr及其模拟实现

在C语言中&#xff0c;有一种特殊的数据类型&#xff0c;即字符串类型。C 并没有专门定义一个字符串类型&#xff0c;这对我们使用字符串造成了一定的麻烦。但是&#xff0c;C标准库<string.h> 中定义了各种字符串函数&#xff0c;这对于我们来说是一件值得庆幸的事情。…...

递归实现组合型枚举

递归实现组合型枚举 #include<iostream> #include<vector>int n, m; std::vector<int>res; bool st[30];void Print() {for(int i0;i<res.size();i){printf("%d ",res[i]);}puts(""); }void dfs(int num) {if (res.size() m){Print(…...

SCAU:1065 数组中的指针

1065 数组中的指针 时间限制:1000MS 代码长度限制:10KB 提交次数:3436 通过次数:1692 题型: 编程题 语言: G;GCC Description 设有如下数组定义&#xff1a; int a[3][4]{{1,3,5,7},{9,11,13,15},{17,19,21,23}}; 计算下面各项的值&#xff08;设数组a的首地址为2000&…...

找不到msvcp110.dll如何修复?分享5个亲测有效的修复方法

在计算机使用过程中&#xff0c;我们经常会遇到一些错误提示&#xff0c;其中之一就是“msvcp110.dll丢失”。这个错误通常发生在运行某些程序时&#xff0c;系统无法找到所需的动态链接库文件。那么&#xff0c;msvcp110.dll到底是什么呢&#xff1f;它又有什么作用&#xff1…...

LeetCode刷题笔记第80题:删除有序数组中的重复项 II

LeetCode刷题笔记第80题&#xff1a;删除有序数组中的重复项 II 题目&#xff1a; 删除升序数组中超过两次的元素后的数组长度 想法&#xff1a; 使用快慢指针的方法完成&#xff0c;使用快指针遍历整个数组&#xff0c;使用慢指针完成相同元素最多保留两个。在快指针遍历到…...

【开源存储】minio对象存储部署实践

文章目录 一、前言1、介绍说明2、部署方式3、冗余模式4、约束限制4.1、规格参数4.2、API支持a、minio不支持的Amazon S3 Bucket APIb、minio不支持的Amazon S3 Object API 二、部署说明1、软件安装2、minio单机部署3、minio分布式部署3.1、前置条件3.2、开始运行3.3、操作说明 …...

Java编程强化练习(二)

表达式计算&#xff08;支持空格&#xff0c;连乘&#xff0c;连除&#xff09;&#xff08;选做题&#xff0c;不计分&#xff09; 【问题描述】 从标准输入中读入一个整数算术运算表达式&#xff0c;如5 - 1 * 2 * 3 12 / 2 / 2 。计算表达式结果&#xff0c;并输出。 …...

Redis的高可用模式

1. 什么是高可用&#xff1f; 高可用&#xff08;High Availability, HA&#xff09;是指在信息技术中确保系统、服务或应用程序在绝大多数时间内都是可操作和可访问的能力。这通常涉及以下几个关键方面&#xff1a; 最小化停机时间: 高可用系统的目标是减少因硬件故障、系统升…...

非功能关键知识总结(一)

文章目录 一、稳定性(一)、服务级别协议1、SLA2、OLA3、UC (二)、可用性指标(三)、突发事件等级 三、质量(一)、千行代码缺陷数量(二)、软件质量模型的发展(三)、产品质量模型 四、安全(一)、网络安全 五、灾备(一)、灾备指标(二)、灾难恢复等级(三)、容灾技术分类 一、稳定性 …...

时间序列趋势检验相关检验方法:斜率法、Cox-Stuart检验、Mann-Kendall检验

文章目录 1.斜率法1.1.原理1.2.优缺点1.3.Python代码2.Cox-Stuart检验2.1.原理2.2.优缺点2.3.Python代码3.Mann-Kendall 检验3.1.原理3.1.1.假设前提3.1.2.趋势检验3.1.3.S到Z的变换原理3.1.4.Var(s)是如何得到的3.1.5.衡量趋势的指标:倾斜度...

Redis相关知识

yum安装redis 使用以下命令&#xff1a;直接将redis安装到Linux服务器&#xff08;Xshell&#xff09;中 yum -y install redis 启动redis 使用以下命令&#xff0c;以后台运行方式启动redis redis-server /etc/redis.conf & 操作redis 使用以下命令启动redis客户端 redis-…...

数据管理系统-week10-自由访问控制

文章目录 前言一、用户管理用户管理语句介绍二、数据库管理三、特权(重点考点)Administrative (global) privileges数据库特权表权限列权限四、角色参考文献前言 这节课主要讲了用户管理数据库的具体语句,数据库特权当中的全局特权,数据库特权,表特权与列特权的使用与注意…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

Qt 事件处理中 return 的深入解析

Qt 事件处理中 return 的深入解析 在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别&#xff1a;不同层级的事件处理 方…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...