初阶数据结构之计数排序

非比较排序

计数排序

计数排序⼜称为鸽巢原理,是对哈希直接定址法的变形应⽤。
操作步骤:
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.rhkb.cn/news/406072.html

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

相关文章

线段树-点修区查

翻博客的时候突然发现线段树好像一个没有&#xff0c;我就准备把线段树给讲一下 分三个章节 点修区查 区修区查 区修区查&#xff08;带乘法&#xff09; 今天这一章比较简单&#xff0c;最多就区查稍微要动一点脑子 题目简介 输入n和m&#xff0c;n代表数的个数&#x…

读软件开发安全之道:概念、设计与实施05模式(上)

1. 模式 1.1. 模式分类 1.1.1. 设计属性 1.1.2. 暴露最少信息 1.1.3. 冗余 1.1.4. 强力执行 1.1.5. 信任与责任 1.1.6. 反模式 1.2. 模式可以缓解或者避免很多种类的风险&#xff0c;它们可以形成一个重要的工具箱&#xff0c;帮我们解决潜在的安全威胁 1.3. 不需要为…

学习设置echarts 折线图使用相关参数的方法整理

学习设置echarts 折线图使用相关参数的方法整理 折线图堆叠设置为不堆叠的方法 折线图堆叠设置为不堆叠的方法 官网是这样的&#xff0c;但是不需要这种堆叠形式的如下图&#xff1a; 第2条数据值 第1条数据值 第2条数据值 第3条数据值 第2条数据值 第3条数据值 需要改成…

C语言高手参考手册:函数进阶技巧

[大师C语言]合集&#xff3b;大师C语言(第一篇)&#xff3d;C语言栈溢出背后的秘密&#xff3b;大师C语言(第二十五篇)&#xff3d;C语言字符串探秘&#xff3b;大师C语言(第二篇)&#xff3d;C语言main函数背后的秘密&#xff3b;大师C语言(第二十六篇)&#xff3d;C语言结构体…

汽车管理 API 接口:开启高效车辆运营新时代

API&#xff08;Application Programming Interface&#xff09;是一种接口&#xff0c;用于不同软件之间的通信。在汽车管理领域&#xff0c;API的应用可以帮助提升车辆运营的效率&#xff0c;让车主和车辆管理者更方便地获取车辆相关信息&#xff0c;进行保养和维修等工作。本…

Linux yum提示Error downloading packages

很明显的错误&#xff0c;没有考虑过磁盘空间&#xff0c;记录一下。 Error downloading packages:gcc-4.8.5-44.el7.x86_64: Insufficient space in download directory /var/cache/yum/x86_64/7/base/packages* free 0 * needed 16 M使用du查看当前目录下所有文件大小 du …

黑马头条vue2.0项目实战(十一)——功能优化(组件缓存、响应拦截器、路由跳转与权限管理)

1. 组件缓存 1.1 介绍 先来看一个问题&#xff1f; 从首页切换到我的&#xff0c;再从我的回到首页&#xff0c;我们发现首页重新渲染原来的状态没有了。 首先&#xff0c;这是正常的状态&#xff0c;并非问题&#xff0c;路由在切换的时候会销毁切出去的页面组件&#xff…

HBase原理和操作

目录 一、HBase在Zookeeper中的存储元数据信息集群状态信息 二、HBase的操作Web Console命令行操作 三、HBase中数据的保存过程 一、HBase在Zookeeper中的存储 元数据信息 HBase的元数据信息是HBase集群运行所必需的关键数据&#xff0c;它存储在Zookeeper的"/hbase&quo…

数据结构——链式队列和循环队列

目录 引言 队列的定义 队列的分类 1.单链表实现 2.数组实现 队列的功能 队列的声明 1.链式队列 2.循环队列 队列的功能实现 1.队列初始化 (1)链式队列 (2)循环队列 (3)复杂度分析 2.判断队列是否为空 (1)链式队列 (2)循环队列 (3)复杂度分析 3.判断队列是否…

【具体数学 Concrete Mathematics】1.1.2 平面上的直线

【具体数学 Concrete Mathematics】1.1.2 平面上的直线

