【数据结构】归并排序、基数排序算法的学习知识点总结
目录
1、归并排序
1.1 算法思想
1.2 代码实现
1.3 例题分析
2、基数排序
2.1 算法思想
2.2 代码实现
2.3 例题分析
1、归并排序
1.1 算法思想
归并排序是一种采用分治思想的经典排序算法,通过将待排序数组分成若干个子序列,将每个子序列排序,最终合并成一个有序序列。其基本思路可以归纳为以下三个步骤:
- 分治:将待排序数组递归地分成两个子序列,直到每个子序列中只有一个元素;
- 合并:将两个有序子序列合并成一个有序序列,直到合并成一个完整的有序序列;
- 递归:重复以上两个步骤,直到排序完成。
具体实现过程中,可以采取自上而下或自下而上的方式进行归并排序。其中,自下而上的归并排序首先将整个数组划分成若干个大小为1的子数组,然后将相邻两个子数组合并成一个有序数组,逐渐扩大有序数组的长度,直到整个数组有序。
归并排序算法的时间复杂度为 O(nlogn),具有稳定性,适用于对大规模数据进行排序。
1.2 代码实现
归并排序(Merge Sort)是一种分治思想的排序算法,它的核心思想是将待排序的序列分成若干子序列,分别排序,然后合并。
C语言实现归并排序的代码如下:
#include <stdio.h>
#include <stdlib.h>void merge(int arr[], int l, int m, int r) {int i, j, k;int n1 = m - l + 1;int n2 = r - m;// 创建左右子数组int L[n1], R[n2];// 将数据复制到左右子数组中for (i = 0; i < n1; i++) {L[i] = arr[l + i];}for (j = 0; j < n2; j++) {R[j] = arr[m + 1 + j];}// 将左右子数组合并到 arr 中i = 0;j = 0;k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 处理剩余元素while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}
}void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l) / 2;// 分别对左右子数组进行排序mergeSort(arr, l, m);mergeSort(arr, m + 1, r);// 将左右子数组合并merge(arr, l, m, r);}
}int main() {int arr[] = {5, 1, 4, 2, 8, 0, 2};int n = sizeof(arr) / sizeof(arr[0]);printf("Original array: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}// 执行归并排序mergeSort(arr, 0, n - 1);printf("\nSorted array: \n");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}return 0;
}
在这段代码中,merge()
函数用于合并左右子数组,mergeSort()
函数用于对左右子数组进行排序并合并。在 main()
函数中,我们创建了一个待排序的整数数组,然后调用 mergeSort()
函数对其进行排序,并输出排序后的结果。
1.3 例题分析
假设我们有一个无序数组[10, 5, 2, 7, 6, 4, 3, 8, 9, 1],要使用归并排序对其进行排序。下面是具体步骤:
1. 首先将数组不断分成两半,直到每个子数组只有一个元素为止。
[10, 5, 2, 7, 6, 4, 3, 8, 9, 1] -> [10, 5, 2, 7, 6] [4, 3, 8, 9, 1] -> [10, 5] [2, 7, 6] [4, 3] [8, 9, 1] -> [10] [5] [2] [7] [6] [4] [3] [8] [9] [1]
2. 接着,将相邻的两个子数组合并,并按顺序排序。
[10] [5] -> [5, 10]
[2] [7] [6] -> [2, 6, 7]
[4] [3] -> [3, 4]
[8] [9] [1] -> [1, 8, 9]
3. 重复步骤2,直到最终将所有子数组合并成为一个有序数组。
[5, 10] [2, 6, 7] [3, 4] [1, 8, 9] -> [2, 3, 4, 5, 6, 7, 8, 9, 10]
4. 最终得到的有序数组为[2, 3, 4, 5, 6, 7, 8, 9, 10]。可以看出,归并排序的时间复杂度为O(nlogn),且不会破坏原有数组的顺序。
2、基数排序
2.1 算法思想
基数排序是一种非比较排序算法,根据关键字的每一位来排序,最终得到有序序列。其基本思想是将待排序的元素按照其每一位的值,将其分配到对应的桶中,然后按照桶的顺序依次取出元素,即可得到有序序列。
具体实现步骤如下:
-
将所有待排序数按照个位数的值依次放入相应的桶中。
-
按照桶的顺序依次取出每个桶中的元素,将其按照一位数的大小依次放回原数组中。
-
对于十位数、百位数等同理,直到最高位数。
-
最终得到有序序列。
需要注意的是,基数排序算法的空间复杂度较高,需要额外的空间来存储桶和中间结果。在实际应用中,需要权衡算法的时间复杂度和空间复杂度,选择合适的算法。
2.2 代码实现
以下是一个基数排序的实现,它将一组数字按位数从低到高排序,每次排序都利用计数排序算法进行。
#include <iostream>
#include <vector>using namespace std;// 计数排序算法,用于将整数数组按某一位进行排序
void countingSort(vector<int>& arr, int exp)
{vector<int> output(arr.size());vector<int> count(10, 0);// 统计每个数字出现的次数for (int i = 0; i < arr.size(); i++)count[(arr[i] / exp) % 10]++;// 累加计数数组,求出每个数字在排序后的数组中的位置for (int i = 1; i < 10; i++)count[i] += count[i - 1];// 根据计数数组中的位置,将数字放置到排序后的数组中for (int i = arr.size() - 1; i >= 0; i--){output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}// 将排序后的数组复制到原始数组中for (int i = 0; i < arr.size(); i++)arr[i] = output[i];
}// 基数排序算法
void radixSort(vector<int>& arr)
{int max = *max_element(arr.begin(), arr.end());// 从低位到高位依次进行排序for (int exp = 1; max / exp > 0; exp *= 10)countingSort(arr, exp);
}int main()
{vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };radixSort(arr);for (int i = 0; i < arr.size(); i++)cout << arr[i] << " ";return 0;
}
2.3 例题分析
基数排序是一种非比较排序算法,其基本思想是将待排序的数据按照位数划分为不同的数字位,然后依次对每一位进行排序。
例如,对于一个无序数组[753, 584, 626, 901, 321],经过一轮排序后,按照个位数字的大小,可以得到以下排列:[901, 321, 753, 584, 626],此时数组已经按照个位数字排好序了。
接下来,我们再按照十位数字的大小对这个序列进行排序,排完之后得到的序列为:[321, 584, 626, 901, 753]。
最后,再按照百位数字的大小进行排序就可以得到最终的有序数组:[321, 584, 626, 753, 901]。
基数排序的时间复杂度是O(d*(n+k)),其中d为位数,n为元素个数,k为数字范围。因此,当数字范围较小且位数不多时,基数排序的效率较高,但如果数字范围很大或者位数较多时,基数排序的效率就会下降。
相关文章:

