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

算法:排序

排序算法

  • 1. 简单排序
    • 1.1 直接插入排序
    • 1.2 冒泡排序
    • 1.3 简单选择排序
  • 2. 希尔排序
  • 3. 快速排序
  • 4. 堆排序
  • 5. 归并排序

将文件的内容按照某种规则进行排列。

排序算法的稳定判定:若在待排序的一个序列中, R i R_i Ri R j R_j Rj的关键码相同,即 k i = k j k_i=k_j ki=kj,且在排序前 R i R_i Ri领先于 R j R_j Rj,那么当排序后,如果 R i R_i Ri R j R_j Rj的相对次序保持不变, R i R_i Ri仍领先于 R j R_j Rj,则称此类排序方法为稳定的。若可能出现 R j R_j Rj领先于 R i R_i Ri的情况,则称此列排序是不稳定的。

排序可分为内部排序和外部排序,通过是否全部在内存中排序进行判定。

排序完成两个操作:

  1. 比较两个关键码的大小;
  2. 将记录从一个位置移动到另一个为止。

1. 简单排序

1.1 直接插入排序

将某个数据插入已经排好的队列中。

void insertSort(int data[], int n)
{int i, j;int temp;for (i = 1; i < n; i++){if (data[i] < data[i - 1]) {temp = data[i]; data[i] = data[i - 1];for (j = i - 2; j >= 0 && data[j] > temp; j--) data[j + 1] = data[j];data[j+1] = temp;}}
}

运行结果:

int array[8] = {12, 18184, 45, 78, 45, 555, 47, 36};insertSort(array, 8);for (int i = 0; i < 8; i++)
{printf("%d\n", array[i]);
}

在这里插入图片描述
直接插入排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。排序过程中仅需要一个元素的辅助空间,空间复杂度为 O ( 1 ) O(1) O(1)。直接插入排序是一种稳定的排序方法。

1.2 冒泡排序

顾名思义,冒泡法就是像气泡上浮一样把数据逐渐传递上去。

void bubbleSort(int data[], int n) 
{int i, j, tag = 1;   //tag表示排序过程中是否交换过元素值int temp;for (i = 1; tag && i < n; i++){tag = 0;for (j = 0; j < n - i; j++){if (data[j]>data[j+1]){temp = data[j];data[j] = data[j+1];data[j + 1] = temp;tag = 1;}}}
}
int array[8] = {12, 18184, 45, 78, 45, 555, 47, 36};
//insertSort(array, 8);
bubbleSort(array, 8);for (int i = 0; i < 8; i++)
{printf("%d\n", array[i]);
}

在这里插入图片描述
冒泡排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。排序过程中仅需要一个元素的辅助空间,空间复杂度为 O ( 1 ) O(1) O(1)。冒泡排序是一种稳定的排序方法。

1.3 简单选择排序

逐步找出最小的元素,依次放置。

void selectSort(int data[], int n)
{int i, j, k;int temp;for (i = 0;  i < n-1; i++){k = i;for ( j = i+1; j < n; j++){if (data[j] < data[k]) k = j;}if (k!=i){temp = data[i];data[i] = data[k];data[k] = temp;}}
}

算法结果:

int array[8] = {12, 18184, 45, 78, 45, 555, 47, 36};//insertSort(array, 8);
//bubbleSort(array, 8);
selectSort(array, 8);for (int i = 0; i < 8; i++)
{printf("%d\n", array[i]);
}

在这里插入图片描述
简单选择排序的时间复杂度为 O ( n 2 ) O(n^2) O(n2)。排序过程中仅需要一个元素的辅助空间,空间复杂度为 O ( 1 ) O(1) O(1)。简单选择排序是一种不稳定的排序方法。

2. 希尔排序

