【数据结构】排序之归并排序与计数排序

个人主页 : zxctsclrjjjcph
文章封面来自:艺术家–贤海林
如有转载请先通知

目录

  • 1. 前言
  • 2. 归并排序
    • 2.1 递归实现
      • 2.1.1 分析
      • 2.1.2 代码实现
    • 2.2 非递归实现
      • 2.2.1 分析
      • 2.2.2 代码实现
  • 3. 计数排序
    • 3.1 分析
    • 3.2 代码实现
  • 4. 附代码
    • 4.1 Sort.h
    • 4.2 Sort.c
    • 4.3 Test.c

1. 前言

在前面的文章中介绍了 插入排序和交换排序,今天来分享的是归并排序和计数排序。
话不多说,正文开始。

2. 归并排序

归并排序既是内排序也是外排序。

基本思想:
归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤:
在这里插入图片描述

在这里插入图片描述
归并排序的特性总结:

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

2.1 递归实现

2.1.1 分析

左边和右边都无序,先分割,8个分为4个,4个分为两个,两个分为1个,一个可以认为它有序了。
在这里插入图片描述
一个和一个归为2个有序,2个和2个归为4个有序,4个4个归为有序。这里用的就是后序递归
用一个临时数组tmp来进行排序后再拷贝回原数组,不可能每次调用数组自己就再开辟一次空间。
在递归的时候必须是一段区间,所以这里重新写一个子函数_MergeSort()来实现递归。
直接分割区间mid = (begin + end) / 2,然后分割左区间再分割右区间,当只有一个值时,已经有序了。
在这里插入图片描述
归并时,将左右区间里面的值进行比较,取小的尾插在tmp临时数组中。一个一个插入,最后肯定还剩下一组,如果剩下第一个区间就直接尾插tmp[i++] = a[begin1++];同样剩下第二个区间也直接尾插tmp[i++] = a[begin2++],最后拷贝回原数组memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1))

2.1.2 代码实现

void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid][mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);// [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]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}

来个例子测试一下。
在这里插入图片描述

2.2 非递归实现

如果用栈模拟实现,是不合适的,栈适合前序遍历,而归并排序是后序遍历。可以在栈里面对区间进行分割,但是栈空了,已经没有区间了,实现不了归并。

2.2.1 分析

归并分割是为了实现有序,直接到过来,一个和一个归并就实现有序。
在这里插入图片描述
同样要先开一个临时数组tmp,先归第一组区间[begin1, end1][begin2, end2]实现归并,谁小谁尾插,归并逻辑和上面递归是一样的。
gap为每一组数据个数,第一个区间就是int begin1 = i, end1 = i + gap - 1;
第二个区间就是int begin2 = i + gap, end2 = i + 2 * gap - 1。(这里算的是下标,所以end得减1)。
在这里插入图片描述
这里实现完一组gap,要实现下一个gap,用一个for 循环实现for(size_t i = 0; i < n; i += 2 * gap)。那么结束条件就是gap > n。
在这里插入图片描述

代码写出来就是

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){printf("gap:%2d->", gap);for (size_t 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] 归并printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);int j = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * 2 * gap);}printf("\n");gap *= 2;}free(tmp);
}

举个例子实现代码,发现结果出不来。为什么呢?
在这里插入图片描述
说明区间越界了,得对区间进行处理。
区间[begin1, end1][begin2, end2]中begin1不存在越界,i是一直小于n。
end1,begin2, end2都会存在越界情况。
对end1如果它大于n,不需要归并了,就直接break;
对begin2如果它大于n,说明第二个区间越界了,也不需要归并,就直接break;
对end2如果它大于n,这里的第二个区间还存在一些值,将区间修改为n-1(end2 = n - 1)。

            if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}

在这里插入图片描述
这里得注意拷贝,在使用memcpy时,归一组就拷贝一组,如果全部归并之后再拷贝,就会出现随机值。
在这里插入图片描述
放在外面,如果后面区间出现越界,直接break,就没有就行归并,它本身就是有序的,会把之前有序的数据覆盖。

2.2.2 代码实现

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){printf("gap:%2d->", gap);for (size_t 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]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}printf("\n");gap *= 2;}free(tmp);
}

举个例子:
在这里插入图片描述

3. 计数排序

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

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

在这里插入图片描述
计数排序的特性总结:

  1. 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
  2. 时间复杂度:O(MAX(N,范围))
  3. 空间复杂度:O(countN范围)
  4. 稳定性:稳定

局限性:

  1. 不适合分散的数据,更适合集中数据;
  2. 不适合浮点数、字符串、结构体数据排序,只适合整数。

3.1 分析

在这里插入图片描述

