当前位置: 首页 > news >正文

数据结构——排序算法(C语言)

本篇将详细讲一下以下排序算法:

  1. 直接插入排序
  2. 希尔排序
  3. 选择排序
  4. 快速排序
  5. 归并排序
  6. 计数排序

排序的概念

排序:所谓排序,就是使一串记录,按照其中的某个或某写关键字的大小,按照递增或递减0排列起来的操作。

稳定性的概念

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变。如一下例子,

5 2 3 4 5 9 8

 经过排序,如果红5和蓝5的相对顺序不对,这就叫稳定,反之则不稳定。

 直接插入排序

直接插入排序的思想:将待排序的记录按其关键码值的大小逐个插入到一个已经排好序的序列中,直到所有的序列为有序序列。

实际中,我们玩扑克牌时,就用到了这样的一个排序算法。

 

时间复杂度: 

直接插入排序时一个稳定的排序,如果有相同的元素,它们的相对位置不会发生变化。它时间复杂度最好的情况下是O(N),当一个数插入到已经排好序的序列中,只需要比较一次就好了。

最坏情况:O(N^2) ,在完全逆序的情况下,要排升序。


希尔排序 

 希尔排序其实和插入排序很像,只不过希尔排序的思想是:先预排序,最后插入排序。

预排序的意义在哪里??

  • 大的数更快到后面去,小的数更快到前面去。gap越大跳的越快,越不有序,当gap =1 时就是插入排序。

 时间复杂度

希尔排序的时间复杂度:大约为O(N^1.3) 


选择排序

选择排序的思想:选择排序可以在一次查找中找到最大的数和最小的数,然后把最大的数放到最后,最小的数放到最前面。

 

时间复杂度

时间复杂度是O(N^2)

稳定性:差 


 快速排序

快排思想:说到排序,或多或少都听过快速排序,快速排序是Hoare于1962年提出的一种二叉树结构的交换方法,其基本思想为:任取待排序元素序列中的某个元素作为基准值,按照该排序吗将待排序集合分割成2个子序列,左序列小于keyi值,右序列大于keyi值,然后重复此方法,最后拍完序。

