【八大排序】归并排序 | 计数排序 + 图文详解！！

在这里插入图片描述

📷 江池俊： 个人主页
🔥个人专栏： ✅数据结构冒险记 ✅C语言进阶之路
🌅 有航道的人，再渺小也不会迷途。

在这里插入图片描述

文章目录

    • 一、归并排序
      • 1.1 基本思想 + 动图演示
      • 2.2 递归版本代码实现 + 算法步骤
      • 2.3 非递归版本代码实现 + 算法步骤
      • 2.4 归并排序的特性总结
    • 二、计数排序
      • 2.1 基本思想
      • 2.2 动图演示
      • 2.3 算法步骤
      • 2.4 代码实现
      • 2.5 计数排序特性总结
    • 三、排序算法复杂度及稳定性分析

在这里插入图片描述

一、归并排序

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
  • 自下而上的迭代；

1.1 基本思想 + 动图演示

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。它将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

在这里插入图片描述

在这里插入图片描述

2.2 递归版本代码实现 + 算法步骤

归并排序的基本思想是分治思想，它包括以下三个步骤：

  1. 分解（Divide）：将含有n个元素的序列分成两个各自包含大约n/2个元素的子序列。（当数组分解成一个时即可认为其有序）
  2. 解决（Conquer）：递归地对这两个子序列进行归并排序。
  3. 合并（Combine）：将两个排序好的子序列合并成一个最终的排序序列。

归并排序通过不断地将大问题分解成小问题来解决，即把大的数组拆分成若干个小的数组，然后逐一合并这些有序的小数组来得到最终排序好的整体数组。这种算法非常适用于链表等数据结构，在处理大规模数据时尤其高效。

// 归并排序递归函数
void _MergeSort(int* a, int begin, int end, int* temp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid] [mid+1, end]_MergeSort(a, begin, mid, temp);_MergeSort(a, mid+1, end, temp);// ... 归并 [begin,mid] [mid+1,end]int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){temp[i++] = a[begin1++];}else{temp[i++] = a[begin2++];}}while (begin1 <= end1){temp[i++] = a[begin1++];}while (begin2 <= end2){temp[i++] = a[begin2++];}// 拷贝回原数组memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
}// 归并排序
void MergeSort(int* a, int n)
{// 申请一个与原数组同样大小的空间int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, temp);free(temp);
}

【递归展开图】：
在这里插入图片描述

现在我们来分析一下以上代码：
这段代码是归并排序（Merge Sort）的实现。归并排序是一种分治算法，它将一个数组分成两半，对每一半进行排序，然后将两个有序的部分合并成一个有序的数组。以下是这段代码的算法思想和步骤分析：

  1. 递归划分：

    • 在_MergeSort函数中，首先检查基准条件，即如果begin大于或等于end，则数组已经完全有序，所以直接返回。
    • 然后，计算中间索引mid，将数组分成两个子数组：[begin, mid]和[mid+1, end]。
    • 对这两个子数组递归地进行归并排序。

  2. 合并：

    • 在递归调用返回后，两个子数组都是有序的。然后，将这两个有序的子数组合并成一个有序的数组。
    • 合并操作通过双指针技术完成。指针begin1和begin2分别指向两个子数组的开始位置，而指针end1和end2分别指向两个子数组的结束位置。
    • 开始时，从两个子数组中取最小的元素，放到临时数组temp中，直到其中一个子数组被完全取完。
    • 然后，将剩余的子数组的所有元素复制到临时数组中。

  3. 拷贝回原数组：

    • 最后，使用memcpy函数将临时数组中的元素复制回原数组。这一步是必要的，因为临时数组是在堆上分配的，而原数组是在栈上。

  4. 主函数：

    • MergeSort函数是归并排序的入口点。它首先在堆上为原数组分配一个同样大小的临时数组。如果分配失败（即malloc返回NULL），则输出错误信息并返回。
    • 然后，调用递归函数_MergeSort对原数组进行排序。
    • 最后，释放临时数组以防止内存泄漏。

  5. 稳定性：

    • 归并排序是稳定的排序算法，这意味着相等的元素在排序后保持其原始顺序。这是因为归并排序在合并两个子数组时，总是选择较小的元素，而不改变其相对顺序。

  6. 时间复杂度：

    • 归并排序的时间复杂度为O(nlogn)，其中n是数组的大小。这是因为每次递归调用都会将问题规模减半（logn），并且需要进行n次这样的递归调用（n）。

  7. 空间复杂度：

    • 归并排序的空间复杂度为O(n)，因为需要一个与原数组同样大小的临时数组来存储合并过程中的中间结果。

