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

C#排序算法新境界:深度剖析与高效实现基数排序

基数排序(Radix Sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数进行比较。具体来说,基数排序有两种方法:

  1. 最低位优先(LSD, Least Significant Digit first):从最低位开始,向最高位进行排序。
  2. 最高位优先(MSD, Most Significant Digit first):通常用于字符串的排序,从最高位开始,向最低位进行排序,且常使用递归实现。

在这里,我们将以最低位优先(LSD)的方式实现一个针对非负整数的基数排序。为了简化,我们假设所有整数都是非负的,并且它们的位数都是相同的(或者我们可以对它们进行补零以使得位数相同)。

以下是基数排序的C#实现:

using System;
using System.Collections.Generic;class Program
{static void Main(string[] args){int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };// 调用基数排序RadixSort(arr);
​Console.WriteLine("Sorted array: ");foreach (int num in arr){Console.Write(num + " ");}Console.WriteLine();}// 基数排序方法static void RadixSort(int[] arr){// 找到数组中的最大值以确定最大位数int max = arr[0];for (int i = 1; i < arr.Length; i++){if (arr[i] > max)max = arr[i];}// 对每个位数进行排序for (int exp = 1; max / exp > 0; exp *= 10){CountingSortForRadix(arr, exp);}}// 基数排序中的计数排序,用于按当前位数排序static void CountingSortForRadix(int[] arr, int exp){int n = arr.Length;int[] output = new int[n]; // 输出数组    int[] count = new int[10]; // 计数数组,0-9// 存储当前位的值for (var i = 0; i < n; i++)count[(arr[i] / exp) % 10]++;// 更改count[i],使其包含实际的位置信息for (var i = 1; i < 10; i++)count[i] += count[i - 1];// 构建输出数组for (var i = n - 1; i >= 0; i--){output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}// 将排序后的数据复制回原数组for (var i = 0; i < n; i++)arr[i] = output[i];}
}

在这个实现中,RadixSort 方法首先找到数组中的最大值,以确定需要处理的最大位数。然后,它使用一个循环,每次循环对当前位(从最低位开始)进行排序。

CountingSortForRadix 方法是一个辅助方法,它使用计数排序来对数组中的元素按当前位进行排序。这个方法首先计算每个数字在当前位上的值(通过除以当前位的位权并取模10得到),然后使用一个计数数组来记录每个值出现的次数。接下来,它修改计数数组,使得每个位置包含小于或等于当前值的元素应该占据的位置。最后,它使用这些信息来构建排序后的数组,并将其复制回原数组。

注意,这个实现假设了所有数字都是非负的,并且它们的位数可能不同(通过最高位之前的0来隐含地表示较短的数字)。如果输入包含负数,或者你需要对字符串进行排序,你可能需要修改这个算法以适应这些情况。

相关文章:

C#排序算法新境界:深度剖析与高效实现基数排序

基数排序&#xff08;Radix Sort&#xff09;是一种非比较型整数排序算法&#xff0c;其原理是将整数按位数切割成不同的数字&#xff0c;然后按每个位数进行比较。具体来说&#xff0c;基数排序有两种方法&#xff1a; 最低位优先&#xff08;LSD, Least Significant Digit f…...

玩机搞机-----如何简单的使用ADB指令来卸载和冻结系统应用 无需root权限 详细操作图示教程

同类博文&#xff1a; 玩机搞机---卸载内置软件 无root权限卸载不需要的软件 安全卸载_无需root卸载彻底内置软件-CSDN博客 在很多时候我们需要卸载一些系统级的app。但如果直接手机端进行卸载的话。是无法正常卸载的。其实我们可以通过有些成品工具或者完全靠ADB指令来进行卸…...

如何通过 Apache Camel 将数据导入 Elasticsearch

作者&#xff1a;来自 Elastic Andre Luiz 使用 Apache Camel 将数据提取到 Elasticsearch 的过程将搜索引擎的稳健性与集成框架的灵活性相结合。在本文中&#xff0c;我们将探讨 Apache Camel 如何简化和优化将数据提取到 Elasticsearch。为了说明此功能&#xff0c;我们将实…...

打造民国风格炫酷个人网页:用HTML和CSS3传递民国风韵

附源码&#xff01;&#xff01;&#xff01; 感谢支持 小弟不断创作网站demo感兴趣的可以关注支持一下 对了 俺在结尾带上了自己用的 背景 大家可以尝试换一下效果更好哦~~~ 如何创建一个民国风格的炫酷网页 在这篇博客中&#xff0c;我们将展示如何制作一个结合民国风格和…...

豆包MarsCode编程助手:产品功能解析与应用场景探索!

随着现代技术的不断进化升级&#xff0c;人工智能正在逐步改变着我们的日常工作方式。特别是对于复杂的项目&#xff0c;代码编写、优化、调试、测试等环节充满挑战。为了简化这些环节、提高开发效率&#xff0c;许多智能编程工具应运而生&#xff0c;豆包MarsCode 编程助手就是…...

爬虫全网抓取

爬虫全网抓取是指利用网络爬虫技术&#xff0c;通过自动化的方式遍历互联网上各个网站、论坛、博客等&#xff0c;从这些网页中提取所需的数据。它通常涉及以下几个步骤&#xff1a; 目标设定&#xff1a;确定要抓取哪些类型的网页内容&#xff0c;比如新闻、商品信息、用户评论…...

【计算机组成原理】详细解读带符号整数在计算机中的运算