希尔排序又称为“缩小增量排序”,是对直接插入排序方法的改进。
希尔排序的基本思想是:先将整个待排记录序列分割成若干子序列,然后分别进行直接插入排序,待整个序列中的记录基本有序时,再对全体记录进行一次直接插入排序。具体做法是先取一个小于n的整数 d 1 d_1 d1作为第一个增量,将所有相距为 d 1 d_1 d1的记录放在同一个组中,从而把文件的全部记录分成 d 1 d_1 d1组,在各组内进行直接插入排序;然后取第二个增量 d 2 ( d 2 < d 1 ) d_2(d_2<d_1) d2(d2<d1),重复上述分组和排序工作,依此类推,直至所取的增量 d i = 1 ( d i < d i − 1 < . . . < d 2 < d 1 ) d_i=1(d_i<d_{i-1}<...<d_2<d_1) di=1(di<di1<...<d2<d1),即所有记录放在同一组进行直接插入排序,将所有记录排列有序为止。
在这里插入图片描述

/*************************************************Function:shellSort,希尔排序方法Description: 整数序列排序,从小到大Input:    data[]   排序数组n        数组大小delta[]  长度为m且递减有序的增量序列最后一个元素为1m   delta[]数组大小Output:输出转换结果Return: 0
*************************************************/
void shellSort(int data[], int n, int delta[], int m)
{int k, i, dk, j; int temp;for ( i = 0; i < m; i++){dk = delta[i];for (k = dk; k < n; ++k){if (data[k]<data[k-dk]){temp = data[k];for (j = k - dk; j>0&&temp<data[j]; j-=dk){data[j + dk] = data[j];}data[j + dk] = temp;}}}
}

希尔排序的时间复杂度为 O ( N 1.3 ) O(N^{1.3}) O(N1.3).希尔排序是不稳定的排序方法。

3. 快速排序

快速排序

一趟快速排序的过程称为一次划分,具体做法是:附设两个元素位置指示变量 i i i j j j,它们的初值分别指向待排序列的第一个记录和最后一个记录。设枢轴记录(通常是第一个记录)的关键码为 pivot,则首先从j所给位置起向前搜索,找到第一个关键码小于 pivot 的记录时停止,然后从i所给位置起向后搜索,找到第一个关键码大于pivot 的记录时停止,此时交换j所给位置和i所给位置的元素,重复该过程直至i与i相等为止,完成一趟划分。

//用data[low]的值作为枢轴元素pivot进行划分
//不断劈成两半之后排序
int partition(int data[], int low, int high)
{int i, j;int pivot;while (i<j){while (i<j&&data[j]>=pivot){j--;}data[i] = data[j];while (i < j && data[i] <= pivot){i++;}data[j] = data[i];}data[i] = pivot;return i;
}/*************************************************Function:quickSort,快速排序方法Description: 整数序列排序,从小到大Input:    data[]   排序数组low  数组最低位high 数组最高位Output:输出转换结果Return: 0
*************************************************/
void quickSort(int data[], int low, int high)
{if (low < high){int loc = partition(data, low, high);quickSort(data,low,loc-1);quickSort(data,  loc + 1, high);}
}

4. 堆排序

5. 归并排序

相关文章:

算法:排序

排序算法 1. 简单排序1.1 直接插入排序1.2 冒泡排序1.3 简单选择排序 2. 希尔排序3. 快速排序4. 堆排序5. 归并排序 将文件的内容按照某种规则进行排列。 排序算法的稳定判定&#xff1a;若在待排序的一个序列中&#xff0c; R i R_i Ri​和 R j R_j Rj​的关键码相同&#xf…...

MyBatis-Plus 更新对象时如何将字段值更新为 null

MyBatis-Plus 是一个 MyBatis 的增强工具&#xff0c;在简化开发、提高效率方面表现非常出色。然而&#xff0c;在使用 MyBatis-Plus 更新对象时&#xff0c;默认情况下是不会将字段值更新为 null 的。这是因为 MyBatis-Plus 使用了非空字段策略&#xff08;FieldStrategy&…...

Unreal5从入门到精通之如何在VR中使用3DUI

