当前位置: 首页 > 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;是不是就会像我们的从一个池塘抽水去灌到另外一个…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...