【数据结构】归并排序、基数排序算法的学习知识点总结
目录 1、归并排序 1.1 算法思想 1.2 代码实现 1.3 例题分析 2、基数排序 2.1 算法思想 2.2 代码实现 2.3 例题分析 1、归并排序 1.1 算法思想 归并排序是一种采用分治思想的经典排序算法,通过将待排序数组分成若干个子序列,将每个子序列排序ÿ…...

【C++】C++模板进阶 —— 非类型模板参数、模板的特化以及模板的分离编译
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:C学习 🎯长路漫漫浩浩,万事皆有期待 上一篇博客:【C】C多…...

HTML的相关知识
1.什么是HTML?基本语法 HTML: Hyper Text Markup Language (超文本标记语言) 超文本?超级文本,例如流媒体,声音、视频、图片等。 标记语言?这种语言是由大量的标签组成。HTML标签参考手…...

基于微信小程的流浪动物领养小程序设计与实现(源码+lw+部署文档+讲解等)
文章目录 前言系统主要功能:具体实现截图论文参考详细视频演示为什么选择我自己的网站自己的小程序(小蔡coding)有保障的售后福利 代码参考源码获取 前言 💗博主介绍:✌全网粉丝10W,CSDN特邀作者、博客专家、CSDN新星计…...

Java后端接口编写流程
💗wei_shuo的个人主页 💫wei_shuo的学习社区 🌐Hello World ! Java后端接口编写流程 Java后端接口编写流程,更具业务逻辑编写Java后端接口,提供给前端访问 实现逻辑流程 POJO:实体类编写 Data B…...

【问题记录】解决“命令行终端”和“Git Bash”操作本地Git仓库时出现 中文乱码 的问题!
环境 Windows 11 家庭中文版git version 2.41.0.windows.1 问题情况 在使用 “命令行终端” 和 “Git Bash” 在本地Git仓库敲击命令时,对中文名称文件显示一连串的数字,如下所示:这种情况通常是由于字符编码设置不正确所引起的 解决办法 设置…...

软考高级之系统架构师之软件需求工程
概述 一个完整的软件生存周期是以需求为出发点。软件需求是指用户对系统在功能、行为、性能、设计约束等方面的期望。 需求开发: 需求获取需求分析需求定义(需求规格说明书)需求验证 需求管理: 变更控制版本控制需求跟踪需求状态跟踪 需…...

使用 Velocity 模板引擎的 Spring Boot 应用
使用 Velocity 模板引擎的 Spring Boot 应用 模板引擎是构建动态内容的重要工具,特别适用于生成HTML、邮件内容、报告和其他文本文档。Velocity是一个强大的模板引擎,它具有简单易用的语法和灵活性。本文将介绍如何在Spring Boot应用中使用Velocity模板…...