有符号整数的运算 导读一、补码的优势二、补码的加法运算三、补码的减法运算四、原码、反码、补码的特性结语 导读 大家好&#xff0c;很高兴又和大家见面啦&#xff01;&#xff01;&#xff01; 经过前面的介绍&#xff0c;我们已经初步认识了有符号整数的三种表示形式&…...

vue3常见的bug 修复bug

Vue 3 作为 Vue.js 的最新版本&#xff0c;在性能、开发体验以及代码可维护性等方面带来了显著的提升。然而&#xff0c;就像任何软件框架一样&#xff0c;Vue 3 在使用过程中也可能遇到一些典型的bug或问题。以下是一些可能遇到的典型问题&#xff1a; 响应式系统相关的问题&…...

C++课程笔记 类和对象

类概念 结构体&#xff1a;只要属性 类&#xff1a;有属性也有方法 c可以省略struct c不行 #include<iostream> using namespace std;typedef struct queue1 {int a;queue1 q() {queue1 q(2);return q;};queue1(){}queue1(int qa){a qa;} }q1; int main() {queue1 Q1;…...

提问即创作:用Prompt提示词引领AI灵感爆发

文章目录 &#x1f34a;AI内容创作的精髓&#xff1a;提示词Prompt1 什么是提示词工程?1.1 提示词是如何影响AI的输出结果?1.2 提示词的原理是什么1.3 提示词工程师的前景1.4 谁能成为提示词工程师&#xff1f;1.5 提示词的未来前景 2 提示词的基本书写技巧3 常见的提示词框架…...

一码空传临时网盘PHP源码,支持提取码功能

源码介绍 一码空传临时网盘源码V2.0免费授权&#xff0c;该源码提供了一个简单易用的无数据库版临时网盘解决方案。前端采用了layui开发框架&#xff0c;后端使用原生PHP编写&#xff0c;没有引入任何开发框架&#xff0c;保持了代码的简洁和高效。 这个程序使用了一个无数据…...

自然语言处理实战项目

自然语言处理实战项目 自然语言处理&#xff08;NLP, Natural Language Processing&#xff09;是人工智能的重要分支之一&#xff0c;致力于让计算机理解、生成并与人类进行语言交互。随着深度学习、神经网络和大数据的发展&#xff0c;NLP技术在近年来取得了飞跃性的进展&am…...

人工智能物联网的去中心化和分布式学习:全面综述、新兴挑战和机遇

这篇论文的标题是《Decentralized and Distributed Learning for AIoT: A Comprehensive Review, Emerging Challenges, and Opportunities》&#xff0c;作者是Hanyue Xu, Kah Phooi Seng, Li Minn Ang, 和 Jeremy Smith。论文发表在IEEE Access期刊上&#xff0c;接收日期为2…...

滑动窗口算法—最小覆盖子串

题目 ”最小覆盖子串“问题&#xff0c;难度为Hard&#xff0c;题目如下&#xff1a; 给你两个字符串 S 和 T&#xff0c;请你在 S 中找到包含 T 中全部字母的最短子串。如果 S 中没有这样一个子串&#xff0c;则算法返回空串&#xff0c;如果存在这样一个子串&#xff0c;则可…...

应用案例|开源 PolarDB-X 在互联网安全场景的应用实践

背景介绍 中盾数科集团始创于2012年&#xff0c;是由网络安全服务而发展起来的科技型、多元化的企业集团。旗下包括网络安全服务、信创一体化服务、箱式液冷、区块链、位置服务、视觉服务等六大板块&#xff0c;业务覆盖湖南、甘肃、贵州等多个省份。 业务挑战 中盾集团基于A…...

【大数据】MapReduce的“内存增强版”——Spark

【大数据】MapReduce的“内存增强版”——Spark 文章脉络 Spark架构 Spark-core SparkConf 和 SparkContext RDD Spark集群 Spark-sql 在大数据时代&#xff0c;数据处理和分析成为企业竞争的重要手段。Hadoop作为大数据处理的基石&#xff0c;其核心组件MapReduce在众多…...

o1模型:引领AI技术在STEM领域的突破与应用

o1模型是OpenAI最新推出的大型语言模型&#xff0c;它在多个领域展现出了卓越的能力&#xff0c;被认为是AI技术发展的一个重要里程碑。以下是对o1模型的详细介绍和分析&#xff1a; o1模型的简介和性能评估 o1模型在物理、化学、生物学等领域的基准任务上达到了博士生水平&…...

数据库系统 第57节 数据库迁移

数据库迁移是一个复杂的过程&#xff0c;涉及到将数据从一个数据库系统转移到另一个数据库系统。这个过程通常需要仔细规划和执行&#xff0c;以确保数据的完整性和可用性。以下是数据库迁移的一些关键方面&#xff1a; 数据迁移工具&#xff1a; 这些工具可以帮助自动化迁移过…...

【主机入侵检测】Wazuh规则详解

前言 Wazuh 规则是一组用XML格式编写的条件&#xff0c;它们定义了应该如何解释日志数据。这些规则由Wazuh Manager使用&#xff0c;用于在日志消息中检测特定的模式或行为&#xff0c;并相应地生成警报或响应。它们在威胁检测中扮演着至关重要的角色&#xff0c;因为它们允许系…...

redis有序集合写入和求交集的速度

背景 团队小伙伴做了一个需求。大概的需求是有很多的图片作品&#xff0c;图片作品有一些类别&#xff0c;每个人进入到每个类别的作品业&#xff0c;根据权重优先查看权重最高的的作品&#xff0c;权重大概是基于每个人对该作品的浏览计算&#xff0c;浏览过的作品放在最后展…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...