2.3 非递归版本代码实现 + 算法步骤

// 归并排序（非递归）
void MergeSortNonR(int* a, int n)
{int* temp = (int*)malloc(sizeof(int) * n);if (temp == NULL){perror("malloc fail");return;}int gap = 1; // 通过gap来控制归并的两个区间的大小，表示的是这两个区间的大小while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;// [begin1, end1] [begin2, end2] 归并// 边界处理if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}// 归并int j = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] <= a[begin2]){temp[j++] = a[begin1++];}else{temp[j++] = a[begin2++];}}while (begin1 <= end1){temp[j++] = a[begin1++];}while (begin2 <= end2){temp[j++] = a[begin2++];}// 拷贝回原数组（边归并边拷贝） --- 因为最后可能有一个区间不需要归并，所以这一个区间的元素是不需要改变的，即不需要拷贝回去，若一次性拷贝回原数组，会使这个区间的元素全部变为随机值memcpy(a + i, temp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;}free(temp);
}

对于上述代码我们接着来分析一下它的算法步骤：

【算法步骤】：

  1. 初始化：

    • 定义一个临时数组temp，其大小为输入数组a的大小。
    • 初始化一个变量gap为1，它表示每次归并时每组数据的个数。

  2. 归并循环：

    • 当gap小于输入数组的长度n时，进入循环。
    • 在每次循环中，将数组分为两个子数组（每个子数组的大小为gap），并对这两个子数组进行归并。

  3. 子数组归并：

    • 定义两个子数组的起始和结束索引：begin1到end1和begin2到end2。
    • 处理边界情况：如果其中一个子数组超出数组范围，则退出循环。
    • 使用一个临时数组temp来存储归并的结果。
    • 使用一个双指针方法（类似于两个指针比较和交换）来将两个子数组合并为一个有序数组。

  4. 拷贝回原数组：

    • 使用memcpy函数将临时数组中的数据拷贝回原数组。这一步是为了在归并过程中更新原数组。

  5. 扩大gap：

    • 在每次循环结束时，将gap乘以2，以便在下一次循环中处理更大的子数组。

  6. 释放内存：

    • 归并完成后，释放临时数组temp的内存。

2.4 归并排序的特性总结

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定

二、计数排序

2.1 基本思想

思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中

在这里插入图片描述

2.2 动图演示

在这里插入图片描述

2.3 算法步骤

这段代码是实现计数排序算法的C语言代码。以下是该代码的算法步骤和思想分析：

算法步骤：

  1. 找出数组中的最小值和最大值：这是计数排序的一个重要步骤，因为算法需要对数组中的每个元素进行计数，所以需要知道元素的可能范围。
  2. 计算范围：根据最小值和最大值计算出元素的可能范围。
  3. 计数：遍历输入数组，对每个元素在其可能的范围内进行计数。
  4. 构建输出数组：根据计数结果，将每个元素放到它在输出数组中的正确位置。

2.4 代码实现

// 计数排序 
// 时间复杂度：O(N+range) 空间复杂度：O(range) 
void CountSort(int* a, int n)
{int min = a[0], max = a[0];for (int i = 1; i < n; i++){if (a[i] < min){min = a[i];}if (a[i] > max){max = a[i];}}int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail");return;}// 统计次数for (int i = 0; i < n; i++){count[a[i] - min]++;}// 排序int i = 0;for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;}}
}

2.5 计数排序特性总结

  1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。数排序适用于整数且范围较小的情况。对于范围较大的整数或小数，需要更复杂的排序算法。
  2. 时间复杂度：O(MAX(N,范围))，由于算法只涉及到一次遍历输入数组和一次遍历计数数组，所以时间复杂度为O(MAX(N,范围))。
  3. 空间复杂度：O(范围)，由于需要创建一个与范围大小相等的计数数组，所以空间复杂度为O(范围)。
  4. 稳定性：稳定（相等的元素在排序后保持其原始顺序）

三、排序算法复杂度及稳定性分析

在这里插入图片描述
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/256369.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

面试经典150题——长度最小的子数组

面试经典150题——长度最小的子数组

​"In the midst of winter, I found there was, within me, an invincible summer." - Albert Camus 1. 题目描述 2. 题目分析与解析 首先理解题意&#xff0c;题目要求我们找到一个长度最小的 连续子数组 满足他们的和大于target&#xff0c;需要返回的是子数组的…
阅读更多...
探索现代Web前端开发框架：选择最适合你的工具

