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

蓝桥杯算法基础(13):十大排序算法(希尔排序) (快速排序)c语言版

希尔排序 

优化版的插入排序,优化的地方就是步长(增量)增大了,原来的插入排序的步长(增量)是1,而希尔排序的步长(增量)可以很大,然后逐渐减小直到1形成插入排序
也叫(减小增量排序)
若不了解,可看之前发布的希尔排序
void shellSort1(int arr[],int length){for(int i=interval;i<arr.length;i+=interval){int target=arr[i];int j=i-interval;while(target<arr[j]){arr[j+inertval]=arr[j];j-=interval;}arr[j+interval]=target;}
}
个人感觉shellSort2更复杂一些。
void shellSort2(int arr[],int length){int h=4;while(h>=1){for(int i=h;i<length;i++){for(int j=i;j>=h&&arr[j]<arr[j-h];j-=h){int temp=arr[j];arr[j]=arr[j-h];arr[j-h]=temp;}}h/=2;}
}
shellSort1的增量为length/2,不断取半
个人感觉shellSort1更好用,shellSort2复杂一些,shellSort更复杂。
经典的希尔序列1,4,13,.....,3*n+1
void shellSort3(int arr[],int length){int h=1;int t=length/3;while(h<t)h=3*h+1;//让步长(增量)在length左右//shellSort2的步长给锁死成4了,不过挺好用while(h>=1){for(int i=h;i<length;i++){for(int j=i;j>=h&&arr[j]<arr[j-h];j-=h){int temp=arr[j];arr[j]=arr[j-h];arr[j-h]=temp;}}h/=3;}
}
快速排序
冒泡排序的优化版本,核心思想:使用轴,每一轮左右递归后,把轴放到中间,使得轴的左边都比轴小,轴的右边东渡比轴大,当所有的递归都结束了就自然排序好了
pivot:轴(主元)一般选第一个元素
需要用到双指针,一个左指针,一个右指针
左指针找比轴(主元)大的,右指针找比轴(主元)小的
然后二者值交换
void quickSort(int arr[],int left,int right){if(left>=right)return;int i=left;//左指针int j=right;//右指针int pivot=arr[i];//该整体第一个元素,并将主元提取出来while(i<j){while(i<j&&arr[j]>=pivot)j--;//找右边第一个小于pivot的值arr[i]=arr[j];//然后把小于pivot的值给主元所在位置while(i<j&&arr[i]<=pivot)i++;//找左边第一个大于pivot的值arr[j]=arr[i];将该值赋给第一个小于pivot的值//保留一个空位,即原来主元空出来的位置,可用于值的交换//左指针每找到一个大于pivot的值,就停下,右指针每找到一个小于pivot的值,就停下,然后二者互换// while(i<j&&arr[i]<=pivot)循环条件添加i<j是因为,在while(i<j)这个大循环中,仍有两个while嵌套,第一个while结束后,第二个while会继续执行,i和j的位置就彼此越界了}arr[i]=pivot;quickSort(arr,left,i-1);quickSort(arr,i+1,right);}(第二种写法)void swap(int arr[],int i,int j){//换值函数int temp=arr[i];arr[i]=arr[j];arr[j]=temp;}
void quickSort2(int arr[],int left[],int right){//另一种快速排序的样例if(left>=right)return;int pivot=arr[left];int i=left+1;//这里有两个指针int j=left+1;while(j<=right){//每轮循环,j都向右移一位if(arr[j]<pivot){//如果j指向的值小于pivotswap(arr,i,j);//则交换i和j的值i++;//每次将小于pivot的值移到左边,i右移一位,i就用于等待交换的位置,每次j找到小于pivot的值,都与i位置上的数交换}j++;//j用于寻找小于pivot的值}swap(arr,left,i-1);//while循环结束后,i最后+1了,所以i-1为最后一个小于pivot的值的位置,因此将主元left上的值与i-1的值交换quickSort2(arr,left,i-2);//主元左边quickSort2(arr,i,right);//主元右边
}

相关文章:

蓝桥杯算法基础(13):十大排序算法(希尔排序) (快速排序)c语言版

希尔排序 优化版的插入排序&#xff0c;优化的地方就是步长&#xff08;增量&#xff09;增大了&#xff0c;原来的插入排序的步长&#xff08;增量&#xff09;是1&#xff0c;而希尔排序的步长&#xff08;增量&#xff09;可以很大&#xff0c;然后逐渐减小直到1形成插入排…...

web学习笔记(三十二)

目录 1.函数的call、apply、bind方法 1.1call、apply、bind的相同点 1.2call、apply、bind的不同点 1.3call、apply、bind的使用场景 2. 对象的深拷贝 2.1对象的浅拷贝 2.1对象的深拷贝 1.函数的call、apply、bind方法 1.1call、apply、bind的相同点 在没有传参数时&…...

Android 地图SDK 绘制点 删除 指定

问题 Android 地图SDK 删除指定绘制点 详细问题 笔者进行Android 项目开发&#xff0c;对于已标记的绘制点&#xff0c;提供撤回按钮&#xff0c;即删除绘制点&#xff0c;如何实现。 解决方案 新增绘制点 private List<Marker> markerList new ArrayList<>…...

Nodejs 第五十八章(大文件上传)

在现代网站中&#xff0c;越来越多的个性化图片&#xff0c;视频&#xff0c;去展示&#xff0c;因此我们的网站一般都会支持文件上传。 文件上传的方案 大文件上传&#xff1a;将大文件切分成较小的片段&#xff08;通常称为分片或块&#xff09;&#xff0c;然后逐个上传这…...

Linux编译器--gcc/g++的使用

1. gcc与g gcc与g分别是c语言与c代码的编译器&#xff0c;但同时g也兼容c语言。 我们知道在Linux中&#xff0c;系统并不以文件后缀来区分文件类别。但对于gcc与g等编译器而言却是需要的。Linux中c代码文件的后缀是.c&#xff0c;c代码文件的后缀是.cpp(.cc)(.cxx)。 在Linu…...

苍穹外卖-day13:vue基础回顾+进阶

vue基础回顾进阶 课程内容 VUE 基础回顾路由 Vue-Router状态管理 vuexTypeScript 1. VUE 基础回顾 1.1 基于脚手架创建前端工程 1.1.1 环境要求 要想基于脚手架创建前端工程&#xff0c;需要具备如下环境要求&#xff1a; ​ node.js 前端项目的运行环境 学习web阶段已安…...

蓝桥杯/慈善晚会/c\c++

问题描述 热心公益的G哥哥又来举办慈善晚会了&#xff0c;这次他邀请到了巴菲特、马云等巨富&#xff0c;还邀请到了大V、小C等算法界泰斗。晚会一共邀请了n位尊贵的客人&#xff0c;每位客人都位于不同的城市&#xff0c;也就是说每座城市都有且仅有一位客人。这些城市的编号为…...

2024.3.19

思维导图...

【Python】新手入门学习:详细介绍单一职责原则(SRP)及其作用、代码示例

【Python】新手入门学习&#xff1a;详细介绍单一职责原则&#xff08;SRP&#xff09;及其作用、代码示例 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyT…...

【DataWhale学习笔记】使用AgentScope调用qwen大模型

AgentScope AgentScope介绍 AgentScope是一款全新的Multi-Agent框架&#xff0c;专为应用开发者打造&#xff0c;旨在提供高易用、高可靠的编程体验&#xff01; 高易用&#xff1a;AgentScope支持纯Python编程&#xff0c;提供多种语法工具实现灵活的应用流程编排&#xff…...

【C++】手撕AVL树

> 作者简介&#xff1a;დ旧言~&#xff0c;目前大二&#xff0c;现在学习Java&#xff0c;c&#xff0c;c&#xff0c;Python等 > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;能直接手撕AVL树。 > 毒鸡汤&#xff1a;放弃自…...

探索 TorchRe-ID--基于 Python 的人员再识别库

导言 人员再识别&#xff08;re-ID&#xff09;是计算机视觉中的一项重要任务&#xff0c;在监控系统、零售分析和人机交互中有着广泛的应用。TorchRe-ID 是一个功能强大、用户友好的 Python 库&#xff0c;它为人员再识别任务提供了一套全面的工具和模型。在本文中&#xff0…...

鸿蒙Harmony应用开发—ArkTS声明式开发(容器组件:Flex)

以弹性方式布局子组件的容器组件。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。Flex组件在渲染时存在二次布局过程&#xff0c;因此在对性能有严格要求的场景下建议使用Column、Row代替。Flex组…...

tmux最基础的一点应用-不用一直挂着ssh,可以干点别的事情

文章目录 使用原因基础命令创建一个窗口退出当前窗口重新进入万一忘记了环境名字想要删除环境 使用原因 跑程序要很久&#xff0c;需要干别的事情&#xff0c;电脑不能一直开&#xff0c;可以使用tmux来管理。 基础命令 创建一个窗口 tmux new -s <你自己起的环境名字&g…...

Java推荐算法——特征加权推荐算法(以申请学校为例)

加权推荐算法 文章目录 加权推荐算法1.推荐算法的简单介绍2.加权推荐算法详细介绍3.代码实现4.总结 1.推荐算法的简单介绍 众所周知&#xff0c;推荐算法有很多种&#xff0c;例如&#xff1a; 1.加权推荐&#xff1a;分为简单的特征加权&#xff0c;以及复杂的混合加权。主要…...

探索什么便签软件好用,可以和手机同步的便签软件

在信息技术日新月异的今天&#xff0c;各类数字工具已经成为我们生活与工作的重要助手。便签软件作为一种简单却高效的辅助工具&#xff0c;悄然改变着人们的记录习惯与时间管理方式。而在诸多便签软件中&#xff0c;能够实现手机与电脑同步功能的产品尤显其独特的价值。那么&a…...

字符函数与字符串函数

前言 本次博客可以说内容最为多的一次博客&#xff0c;讲解同样很细致大家好好看看 1字符函数 在讲解字符函数时,大家得了解什么是字符吧 普通字符a b c 1 转义字符 \n 换行‘ \t’ 水平制表符\r回车 大家了解即可 在C语言中字符也可以有分类 所以我们先来看看…...

Kubernetes 项目整体布局 el-container

整体布局整体布局 你可能会去敲不同的项目&#xff0c;有很多种平台。那么其实都是可以复用的。唯一不同的就是main里面的内容是不同的&#xff0c;边框架子都是相同的。其实框架是不怎么变化的&#xff0c;变化的是main里面。 src/layout/Layout.vue 这里需要新增一个页面Lay…...

AI赋能写作:AI大模型高效写作一本通

❤️作者主页&#xff1a;小虚竹 ❤️作者简介&#xff1a;大家好,我是小虚竹。2022年度博客之星评选TOP 10&#x1f3c6;&#xff0c;Java领域优质创作者&#x1f3c6;&#xff0c;CSDN博客专家&#x1f3c6;&#xff0c;华为云享专家&#x1f3c6;&#xff0c;掘金年度人气作…...

unraid docker.img扩容

unraid 弹Docker image disk utilization of 99%&#xff0c;容器下载/更新失败 我的版本是6.11.5&#xff0c;docker.img满了导致容器不能更新&#xff0c;遇到同样问题的可以先用docker命令清除一下仓库(当然不一定能清理出来&#xff0c;我已经清理过只清理出来1G多点&…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

华为OD机试-食堂供餐-二分法

import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...