初阶数据结构之计数排序

news/2024/12/21 22:20:02/

非比较排序

计数排序

计数排序⼜称为鸽巢原理,是对哈希直接定址法的变形应⽤。
操作步骤:
1)统计相同元素出现次数
2)根据统计的结果将序列回收到原来的序列中
在这里插入图片描述
在这里插入图片描述

#include "CountSort.h"
void Count(int* arr, int n)
{//根据最大值和最小值确定数组范围int max = arr[0];int min = arr[0];for (int i = 0; i < n; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!");exit(1);}//初始化,使range数组中所有数据为0memset(count, 0, range * sizeof(int));//统计数组中每个数据出现的次数for (int i = 0; i < n; i++){count[arr[i] - min]++;}//给数组元素初始化int index = 0;for (int i = 0; i < range; i++){//取count中的数据往arr中放while (count[i]--){arr[index++] = i + min;}}}

计数排序的特性:
计数排序在数据范围集中时,效率很⾼,但是适⽤范围及场景有限。
时间复杂度: O(N + range)
空间复杂度: O(range)
稳定性:稳定
注意点:
时间复杂度主要是因为count数组会出现里面元素0的情况

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

稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,⽽在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
Q:怎样理解稳定性?
A:通俗点来说就是 ,举一个例子,2,1,3,4,2 稳定的情况是排完序后相同的数字前后顺序一致,不稳定则相反
在这里插入图片描述
在这里插入图片描述
稳定性验证案例
直接选择排序:5 8 5 2 9
希尔排序:5 8 2 5 9
堆排序:2 2 2 2
快速排序:5 3 3 4 3 8 9 10 11

注意
希尔排序不稳定是在于分组
归并排序不稳定是因为找基准值

排序的相关内容先更新到这里告一段落喽! 希望大家有所收获!
在这里插入图片描述


http://www.ppmy.cn/news/1512710.html

相关文章

LabVIEW轨距实时动态检测系统

轨距实时动态检测系统解决铁路轨距不平顺现象&#xff0c;提高铁路运行安全性。系统利用高精度的激光位移传感器与数据同步采集技术&#xff0c;结合LabVIEW软件进行数据处理&#xff0c;有效提高了轨距检测的准确性与效率。 项目背景 随着铁路运输业的快速发展&#xff0c;轨…

golang 如何利用defer+recover()函数 将指定类型的panic异常转换为函数返回 error返回 使用方法示例

在golang开发的时候&#xff0c;对于业务逻辑中的某些panic异常&#xff0c;我们希望将某些不可控的panic异常转换为普通的 error并作为函数返回值返回&#xff0c; 如io 或者os中的某些操作就会导致panic异常&#xff0c;对于这个过程中的某些不可控的panic异常我们希望将某些…

Python使用matplotlib计算并绘制图像的直方图

除了使用OpenCV计算图像直方图外&#xff0c;matplotlib也提供了直方图计算并绘制功能&#xff0c;只需要把图像&#xff08;或对应通道&#xff09;作为参数输入&#xff0c;即可通过matplotlib输出直方图&#xff08;标准直方图&#xff0c;非条形图表达&#xff09;&#xf…

入门 - vue整个过程的生命周期详解

生命周期概念 Vue的生命周期就是vue实例从创建到销毁的全过程&#xff0c;也就是new Vue()开始就是vue生命周期的开始。Vue 实例有⼀个完整的⽣命周期&#xff0c;也就是从开始创建、初始化数据、编译模版、挂载Dom->渲染、更新->渲染、卸载 等⼀系列过程&#xff0c;称…

Unity的动画系统

目录 Unity动画系统的最新更新和改进有哪些&#xff1f; 如何在Unity中高效地使用Animator组件进行复杂动画制作&#xff1f; Unity动画系统中的动画混合和分层功能是如何工作的&#xff1f; 动画混合&#xff08; blend tree&#xff09; 动画分层 在Unity中创建和管理动…

web后端(javaEE)开发——servlet

目录 一、web后端开发概述 二、web后端开发环境搭建 1.安装服务器软件 2.安装JDK 三、创建web后端项目 1.创建项目 2.修改设置 3.*在IDEA中集成Tomcat* 四、Servlet创建和应用 1.概述 2.Servlet程序创建与配置 3.分析Servlet程序结构 一、web后端开发概述 web开发&a…

YOLOv8轻量化改进之slimneck

目录 一、原理 二、代码 三、修改到YOLOv8中 四、yaml文件修改 一、原理 论文地址:2206.02424 (arxiv.org) 主要模块的网络结构 二、代码 slimneck的代码如下,slimneck主要由GSConv和VoVGSCSPC两部分组成。 class GSConv(nn.Module):# GSConv https://github.com/Alan…

SQL数据抽样:精准洞察的高效策略

标题&#xff1a; SQL数据抽样&#xff1a;精准洞察的高效策略 摘要&#xff1a; 在数据分析领域&#xff0c;数据抽样是一种有效减少数据集规模并提取代表性样本的方法。SQL作为数据查询和处理的标准语言&#xff0c;提供了多种数据抽样技术。本文将详细介绍SQL中的数据抽样方…