mysql的mvcc详解
一 MVCC的作用 1.1 mvcc的作用 1.MVCC(Multiversion Concurrency Control)多版本并发控制。即通过数据行的多个版本管理来实现数据库的并发控制,使得在InnoDB事务隔离级别下执行一致性读操作有了保障。 2.mysql中的InnoDB中实现了MVCC主要…...

FreeRTOS两个死机原因(中断调用接口异常)【杂记】
1、中断回调函数中没有使用中断级API (xxFromISR) 函数 xSemaphoreGiveFromISR(uart_busy,&HighterTask);----正确 xSemaphoreGive(uart_busy);-----错误2、比configMAX_SYSCALL_INTERRUPT_PRIORITY优先级高的中断函数中使用了FreeRTOS的函数 3、临界代码保护后不可调用os…...

【AI视野·今日Robot 机器人论文速览 第四十三期】Thu, 28 Sep 2023
AI视野今日CS.Robotics 机器人学论文速览 Thu, 28 Sep 2023 Totally 37 papers 👉上期速览✈更多精彩请移步主页 Interesting: 📚****触觉力控学习策略,基于触觉的主动推理与力控用于小孔插入任务。提出了姿态控制与插入控制双策略模型。 (from 东京大学…...

批量快捷创建新数组的几种方式
1. for循环, push(比较简单, 就不上代码了) 2.创建空数组,填充null,然后map: function createData() { return new Array(1000) .fill(null) .map((v,i)>({name: name${i1}})) } console.log(createData()) 3.Array.frommap function createData() { return Array.from…...

单目标应用:基于沙丁鱼优化算法(Sardine optimization algorithm,SOA)的微电网优化调度MATLAB
一、沙丁鱼优化算法 沙丁鱼优化算法(Sardine optimization algorithm,SOA)由Zhang HongGuang等人于2023年提出,该算法模拟沙丁鱼的生存策略,具有搜索能力强,求解精度高等特点。 沙丁鱼主要以浮游生物为食,这些生物包括细菌、腔肠…...
基于Halo搭建个人博客
准备 云服务器 安装Docker 开启8090端口 步骤 拉取Halo镜像 docker pull halohub/halo:2.1.0 制作容器并启动 docker run -it -d --name halo -p 8090:8090 -v ~/.halo2:/root/.halo2 halohub/halo:2.1.0 --halo.external-urlhttp://服务器ip:8090/ --halo.security.in…...
DPDK系列之三十一DPDK的并行机制简介
一、并行机制 什么是并行机制?这个很多开发者的眼中,其实是模糊的。可能说起来头头是道,但是细一查究竟,发现都是飘在空中的东西。在前面的“多核和多CPU编程”中,对并行机制已经进行了较深入的分析,这里只…...

【Java】复制数组的四种方式
1. System.arraycopy() 用来将一个数组的(一部分)内容复制到另一个数组里面去。 定义: void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);例: int[] arr1 { 1, 2, 3, 4, 5 }; int[] arr2 new…...

设计模式5、原型模式 Prototype
解释说明:使用原型实例指定待创建对象的类型,并且通过复制这个原型阿里创建型的对象 UML 结构图: 抽象原型(Prototype):规定了具体原型对象必须实现的clone()方法 具体原型(ConcretePrototype&…...
驱动挂载物理页代码示例
驱动挂载物理页代码示例 使用的实验环境为32位xp系统在101012分页模式下 此实验用于测试对分页模式的掌握程度 代码思路如下: 获取目标进程的cr3在目标进程中申请新的物理页拆分新申请的物理页的线性地址通过差分出的内容获取pte将pte写入到要挂载的线性地址的p…...

【新版】系统架构设计师 - 层次式架构设计理论与实践
个人总结,仅供参考,欢迎加好友一起讨论 文章目录 架构 - 层次式架构设计理论与实践考点摘要层次式体系结构概述表现层框架设计MVC模式MVP模式MVVM模式使用XML设计表现层表现层中UIP设计思想 中间层架构设计业务逻辑层工作流设计业务逻辑层设计 数据访问层…...

大数据Flink(九十):Lookup Join(维表 Join)
文章目录 Lookup Join(维表 Join) Lookup Join(维表 Join) Lookup Join 定义(支持 Batch\Streaming):Lookup Join 其实就是维表 Join,比如拿离线数仓来说,常常会有用户画像,设备画像等数据,而对应到实时数仓场景中,这种实时获取外部缓存的 Join 就叫做维表 Join。…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...

C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...