快速排序一次可以确定一个值在正确的位置上。(这个值就是key值)

	if (begin >= end){return;}int left = begin, right = end;int keyi = left;while (left < right){//先让右边先走while (left<right && a[right]>=a[keyi]){--right;}while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;//[begin,keyi-1]  keyi [keyi+1,end]QuickSort(a,begin,keyi-1);QuickSort(a,keyi+1,end);

最常见的就是上面的递归代码,这是Hoare的一种方式实现快排。

Hoare思想:让基准值的右边先走,直到找到比基准值小的数,然后让左边走,直到找到比基准值大的数,然后交换,最后left=right相等的时候,将left位置的值与基准值交换。这样就实现了一次排序。

这里我们想一想快速排序为什么要让基准值的对面开始????

挖坑法: 用一个tmp记录第一个值的坑位,让右边先走,直到找到比坑位小的数,然后让a[right]赋值给坑位,然后把坑位给给right,继续让左边先走,直到找到比坑位大的数,然后把值赋给坑位,让坑位给给left,一直循环。

前后指针法:让prev指向key值,cur指向key值之后的一个值,当a[cur] < a[key] 的时候,就让prev++和cur交换,然后一直循环。


快排的非递归: 快排的思想其实不难发现像一个栈(后进先出),因为快排每次可以确定一个基准值的位置,所以,第一次push进left和right,让他们进行一次排序,就接着push进right和keyi+1,再push进keyi-1和left,注意顺序,因为快排的中间也是一个后进先出的思想。

快排的缺点

 快排其实是有缺点的,因为快排的时间复杂度不一定是O(N*logN),如果排升序,给一个倒序的序列,就有可能达到O(N^2)。所以有了这么一个缺点,就可以做一个三数区中的优化,其实Sort函数中也有这样的处理,而且Sort中还优化了一次快排递归深度过深的时候会用堆排序,在接近有序的时候会用插入排序,而且Sort中只对了右边进行递归处理。如果有兴趣,可以去了解一下Sort的源码,里面有详细解释。


 归并排序

归并排序:它是建立在归并操作上的一种有效的排序算法,该算法采用了分治的思想。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段有序。若将两个有序表合并成一个有序表,称为二路归并。        

归并排序可以看出是一个后序的排序, 先递归,然后从前面开始排好序,然后再memcpy到原数组。

归并排序其实用在解决磁盘外的外排序问题中,如果有下面的场景,归并排序就起到了很大的作用。

时间复杂度

 归并排序也是一种经典的O(N*logN)  空间复杂度是O(N),这时因为开辟了一块tmp临时数组


计数排序 

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

步骤:1.统计想相同元素出现的次数

2.根据统计的结果将序列回收到原来的序列中

 计数排序的特性:

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

相关文章:

数据结构——排序算法(C语言)

本篇将详细讲一下以下排序算法&#xff1a; 直接插入排序希尔排序选择排序快速排序归并排序计数排序 排序的概念 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某写关键字的大小&#xff0c;按照递增或递减0排列起来的操作。 稳定性的概念…...

基于Http Basic Authentication的接口

Basic Authenrication是 HTTP 用户代理提供用户名的一种方法 &#xff0c;它是对 Web 资源实施访问控制的最简单技术&#xff0c;它不需要 Cookie、会话标识符和登录页面。HTTP Basic身份验证使用静态的标准HTTP标头&#xff0c;这意味着 不必在预期中进行握手。 当用户代理想…...

【yaml文件的编写】

yaml文件编写 YAML语法格式写一个yaml文件demo创建资源对象查看创建的pod资源创建service服务对外提供访问并测试创建资源对象查看创建的service在浏览器输入 nodeIP:nodePort 即可访问 详解k8s中的port&#xff1a;portnodePorttargetPortcontainerPortkubectl run --dry-runc…...

kt6368A双模蓝牙芯片无法透传 可能是什么问题呢

一、问题简介- kt6368A蓝牙芯片无法透传 可能是什么问题呢&#xff1f; KT6368A蓝牙芯片&#xff0c;在使用上还是非常的简单&#xff0c;总共也就8个腿&#xff0c;焊接也是很容易的事情 出现不能透传&#xff0c;大概率有如下2点原因 硬件问题&#xff0c;比如&#xff1…...

SpringBoot终极讲义第二章笔记

01.关于Import 和 ImportResource Import注解用法(类上): 一般和Configuration一起使用,用来导入里面Bean方法返回的对象 ImportResource(类上):一般和Configuration一起使用,用来导入某个.XML文件里的bean 个人觉得这两个注解有点鸡肋 SpringBoot启动类默认扫描的是启动类…...

【C++面向对象侯捷下】4. pointer-like classes,关于智能指针 | 5. function-like classes,所谓仿函数

文章目录 4. pointer-like classes,关于智能指针pointer-like classes,关于智能指针 shared_ptrpointer-like classes,关于迭代器5. function-like classes&#xff0c;所谓仿函数【不懂&#xff0c;跳过】 4. pointer-like classes,关于智能指针 pointer-like classes,关于智…...

社科院与杜兰大学能源管理硕士项目——惊喜会随时间慢慢酝酿而出

我们越来越难感受到惊喜&#xff0c;按部就班的生活让我们丧失了感知力&#xff0c;我们再难以被简单的确幸所打动。试试停下脚步&#xff0c;惊喜往往不期而遇。社科院与杜兰大学能源管理硕士项目是你人生中的小确幸吗 学习是一种持续不断的自我提升&#xff0c;它能让我们逐渐…...

Array简介

概念&#xff1a; 数组&#xff08;Array&#xff09;是Java中最简单的数据结构之一&#xff0c;它用于存储固定大小的相同类型元素序列。数组是一个连续分配的内存块&#xff0c;可以通过索引访问其中的元素。元素在数组中按照顺序排列&#xff0c;并使用整数索引来唯一标识每…...

Django的模版使用(Django-03)

一 模版的使用 模板引擎是一种可以让开发者把服务端数据填充到html网页中完成渲染效果的技术。它实现了 把前端代码和服务端代码分离 的作用&#xff0c;让项目中的业务逻辑代码和数据表现代码分离&#xff0c;让前端开发者和服务端开发者可以更好的完成协同开发。 静态网页&…...

详解分布式搜索技术之elasticsearch

目录 一、初识elasticsearch 1.1什么是elasticsearch 1.2elasticsearch的发展 1.3为什么学习elasticsearch? 1.4正向索引和倒排索引 1.4.1传统数据库采用正向索引 1.4.2elasticsearch采用倒排索引 1.4.3posting list ​1.4.4总结 1.5 es的一些概念 1.5.1文档和字段 …...

系统架构设计:3 软件架构建模技术与应用

目录 一 架构“4+1”视图 二 论点 1 架构的本质 2 “4+1”视图 (1)逻辑视图 <...

JAVA在线电子病历编辑器源码 B/S架构

电子病历在线制作、管理和使用的一体化电子病历解决方案&#xff0c;通过一体化的设计&#xff0c;提供对住院病人的电子病历书写、保存、修改、打印等功能。电子病历系统将临床医护需要的诊疗资料以符合临床思维的方法展示。建立以病人为中心&#xff0c;以临床诊疗信息为主线…...

TS中的枚举是什么如何使用

在 TypeScript 中&#xff0c;枚举&#xff08;enum&#xff09;是一种用于定义命名常量集合的数据类型。枚举可以提高代码的可读性和可维护性&#xff0c;因为它允许开发人员定义并使用有意义的符号名称来表示特定的常量。 下面是一个使用枚举的示例&#xff1a; enum Color…...

UG\NX二次开发 重命名特征对象 UF_OBJ_set_name

文章作者:里海 来源网站:《里海NX二次开发3000例专栏》 感谢粉丝订阅 感谢 林闹 订阅本专栏,非常感谢。 简介 UG\NX二次开发 重命名特征 UF_OBJ_set_name 效果 代码 #include "me.hpp" #include <vector> #include...

低欲望社会:只要我没欲望,世界就对我束手无策?

新的转变正在发生&#xff0c;越来越多的人&#xff0c;正从外部的物质世界向内部的精神世界回归。 比如&#xff0c;中产不再炫名牌&#xff0c;而是改炫读书&#xff1b;打工人不再炫工资&#xff0c;而是炫如何整顿职场。 越来越多的人认为消费主义弥漫着恶臭&#xff0c;…...

抢红包设计

抢红包大致可以分为2步&#xff1a;1 发红包 &#xff1b;2 抢红包 发红包流程 为了突出红包设计主题&#xff0c;以下设计会忽略支付流程、24H过期退款剩余金额、用户领取红包余额到账等业务&#xff0c;则简化后的相关表设计如下&#xff1a; CREATE TABLE red_record (id…...

k8s集群-6(daemonset job cronjob控制器)

Daemonset 一个节点部署一个节点 当有节点DaemonSet 确保全部 (或者某些) 节点上运行一个 Pod 的副本。加入集群时&#xff0c;也会为他们新增一个 Pod 。当有节点从集群移除时&#xff0c;这些Pod 也会被回收。删除 DaemonSet 将会删除它创建的所有 Pod。 DaemonSet 的典型用…...

Compose 编译器版本和Kotlin版本对应关系

使用了最新的kotlin版本&#xff0c;compose报错&#xff0c;不兼容&#xff0c;在这里记录一下版本对应关系 值得注意的是Compose Kotlin 编译器扩展 (androidx.compose.compiler) 未关联到 Compose 库版本。相反&#xff0c;它会关联到 Kotlin 编译器插件的版本&#xff0c;…...

vite+vue+cesium

1.创建vite项目 npm create vite 项目名称 2. 选择vuejs/ts 3.在终端输入命令 npm install 4.安装cesium插件&#xff0c;在终端输入命令 npm i cesium vite-plugin-cesium vite -D 5.项目配置cesium 在vite.config.js里进行配置 import { defineConfig } from vite i…...

tcp滑动窗口原理

18.1 滑动窗口 我们再来看这个比喻&#xff1a; 网络仅仅是保证了整个网络的连通性&#xff0c;我们我们基于整个网络去传输&#xff0c;那么是不是我想发送多少数据就发送多少数据呢&#xff1f;如果是这样的话&#xff0c;是不是就会像我们的从一个池塘抽水去灌到另外一个…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器

一.自适应梯度算法Adagrad概述 Adagrad&#xff08;Adaptive Gradient Algorithm&#xff09;是一种自适应学习率的优化算法&#xff0c;由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率&#xff0c;适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

【JVM】Java虚拟机(二)——垃圾回收

目录 一、如何判断对象可以回收 &#xff08;一&#xff09;引用计数法 &#xff08;二&#xff09;可达性分析算法 二、垃圾回收算法 &#xff08;一&#xff09;标记清除 &#xff08;二&#xff09;标记整理 &#xff08;三&#xff09;复制 &#xff08;四&#xff…...

【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制

目录 节点的功能承载层&#xff08;GATT/Adv&#xff09;局限性&#xff1a; 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能&#xff0c;如 Configuration …...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...