文章目录 前言创建3DUI1.新建控件蓝图2.添加控件到画布上3.新建Actor蓝图MyUIActor4.添加控件组件Widget5.设置控件类和画布大小6.创建MyUIActor实例到场景中3DUI和VR射线交互1.添加按钮的点击事件2.设置MyUIActor碰撞响应3.VRPawn添加控件交互组件4.添加手柄Trigger点击事件绑…...

ViSual studio如何安装 并使用GeographicLib

在C的 Boost.Geometry、GDAL/OGR 和 GeographicLib。这些库都可以用于计算两个经纬度点之间的地面距离。 . Boost.Geometry 描述&#xff1a;Boost库的一部分&#xff0c;提供了几何计算功能&#xff0c;包括计算两点之间的地面距离。 优势&#xff1a;轻量级、易于集成到C项…...

Java程序设计:spring boot(11)——分布式缓存 Ehcache 整合

目录 1 Spring Cache 相关注解说明 1.1 CacheConfig 1.2 Cacheable 1.3 CachePut 1.4 CacheEvict 1.5 Caching 2 环境配置 2.1 pom.xml 依赖添加 2.2 ehcahe.xml ⽂件添加 2.3 application.yml 缓存配置 2.4 启动缓存 2.5 JavaBean 对象实现序列化 3 缓存实现 3.…...

豆包,攻克数字是个什么工具?《GKData-挖掘数据的无限可能》(数据爬虫采集工具)

豆包&#xff0c;攻克数字是个什么工具&#xff1f; “攻克数字” 指的是 “攻克数字&#xff08;GKData&#xff09;” 这样一款工具。是一款针对网页、APP中数据自动解析转表存入数据库的软件&#xff0c;为数据工作者而生。它是一个不会编程也能用的可视化数据解析为标准二…...

说一说QWidget

目录 关于QWidget 作为界面组件时&#xff0c;你需要有印象的 1. 控制属性 2. 组件状态与交互属性 3. 外观和样式属性 4. 布局与子组件管理属性 5. 图标和光标属性 6. 大小策略属性 作为单独的窗体的属性 写Qt快两年了&#xff0c;也写过一些规模偏大的软件&#xff0c…...

Web3.0技术入门

Web3.0技术入门是一个涉及多个方面和领域的复杂过程&#xff0c;以下是一些关键的步骤和要点&#xff0c;帮助您初步了解并掌握Web3.0技术。 一、了解Web3.0的基本概念 Web3.0也被称为下一代互联网&#xff0c;它是对当前互联网&#xff08;Web2.0&#xff09;的演进和升级。…...

spygalss cdc 检测的bug(二)

当allow_qualifier_merge设置为strict的时候&#xff0c;sg是要检查门的极性的。 如果qualifier和src经过与门汇聚&#xff0c;在同另一个src1信号或门汇聚&#xff0c;sg是报unsync的。 假设当qualifier为0时&#xff0c;0&&src||src1src1&#xff0c;src1无法被gat…...

集合论(ZFC)之 选择公理(Axiom of Choice)注解

直观感受&#xff08;Intuition&#xff09; 集合论&#xff08;ZFC&#xff09;中的 "C" 指的是选择公理&#xff08;Axiom of Choice&#xff09;中的"choice"。简单来说&#xff0c;对于任一非空集合 S&#xff0c;那么存在一个函数 f&#xff0c;选择出…...

JS:字符串操作

目录 1、 字符串分割 1、 字符串分割 var str "123,456,789"; console.log(str.split(,)); // ["123", "456", "789"]...

.NET 一款二进制文件转换Shellcode的工具

01阅读须知 此文所提供的信息只为网络安全人员对自己所负责的网站、服务器等&#xff08;包括但不限于&#xff09;进行检测或维护参考&#xff0c;未经授权请勿利用文章中的技术资料对任何计算机系统进行入侵操作。利用此文所提供的信息而造成的直接或间接后果和损失&#xf…...