探索现代Web前端开发框架：选择最适合你的工具

在当今快速发展的Web开发领域&#xff0c;前端开发框架的选择显得尤为关键。这些框架可以帮助我们更高效地构建出交互性强、性能卓越的用户界面。本文将带你了解几个当前最受欢迎的Web前端开发框架&#xff0c;并帮助你根据自己的需求选择最合适的工具。 1. React React由Fac…
阅读更多...
K8S之运用节点选择器指定Pod运行的节点

K8S之运用节点选择器指定Pod运行的节点

node节点选择器的使用 使用场景实践使用nodeName使用nodeSelectornodeName和nodeSelector混合使用1、设置了nodeName 和 设置 Node上都不存在的标签。看调度情况2、设置nodeName 为node1 和 设置 node2上才有的标签。看调度情况 实践总结 使用场景 默认情况&#xff0c;在创建…
阅读更多...
故障诊断 | 一文解决，TCN时间卷积神经网络模型的故障诊断（Matlab）

故障诊断 | 一文解决，TCN时间卷积神经网络模型的故障诊断（Matlab）

效果一览 文章概述 故障诊断 | 一文解决，TCN时间卷积神经网络模型的故障诊断（Matlab） 模型描述 时间卷积神经网络（TCN）是一种用于序列数据建模和预测的深度学习模型。它通过卷积操作在时间维度上对序列数据进行特征提取，并且可以处理可变长度的输入序列。 要使用TCN进行…
阅读更多...
vue-组件组成和组件通信（四）

vue-组件组成和组件通信（四）

组件的三大组成部分 (结构/样式/逻辑) scoped样式冲突 默认情况&#xff1a;写在组件中的样式会 全局生效 → 因此很容易造成多个组件之间的样式冲突问题。 1. 全局样式: 默认组件中的样式会作用到全局 2. 局部样式: 可以给组件加上 scoped 属性, 可以让样式只作用于当前组…
阅读更多...
nginx添加lua模块

nginx添加lua模块

目录 已安装了nginx&#xff0c;后追加lua模块nginx 重新编译知识参考&#xff1a; 从零安装一、首先需要安装必要的库&#xff08;pcre、zlib、openssl&#xff09;二、安装LUA环境及相关库 &#xff08;LuaJIT、ngx_devel_kit、lua-nginx-module&#xff09;注意&#xff1a;…
阅读更多...
基于YOLOv8的暗光低光环境下（ExDark数据集）检测，加入多种优化方式---DCNv4结合SPPF ，助力自动驾驶（一）

基于YOLOv8的暗光低光环境下（ExDark数据集）检测，加入多种优化方式---DCNv4结合SPPF ，助力自动驾驶（一）

&#x1f4a1;&#x1f4a1;&#x1f4a1;本文主要内容:详细介绍了暗光低光数据集检测整个过程&#xff0c;从数据集到训练模型到结果可视化分析&#xff0c;以及如何优化提升检测性能。 &#x1f4a1;&#x1f4a1;&#x1f4a1;加入 DCNv4结合SPPF mAP0.5由原始的0.682提升至…
阅读更多...
牛客网SQL进阶114：更新记录

牛客网SQL进阶114：更新记录

官网链接&#xff1a; 更新记录&#xff08;二&#xff09;_牛客题霸_牛客网现有一张试卷作答记录表exam_record&#xff0c;其中包含多年来的用户作答试卷记录&#xff0c;结构如下表。题目来自【牛客题霸】https://www.nowcoder.com/practice/0c2e81c6b62e4a0f848fa7693291d…
阅读更多...
Gitlab和Jenkins集成 实现CI (二)

Gitlab和Jenkins集成 实现CI (二)

Gitlab和Jenkins集成 实现CI (一) Gitlab和Jenkins集成 实现CI (二) Gitlab和Jenkins集成 实现CI (三) 配置Gitlab api token 配置 Gitlab 进入gitlab #mermaid-svg-t84fR8wrT4sB4raQ {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:…
阅读更多...
单例模式：懒汉饿汉线程安全问题

单例模式：懒汉饿汉线程安全问题

在我们前几篇文章中都了解了一些关于线程的知识&#xff0c;那么在多线程的情况下如何创建单例模式&#xff0c;其中的线程安全问题如何解决&#xff1f; 目录 1.什么是单例模式&#xff1f; (饿汉模式) 2.单例模式(懒汉模式) *懒汉模式与懒汉模式的对比 *如何解决懒汉模式…
阅读更多...
【后端高频面试题--SpringBoot篇】