代码核心就是:
在这里插入图片描述
a[i]是多少就对多少进行计数,出现几次就加几次。
在这里插入图片描述
1这个位置出现3次就在原数组中写3个1,2的位置出现一次就在原数组中写一个2。
在这里插入图片描述
这里不可能每一次都从0开始进行排序,每一次都是几对于几
在这里插入图片描述

如果是这样,那么就浪费了1000个空间。
这里使用相对映射而不是绝对映射。
在这里插入图片描述
找最小值1000,最大值1999。
然后用calloc开一个计数数组,因为calloc会初始化为0。
这里1000就在0的位置,1999就在999的位置。
统计次数:对相对映射位置进计数。

    for (int i = 0; i < n; i++){count[a[i] - min]++;}

这里怎么还原呢?
加回去就行j + min
后置减减,返回的减减之前的值,往回写。

    for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;}}

这里负数也能使用计数排序。
在这里插入图片描述

3.2 代码实现

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){printf("calloc fail\n");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;}}
}

4. 附代码

4.1 Sort.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>void PrintArray(int* a, int n);void MergeSort(int* a, int n);
void MergeSortNonR(int* a, int n);
void CountSort(int* a, int n);

4.2 Sort.c

#include"Sort.h"void PrintArray(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid][mid+1, end]_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);// [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]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;while (gap < n){/*printf("gap:%2d->", gap);*/for (size_t 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] 归并/*printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);*/// 边界的处理if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}/*printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);*/int j = begin1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}/*printf("\n");*/gap *= 2;}free(tmp);
}// 基数排序/桶排序// 计数排序
// 时间: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){printf("calloc fail\n");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;}}
}

4.3 Test.c