【CSS】——基础入门常见操作

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 一&#xff1a;CSS引入 二&#xff1a;CSS对元素进行美化 1&#xff1a;style修饰 2&#xff1a;选…...

LuaJIT源码分析(五)词法分析

LuaJIT源码分析&#xff08;五&#xff09;词法分析 lua虽然是脚本语言&#xff0c;但在执行时&#xff0c;还是先将脚本编译成字节码&#xff0c;然后再由虚拟机解释执行。在编译脚本时&#xff0c;首先需要对源代码进行词法分析&#xff0c;把源代码分解为token流。lua的toke…...

005 匿名信

005 匿名信 题目描述 电视剧《分界线》里面有一个片段&#xff0c;男主为了向警察透露案件细节&#xff0c;且不暴露自己&#xff0c;于是将报刊上的字剪下来&#xff0c;剪拼成一封匿名信。现在有一名举报人&#xff0c;希望借鉴这种方式&#xff0c;使用英文报刊完成举报操…...

聊聊Web3D 发展趋势

随着 Web 技术的不断演进&#xff0c;Web3D 正逐渐成为各行业数字化的重要方向。Web3D 是指在网页中展示 3D 内容的技术集合。近年来&#xff0c;由于 WebGL、WebGPU 等技术的发展&#xff0c;3D 内容已经能够直接在浏览器中渲染&#xff0c;为用户提供更加沉浸、互动的体验。以…...

【数据结构与算法】LeetCode: 贪心算法

文章目录 LeetCode&#xff1a; 贪心算法买卖股票的最佳时机 &#xff08;Hot100&#xff09;买卖股票的最佳时机 II跳跃游戏 &#xff08;Hot100&#xff09;跳跃游戏 II&#xff08;Hot100&#xff09;划分字母区间 &#xff08;Hot100&#xff09;分发饼干K次取反后最大化的…...

Date 日期类的实现(c++)

本文用c实现日期类 将会实现以下函数 bool operator<(const Date& d);bool operator<(const Date& d);bool operator>(const Date& d);bool operator>(const Date& d);bool operator(const Date& d);bool operator!(const Date& d);Date&…...

智能家居10G雷达感应开关模块,飞睿智能uA级别低功耗、超高灵敏度,瞬间响应快

在当今科技飞速发展的时代&#xff0c;智能家居已经逐渐成为人们生活中不可或缺的一部分。从智能灯光控制到智能家电的联动&#xff0c;每一个细节都在为我们的生活带来便利和舒适。而在众多智能家居产品中&#xff0c;10G 雷达感应开关模块以其独特的优势&#xff0c;正逐渐成…...

头歌——人工智能(机器学习 --- 决策树2)

文章目录 第5关&#xff1a;基尼系数代码 第6关&#xff1a;预剪枝与后剪枝代码 第7关&#xff1a;鸢尾花识别代码 第5关&#xff1a;基尼系数 基尼系数 在ID3算法中我们使用了信息增益来选择特征&#xff0c;信息增益大的优先选择。在C4.5算法中&#xff0c;采用了信息增益率…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

VisualXML全新升级 | 新增数据库编辑功能

VisualXML是一个功能强大的网络总线设计工具&#xff0c;专注于简化汽车电子系统中复杂的网络数据设计操作。它支持多种主流总线网络格式的数据编辑&#xff08;如DBC、LDF、ARXML、HEX等&#xff09;&#xff0c;并能够基于Excel表格的方式生成和转换多种数据库文件。由此&…...

Java数组Arrays操作全攻略

Arrays类的概述 Java中的Arrays类位于java.util包中&#xff0c;提供了一系列静态方法用于操作数组&#xff08;如排序、搜索、填充、比较等&#xff09;。这些方法适用于基本类型数组和对象数组。 常用成员方法及代码示例 排序&#xff08;sort&#xff09; 对数组进行升序…...