【后端高频面试题--SpringBoot篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;后端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 这里写目录标题 1.什么是SpringBoot&#xff1f;它的主要特点是什么&#xff1f;2.列举一些Spri…
阅读更多...
《剑指 Offer》专项突破 - 面试题 43 : 在完全二叉树中添加节点（两种方法 + C++ 实现）

《剑指 Offer》专项突破 - 面试题 43 : 在完全二叉树中添加节点（两种方法 + C++ 实现）

目录 前言 方法一 方法二 前言 题目链接&#xff1a;LCR 043. 完全二叉树插入器 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 在完全二叉树中&#xff0c;除最后一层之外其他层的节点都是满的&#xff08;第 n 层有 个节点&#xff09;。最后一层的节点可能…
阅读更多...
SQL,HQL刷题,尚硅谷

SQL,HQL刷题,尚硅谷

目录 相关表数据&#xff1a; 题目及思路解析&#xff1a; 汇总分析 1、查询编号为“02”的课程的总成绩 2、查询参加考试的学生个数 分组 1、查询各科成绩最高和最低的分&#xff0c;以如下的形式显示&#xff1a;课程号&#xff0c;最高分&#xff0c;最低分 2、查询每门课程…
阅读更多...
springboot179基于javaweb的流浪宠物管理系统的设计与实现

springboot179基于javaweb的流浪宠物管理系统的设计与实现

简介 【毕设源码推荐 javaweb 项目】基于springbootvue 的 适用于计算机类毕业设计&#xff0c;课程设计参考与学习用途。仅供学习参考&#xff0c; 不得用于商业或者非法用途&#xff0c;否则&#xff0c;一切后果请用户自负。 看运行截图看 第五章 第四章 获取资料方式 **项…
阅读更多...
鸿蒙开发第3篇__大数据量的列表加载性能优化

鸿蒙开发第3篇__大数据量的列表加载性能优化

列表 是最常用到的组件 一 ForEach 渲染控制语法————Foreach Foreach的作用 遍历数组项&#xff0c;并创建相同的布局组件块在组件加载时&#xff0c; 将数组内容数据全部创建对应的组件内容&#xff0c; 渲染到页面上 const swiperImage: Resource[] {$r("app.me…
阅读更多...
类与结构体（6）

类与结构体（6）

我们上一起讲了这一期讲存储类和继承&#xff0c;这个难度很大的。 存储类 存储类主要规定了函数和变量的范围&#xff0c;在c中有这些存储类↓&#xff1a; ৹ auto&#xff08;自动判断函数是什么类型&#xff09; ৹ register (常用的变量和inline差不多&#xff0c;但应…
阅读更多...
Netty应用——通过WebSocket编程实现服务器和客户端长连接（十八）

Netty应用——通过WebSocket编程实现服务器和客户端长连接（十八）

Http协议是无状态的&#xff0c;浏览器和服务器间的请求响应一次&#xff0c;下一次会重新创建连接要求:实现基于webSocket的长连接的全双工的交互改变Http协议多次请求的约束&#xff0c;实现长连接了&#xff0c; 服务器可以发送消息给浏览器客户端浏览器和服务器端会相互感知…
阅读更多...
docker本地目录挂载

docker本地目录挂载

小命令 1、查看容器详情 docker inspect 容器名称 还是以nginx为例&#xff0c;上篇文章我们制作了nginx静态目录的数据卷&#xff0c;此时查看nginx容器时会展示出来&#xff08;docker inspect nginx 展示信息太多&#xff0c;这里只截图数据卷挂载信息&#xff09;&#…
阅读更多...
【附代码】NumPy加速库NumExpr（大数据）

【附代码】NumPy加速库NumExpr（大数据）

文章目录 相关文献测试电脑配置数组加减乘除数组乘方Pandas加减乘除总结 作者&#xff1a;小猪快跑 基础数学&计算数学&#xff0c;从事优化领域5年&#xff0c;主要研究方向&#xff1a;MIP求解器、整数规划、随机规划、智能优化算法 如有错误&#xff0c;欢迎指正。如有…
阅读更多...
CVE-2022-0760 漏洞复现

CVE-2022-0760 漏洞复现

CVE-2022-0760 NSS [HNCTF 2022 WEEK2]ohmywordpress 【CVE-2022-0760】 题目描述&#xff1a;flag在数据库里面。 开题&#xff1a; 顺着按钮一直点下去会发现出现一个按钮叫安装WordPress 安装完之后的界面&#xff0c;有一个搜索框。 F12看看network。 又出现了这个Wor…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发