当前位置: 首页 > 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;采用了信息增益率…...

一七一、React性能优化方式

在 React 中进行性能优化可以通过多种手段来减少渲染次数、优化渲染效率并减少内存消耗。以下是常见的性能优化方法及示例&#xff1a; 1. shouldComponentUpdate shouldComponentUpdate 是类组件中的生命周期方法&#xff0c;它可以让组件在判断是否需要重新渲染时&#xff…...

编写dockerfile生成镜像,并且构建容器运行

编写dockerfile生成镜像&#xff0c;并且构建容器运行 目录 编写dockerfile生成镜像&#xff0c;并且构建容器运行 概述 一、dockerfile文件详解 Dockerfile的基本结构 Dockerfile的常用指令 二、构建过程 概述 随着微服务应用越来越多&#xff0c;大家需要尽快掌握dock…...

Java项目练习——学生管理系统

1. 整体结构 代码实现了基本的学生管理系统功能&#xff0c;包括登录、注册、忘记密码、添加、删除、修改和查询学生信息。 使用了ArrayList来存储用户和学生信息。 使用了Scanner类来处理用户输入。 2. 主要功能模块 登录 (logIn)&#xff1a;验证用户名和密码&#xff0c;…...

sqlserver、达梦、mysql的差异

差异项sqlserver达梦mysql单行注释---- 1、-- &#xff0c;--后面带个空格 2、# 包裹对象名称&#xff0c;如表、表字段等 [tableName] "tableName"tableName表字段自增IDENTITY(1, 1)IDENTITY(1, 1)AUTO_INCREMENT二进制数据类型IMAGEIMAGE、BLOBBLOB 存储一个汉字需…...

Spring AOP(定义、使用场景、用法、3种事务、事务失效场景及解决办法、面试题)

目录 1. AOP定义&#xff1f; 2.常见的AOP使用场景&#xff1a; 3.Spring AOP用法 3.1 Spring AOP中的几个核心概念 3.1.1 切面、切点、通知、连接点 3.1.2 切点表达式AspectJ 3.2 使用 Spring AOP 的步骤总结 3.2.1 添加依赖: 3.2.2 定义切面和切点&#xff08;切点和…...

Flutter鸿蒙next 封装对话框详解

✅近期推荐&#xff1a;求职神器 https://bbs.csdn.net/topics/619384540 &#x1f525;欢迎大家订阅系列专栏&#xff1a;flutter_鸿蒙next &#x1f4ac;淼学派语录&#xff1a;只有不断的否认自己和肯定自己&#xff0c;才能走出弯曲不平的泥泞路&#xff0c;因为平坦的大路…...

【项目实战】通过LLaMaFactory+Qwen2-VL-2B微调一个多模态医疗大模型

前言 随着多模态大模型的发展&#xff0c;其不仅限于文字处理&#xff0c;更能够在图像、视频、音频方面进行识别与理解。医疗领域中&#xff0c;医生们往往需要对各种医学图像进行处理&#xff0c;以辅助诊断和治疗。如果将多模态大模型与图像诊断相结合&#xff0c;那么这会…...

SCSI驱动与 UFS 驱动交互概况

SCSI子系统概况 SCSI&#xff08;Small Computer System Interface&#xff09;子系统是 Linux 中的一个模块化框架&#xff0c;用于提供与存储设备的通用接口。通过 SCSI 子系统&#xff0c;可以支持不同类型的存储协议&#xff08;如 UFS、SATA、SAS&#xff09;&#xff0c…...

软件工程实践项目:人事管理系统

一、项目的需求说明 通过移动设备登录app提供简单、方便的操作。根据公司原来的考勤管理制度&#xff0c;为公司不同管理层次提供相应的权限功能。通过app上面的各种标准操作&#xff0c;考勤管理无纸化的实现&#xff0c;使公司的考勤管理更加科学规范&#xff0c;从而节省考…...

不使用三方软件,win系统下禁止单个应用联网能力的详细操作教程

本篇文章主要讲解&#xff0c;在win系统环境下&#xff0c;禁止某个应用联网能力的详细操作教程&#xff0c;通过本教程您可以快速掌握自定义对单个程序联网能力的限制和禁止。 作者&#xff1a;任聪聪 日期&#xff1a;2024年10月30日 步骤一、按下win按键&#xff08;四个小方…...

珠海网站建设科技公司/济南seo排行榜

我们在工作中或多或少都使用过线程池&#xff0c;但是为什么要使用线程池呢&#xff1f;从他的名字中我们就应该知道&#xff0c;线程池使用了一种池化技术&#xff0c;和很多其他池化技术一样&#xff0c;都是为了更高效的利用资源&#xff0c;例如链接池&#xff0c;内存池等…...

wordpress图片素材主题/网站排名首页前三位

一、前言 1、本文主要内容 Visual Studio Code 开发环境配置使用 ASP.NET Core 构建Web应用ASP.NET Core Web 应用启动类说明ASP.NET Core Web 项目结构说明2、本教程环境信息 软件/环境说明操作系统Windows 10SDK2.1.401ASP.NET Core2.1.3IDEVisual Studio Code 1.27浏览器Chr…...

做免费漫画网站有风险吗/广州网站建设工作室

关于Python的编码问题已经是老生常谈了&#xff0c;此处主要是介绍一个罕见的问题&#xff0c;也算是Python2的一个bug了&#xff08;Python3不会有此问题&#xff09;。 在有时候我们去爬取网页或者调用一些第三方库获取文本的时候&#xff0c;有可能会出现这样一种情况&#…...

思源黑体做网站/线下推广方案

本文为大家讲解了python算法表示概念&#xff0c;供大家参考&#xff0c;具体内容如下常数阶O(1)常数又称定数&#xff0c;是指一个数值不变的常量&#xff0c;与之相反的是变量为什么下面算法的时间复杂度不是O(3)&#xff0c;而是O(1)。?这个算法的运行次数函数是f(n)3。根据…...

网站开发维护成本/微商软文

介绍一下通过在线免费制图网站 Freedgo Design绘制各类图形的方法。 什么是 Freedgo Design&#xff1f;Freedgo Design 是一in款在线绘制专业图形的网站。Freedgo Design可以绘制各种类型的图形&#xff0c;针对业务逻辑的流程图&#xff0c;软件设计ER模板&#xff0c;工作流…...

门户网站建设依据/哪个杭州seo好

Function Function is composed of name, parameter (operand, type of operand), return value, body with another adornment like: inline, virtual, static, const, throw().我们必须在调用函数之前,就声明该函数否则会引起编译错误.函数声明由函数返回类型,函数名和参数表…...