Django 第一课 -- 简介

目录 一. 基本介绍 二. 特点 三. MVC 与 MTV 模型 3.1. MVC 模型 3.2. MTV 模型 一. 基本介绍 Django 是一个由 Python 编写的一个开放源代码的 Web 应用框架。 Django 是一个高级的 Python Web 框架&#xff0c;用于快速开发可维护和可扩展的 Web 应用程序。 使用 Dja…

计算机毕业设计Python深度学习房价预测 房价可视化 链家爬虫 房源爬虫 房源可视化 卷积神经网络 大数据毕业设计 机器学习 人工智能 AI

基于python一/二手房数据爬虫分析预测系统可视化 商品房数据Flask框架&#xff08;附源码&#xff09; 项目介绍 技术栈&#xff1a; python语言、Flask框架、MySQL数据库、Echarts可视化 sklearn机器学习 多元线性回归预测模型、requests爬虫框架 链家一手房 一手房数据商品房…

docker连接宿主机redis,提示Connection refused

目录 一、测试环境 二、问题现象 三、问题总结 一、测试环境 centos 7 redis-5.0.14 docker-26.0.1 二、问题现象 服务器重启后docker连接宿主机redis&#xff0c;提示Connection refused Reconnecting, last destination was /172.25.xxx.x:6379 …

VMware vSphere Client无法访问和连接ESXi虚拟主机解决思路

文章目录 前言1. 问题现象2. 问题原因3. 解决方法4. 参考文章 前言 注意 : 可以先看看参考文章那里&#xff0c;在回过来看 1 、 2 、3 1. 问题现象 版本&#xff1a;VMware vCenter Server 5.5.0 build-2442329 问题描述&#xff1a;用VMware vSphere Client 登录ESXI主机出…

状态压缩、记忆化搜索---蒙德里安的梦想

291. 蒙德里安的梦想 - AcWing题库 求把 NMNM 的棋盘分割成若干个 1212 的长方形&#xff0c;有多少种方案。 例如当 N2&#xff0c;M4N2&#xff0c;M4 时&#xff0c;共有 55 种方案。当 N2&#xff0c;M3N2&#xff0c;M3 时&#xff0c;共有 33 种方案。 如下图所示&…

[数据集][目标检测]瞳孔虹膜检测数据集VOC+YOLO格式8768张2类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;8768 标注数量(xml文件个数)&#xff1a;8768 标注数量(txt文件个数)&#xff1a;8768 标注…

【微信小程序】自定义组件 - 数据、方法和属性

1. data 数据 2. methods 方法 在小程序组件中&#xff0c;事件处理函数和自定义方法需要定义到 methods 节点中&#xff0c;示例代码如下&#xff1a; 3. properties 属性 在小程序组件中&#xff0c;properties 是组件的对外属性&#xff0c;用来接收外界传递到组件中的数…

[Algorithm][贪心][跳跃游戏][加油站][单调递增的数字][坏了的计算器]详细讲解

目录 1.跳跃游戏1.题目链接2.算法思路详解3.代码实现 2.加油站1.题目链接2.算法原理详解3.代码实现 3.单调递增的数字1.题目链接2.算法原理详解3.代码实现 4.坏了的计算器1.代码实现2.算法原理详解3.代码实现 1.跳跃游戏 1.题目链接 跳跃游戏 2.算法思路详解 贪心&#xff1…

记忆化搜索与状态压缩:优化递归与动态规划的利器

记忆化搜索是解决递归和动态规划问题的一种高效优化技术。它结合了递归的灵活性和动态规划的缓存思想&#xff0c;通过保存已经计算过的子问题结果&#xff0c;避免了重复计算&#xff0c;大幅提升了算法的效率。当问题状态复杂时&#xff0c;状态压缩技术可以进一步优化空间使…

Java数组05:Arrays类

本节内容视频链接&#xff1a;Java数组07&#xff1a;Arrays类讲解_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV12J41137hu?p57&vd_sourceb5775c3a4ea16a5306db9c7c1c1486b5 Java中的‌Array类是一个针对数组进行操作的工具类&#xff0c;‌提供了排序、‌…