#include"Sort.h"void TestMergeSort()
{int a[] = {10,8,7,1,3,9,4,2,9,10 };PrintArray(a, sizeof(a) / sizeof(int));/*MergeSort(a, sizeof(a) / sizeof(int));*/MergeSortNonR(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}void TestCountSort()
{int a[] = { 1,3,9,1,5,1,2,3,-5,-5,-2 };PrintArray(a, sizeof(a) / sizeof(int));CountSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}int main()
{/*TestMergeSort();*/TestCountSort();return 0;
}

有问题请指出,大家一起进步!

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

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

相关文章

基于ssm的企业文档管理系统+vue论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本企业文档管理系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信息…

Mac上使用phpstudy+vscode配置PHP开发环境

使用的工具&#xff1a; 1、系统版本 2、vs code code 3、phpstudy_pro 一、下载vs code code以及必要的插件 1、vs code下载 点击vs code官网下载 选择对应的版本&#xff0c;一般电脑会自动识别对应的版本&#xff0c;点击下载&#xff0c;然后傻瓜式安装&#xff01; 2…

可狱可囚的爬虫系列课程 11:Requests中的SSL

一、SSL 证书 SSL 证书是数字证书的一种&#xff0c;类似于驾驶证、护照、营业执照等的电子副本。SSL 证书也称为 SSL 服务器证书&#xff0c;因为它是配置在服务器上。 SSL 证书是由受信任的数字证书颁发机构 CA 在验证服务器身份后颁发的&#xff0c;其具有服务器身份验证和…

大白菜U盘安装系统-戴尔电脑

1. 把U盘插入电脑&#xff0c;启动盘去大白菜官网找&#xff0c;镜像可以去微软官网下&#xff0c;想要专业版的网上找资源。 2. 重启电脑&#xff0c;等出现log之后狂按F12&#xff0c;进入BOSS模式。 3. 选择UEFI...也就是下面白色的&#xff0c;按下回车。 4. 选第一个 5.…

基于Python实现地标景点识别

目录 前言简介地标景点识别的背景 地标景点识别的原理卷积神经网络&#xff08;CNN&#xff09;的基本原理地标景点识别的工作流程 使用Python实现地标景点识别的步骤数据收集数据预处理构建卷积神经网络模型模型训练 参考文献 前言 简介 地标景点识别是一种基于计算机视觉技术…

SpringBoot+SSM项目实战 苍穹外卖(11) Apache ECharts

继续上一节的内容&#xff0c;本节学习Apache ECharts&#xff0c;实现营业额统计、用户统计、订单统计和销量排名Top10功能。 数据统计效果图&#xff1a; 目录 Apache ECharts入门案例 营业额统计用户统计订单统计销量排名Top10 Apache ECharts Apache ECharts 是一款基于 …

家居行业如何制定小红书策略,品牌营销须知

凭借出色的品牌传播力&#xff0c;平台一直以来都备受关注。那么作为运营&#xff0c;进入小红书后&#xff0c;该如何利用好各方特性和优势&#xff0c;进行传播呢?今天我们就和大家一起分享下家居行业如何制定小红书策略&#xff0c;品牌营销须知&#xff01; 一、小红书平台…

可应用于电脑主板等产品上的精密基准电路WL431 输出电压可设定 响应速度快

WL431为三端可调节精密基准源。通过两个外接电阻&#xff0c;输出电压可在Vref约2.5 V )到36V连续调节。该电路输出阻抗小(0.2Q)。 开启特性好&#xff0c;在许多应用场合&#xff0c;它能较好地替换齐纳极管。 主要特点&#xff1a;● 温度系数 50pmC ● 在…

自学Python笔记总结(更新中……)

自学Python笔记总结 网址数据类型类型查看类型&#xff0c;使用type内置类标识符 输出输入语句format函数的语法及用法数据类型的转换运算符算数运算符赋值运算符的特殊场景拆包 比较运算符逻辑运算符 与 短路位运算符运算符优先级 程序流程控制分支语句pass 占位 循环语句 whi…

[DM8] 达梦8配置兼容Oracle

查看版本信息 select *&#xff0c;id_code from v$version; 查询解释&#xff1a; DM Database Server 64 V8 1-1-190-21.03.12-136419-ENT 64 版本位数标识&#xff0c;64表示为64位版本&#xff0c;无64则表示为32位版本 V8 大版本号&#xff0c;目前主要是V7、V8 1-1-190…

行为型设计模式——状态模式

状态模式 状态模式是比较简单的设计模式&#xff0c;它的主要作用是减少代码中大量的 if-else 或者 switch-case 等逻辑判断&#xff08;俗称屎山&#xff09;。它将每个状态定义为一个类&#xff0c;而每个状态类有自己对应的方法&#xff0c;因此当需要根据状态执行逻辑代码…

【Web】什么是 XSS 攻击,如何避免?

&#x1f34e;个人博客&#xff1a;个人主页 &#x1f3c6;个人专栏&#xff1a;Web ⛳️ 功不唐捐&#xff0c;玉汝于成 目录 前言 正文 常见方法&#xff1a; 结语 我的其他博客 前言 在当今数字化时代&#xff0c;网络安全成为信息技术领域中的一项至关重要的任务。X…

【hcie-cloud】【20】容器详解【容器介绍,容器工作机制、容器常用命令说明】【上】

文章目录 前言容器是什么虚拟化技术的四个特点容器也是一种虚拟化技术容器是怎么实现虚拟化的&#xff1f;容器对比虚拟机有哪些优势&#xff1f;容器对比虚拟机有哪些不足&#xff1f;容器不仅是一种虚拟化技术&#xff0c;更重要的是一种应用打包机制容器提供的是PaaS服务常见…

jetlinks 规则编排中的函数节点使用 js 脚本格式化输出当前系统时间的坑

网上搜到的都是类似如下这种&#xff1a; // 获取当前时间 var date new Date();// 格式化输出当前时间 var year date.getFullYear(); var month date.getMonth(); var day date.getDate(); var hour date.getHours(); var minute date.getMinutes(); var second date.…

linux 网络文件共享服务

存储类型 DAS 直连式存储 SAN 存储区域网络 NAS 网络附近存储 FTP文件传输协议 文件传输协议 FTP 早期的三个应用级协议之一&#xff0c;基于c/s架构 数据传输格式&#xff1a;二进制&#xff08;默认&#xff09;和文本 tcp 21端口&#xff08;权限&#xff0c;…

网上申请的电话卡,为什么要快递员激活呢

在网上购买的流量卡&#xff0c;快递员不仅仅只是派送&#xff0c;其实很多时候快递员还负责给你激活流量卡。 那么问题就来了&#xff0c;很多朋友可能因为时间问题&#xff0c;或者比较担心个人隐私问题&#xff0c;比较反感让快递员面对面激活&#xff0c;那么如果遇到快递员…

自媒体必备的8个素材网站,免费可商用。

自媒体必备的8个素材网站&#xff0c;视频、音效、音频、图片等素材非常齐全&#xff0c;免费下载&#xff0c;无需担心侵权&#xff0c;赶紧收藏起来吧~ 视频素材 1、菜鸟图库 https://www.sucai999.com/video.html?vNTYwNDUx 菜鸟图库可以找到设计、办公、图片、视频、音频…

vue前端开发自学练习,Props数据传递-类型校验,默认值的设置!

vue前端开发自学练习,Props数据传递-类型校验,默认值的设置&#xff01; 实际上&#xff0c;vue开发框架的时候&#xff0c;充分考虑到了前端开发人员可能会遇到的各种各样的情况&#xff0c;比如大家经常遇到的&#xff0c;数据类型的校验&#xff0c;再比如&#xff0c;默认…

leetcode 349 两个数组的集合

题目 给定两个数组 nums1 和 nums2 &#xff0c;返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 示例 1&#xff1a; 输入&#xff1a;nums1 [1,2,2,1], nums2 [2,2] 输出&#xff1a;[2] 示例 2&#xff1a; 输入&#xff1a…