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

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...

2025年- H71-Lc179--39.组合总和(回溯,组合)--Java版

1.题目描述 2.思路 当前的元素可以重复使用。 &#xff08;1&#xff09;确定回溯算法函数的参数和返回值&#xff08;一般是void类型&#xff09; &#xff08;2&#xff09;因为是用递归实现的&#xff0c;所以我们要确定终止条件 &#xff08;3&#xff09;单层搜索逻辑 二…...