【CPP】选择排序:冒泡排序、快速排序

目录

  • 1.冒泡排序
      • 简介
      • 代码
      • 分析
  • 2.快速排序
    • 2.1霍尔版本
      • 简介
      • 代码
      • 分析
    • 2.2挖坑版本
    • 2.3前后指针版本
    • 2.4非递归的快排
      • 思路
      • 代码

什么是交换排序?
基本思想:所谓 交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。
其中,冒泡排序快速排序 均属于 交换排序

1.冒泡排序

简介

略。
在这里插入图片描述

代码

在这里插入图片描述

分析

最好的时间复杂度:O(N)
最差的时间复杂度:O(N^2)

2.快速排序

基本思想:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

下面是不同版本的快速排序:

2.1霍尔版本

简介

概述:快速排序属于交换排序的一种,是Hoare于1962年提出的一种二叉树结构的交换排序方法

在这里插入图片描述

思路:

  • 先选定key值,右边先走。
  • 右边找小,左边找大,左右交换
  • 重复第二步,直到left和right相遇与key进行交换

问:为什么相遇位置一定比key值小???
答:因为右边先走决定的。
分析:相遇有两种情况:

  • right 遇 left
    这时候相遇点是 left选定的位置
    • 假如说left是已经走过的,left是找大的,但是找到大之后会与right交换,所以left此时是小值。 汇合点是小值。
    • 假如说left一次都没有走过,right一路“滑铁卢”走到left的起始位置,left的起始位置是key值本身,汇合点是key值,key自己与自己交换没有影响。
  • left 遇 right
    能让left找到right,可以说明right已经找到了小,并且此时值并没有发生交换(因为右边先走!),然后此时right是小值,left遇到了right,汇合点也一定是小值。

代码

在这里插入图片描述

分析

这个版本的快排细节比较多,主要有下面坑:

  • left = begin + 1,问题就是当原数组恰好就是有序的时候反而用了快排会被打乱顺序。
  • while(left < right) 相遇即停止,写成小于等于那很容易造成越界问题。
  • while(left < right && arr[right] >= arr[keyi])
    • 容易造成左右指针错过问题
    • 容易导致arr[left] = arr[right] = arr[keyi]死循环问题
  • keyi = left;要及时更新keyi值,因为对于不同的递归下keyi值都是不同的。


快排与希尔排序:

  • 快排与希尔排序是一个量级的,在数据量巨大的情况下,
    • 若重复数据比较多,快排比较快一点;
    • 若重复数据比较少,希尔排序更快一点。
  • 然而序列有序情况下,快排很吃亏,很慢。

序列有序情况下,快排效率低下的原因分析及解决方法:
在这里插入图片描述
有序序列快排时间复杂度:O(N^2)
理想序列快排时间复杂度:O(N*logN)
总结来看,就是因为在有序序列情况下,快排每次的keyi值都是第一个数导致效率编程>了N^2的情况。注:如果是有序序列,几千的数就会因为递归深度太深而挂掉,因为要递归几千次。

结论:所以我们把keyi值选择不固定即可,可以随机选keyi值也可以三数取中(begin,end,mid)取中间值的下标。

解决方案:①三数取中 或 ②随机数选key
在这里插入图片描述

优化:小区间优化
在上面所说的排序中,其中最后三排的数字占了整个序列的大概百分之八十左右,也就是说为了最后三排的数字排序 多调用栈帧百分之八十左右
小区间优化:用插入排序进行优化(插入排序的小区间适应性更好)。
在这里插入图片描述

实际上,在DeBug环境下,效率大概可以略提升一些,感觉有十分之一吧。
在Release环境下,因为编译器对函数栈帧优化作用极大,以至于小区间优化的作用约等于没有,甚至不如没有小区间优化的版本。
正确代码:
在这里插入图片描述

void quickSort(int* arr, int begin, int end) /** begin指区间起始下标,end指区间最后数字下标 */ // 希望[begin,end]有序
{if (begin >= end) return; //begin > end 没有实际意义 ; begin == end 仅有一个数,当作keyi就结束了if (end - begin + 1 < 10) insertSort(arr + begin, end - begin + 1); // 小区间优化else{// 1.先控制单趟快排,希望[begin,key-1] < [key+1,end]int right = end;int left = begin;int midi = getMidi(arr, begin, end);swap(&arr[midi], &arr[begin]);int keyi = begin;while (left < right) // 相遇停止{while (left < right && arr[right] >= arr[keyi]) right--;while (left < right && arr[left] <= arr[keyi]) left++;swap(&arr[right], &arr[left]);}// 交换swap(&arr[keyi], &arr[left]);keyi = left;//更新下一个递归的keti值// 2.再控制整体多个递归quickSort(arr, begin, keyi - 1);quickSort(arr, keyi + 1, end);}
}

思考:为什么这个代码会有问题?
在这里插入图片描述
在这里插入图片描述

2.2挖坑版本

在这里插入图片描述
思路:

  • key先形成坑位
  • 右边先走,找到比key小的,放到左边的坑位
  • 左边再走,找道比key大的,放到右边的坑位
  • 直到left和right相遇

\

// 挖坑法
int PartSort2(int* a, int begin, int end)
{int midi = getMidi(a, begin, end);swap(&a[midi], &a[begin]);int key = a[begin];int hole = begin;while (begin < end){// 右边找小,填到左边的坑while (begin < end && a[end] >= key){--end;}a[hole] = a[end];hole = end;// 左边找大,填到右边的坑while (begin < end && a[begin] <= key){++begin;}a[hole] = a[begin];hole = begin;}a[hole] = key;return hole;
}

2.3前后指针版本

在这里插入图片描述
思路:cur是一个评判数字要掠过还是交换的角色,prev是一个保证其走过的路都是小值得一个角色。

  • 选定key值,cur先走
  • cur找到小值,prev++,cur与prev的值交换;cur++
  • cur找到大值,cur++;
int PartSort3(int* a, int begin, int end)
{int midi = getMidi(a, begin, end);swap(&a[midi], &a[begin]);int key = begin;int cur = begin + 1;int prev = begin;while (cur <= end){/*if (a[cur] < a[key]) {prev++; swap(&a[prev], &a[cur]);}*/if (a[cur] < a[key] && ++prev != cur) swap(&a[prev], &a[cur]);cur++;}swap(&a[prev], &a[key]);return prev;
}

2.4非递归的快排

思路

用循环写快排,只需要模拟递归的过程即可。
在这里插入图片描述

代码

在这里插入图片描述


EOF

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/355547.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Photoshop揭秘:图像处理领域的领军软件

Photoshop 是一款由 Adobe 企业开发的图像处理软件&#xff0c;也被大家简称为 PS。在广告设计、摄影后期、数字绘画、网页设计等各个领域都得到了广泛的应用&#xff0c;是目前业界最受欢迎的图像处理软件之一。作为一款图像处理软件&#xff0c;Photoshop 为设计者提供了许多…

爆火的AI姓名头像号篇篇10w+, 流量主赚麻了...

最近二师兄在刷公众号时&#xff0c;看到一个非常有趣的账号。简单又“暴li”。 几乎篇篇10w。点击去一看&#xff0c;内容也是非常极简&#xff0c;利用姓氏生成头像。一个字都不多。 几乎每篇文末都有广告&#xff0c;一篇10w按照800来算&#xff0c; 一个月大概 ~~一七得七、…

华为手机怎么找回删除的照片?掌握3个方法,恢复不是梦

由于误删、设备故障、软件更新等原因&#xff0c;我们有时可能会不慎丢失这些宝贵的照片。当面对空空如也的相册时&#xff0c;那种失落感无法言喻。华为手机该怎么找回删除的照片呢&#xff1f;但是&#xff0c;请不要绝望&#xff01;在科技的帮助下&#xff0c;我们可以采取…

threejs 光影投射-与场景进行交互(六)

效果 场景中有三个立方体,三种颜色.点击变成红色,再点恢复自身原有颜色 代码 import ./style.css import * as THREE from three import { OrbitControls } from three/examples/jsm/controls/OrbitControls.js import { log } from three/examples/jsm/nodes/Nodes.js//…

NGINX_十二 nginx 地址重写 rewrite

十二 nginx 地址重写 rewrite 1 什么是Rewrite Rewrite对称URL Rewrite&#xff0c;即URL重写&#xff0c;就是把传入Web的请求重定向到其他URL的过程。URL Rewrite最常见的应用是URL伪静态化&#xff0c;是将动态页面显示为静态页面方式的一种技术。比如 http://www.123.com…

基于淘宝商城用户购物行为数据分析系统

摘 要 在电商行业高速发展的今天&#xff0c;用户购物行为数据量呈指数型增长&#xff0c;传统的数据处理架构已经无法满足于现如今的数据处理需求。针对于这样的需求本课题设计了一种基于淘宝的用户购物行为分析系统&#xff0c;旨在通过对大量数据进行分析处理进而深入研究用…

视频剪辑技巧大揭秘:轻松掌握为视频添加梦幻光晕效果的绝妙方法!

在这个视觉盛宴的时代&#xff0c;每一个画面都渴望被赋予独特的魅力与魔法。今天&#xff0c;我要为你揭秘一个神秘的视频剪辑技巧——给视频添加光晕效果&#xff0c;让你的作品瞬间脱颖而出&#xff0c;成为朋友圈的焦点 首先&#xff0c;你可以打开原视频进行查看。此时&am…

【Kafka】Kafka生产者数据重复、数据有序、数据乱序-07

【Kafka】Kafka生产者数据重复、数据有序、数据乱序-07 1. 数据重复1.1 数据传递语义1.2 幂等性1.2.1 如何开启幂等性1.2.2 同一个消息&#xff0c;多个分区都会存在吗&#xff1f; 1.3 事务1.3.1 Kafka 事务原理1.3.2 Kafka事务的作用和意义作用具体应用场景 2. 数据有序3. 数…

FP7195做大功率钓鱼灯应用方案,0.1%深度无极无频闪调光调色应用,调光曲线顺滑无突兀

文章目录 文章目录 方案背景 一、夜钓灯电路框架 二、FP7195芯片介绍 芯片参数 总结 方案背景 目前夜钓正在逐渐变得时尚起来&#xff0c;随着夜钓群体的年轻化&#xff0c;人们对于夜钓灯的审美要求也越来越高。夜钓灯作为夜间钓鱼的重点装备&#xff0c;不仅仅需要高质量的光…

足底筋膜炎的症状

足底筋膜炎是足底的肌腱或者筋膜发生无菌性炎症所致&#xff0c;其症状主要包括&#xff1a; 1、疼痛&#xff1a;这是足底筋膜炎最常见和突出的症状。疼痛通常出现在足跟或足底近足跟处&#xff0c;有时压痛较剧烈且持续存在。晨起时或长时间不活动后&#xff0c;疼痛感觉尤为…

重生奇迹MU整理装备注意事项

想成为奇迹MU的顶尖玩家&#xff0c;整理装备是必不可少的一项技能。在这篇文章中&#xff0c;我们将为您分享一些整理装备的注意事项与技巧&#xff0c;帮助您在游戏中更好地管理装备&#xff0c;提升你的实力。 整理装备&#xff0c;须知几点 整理装备是每位玩家必须完成的…

Scikit-Learn梯度提升决策树(GBDT)

Scikit-Learn梯度提升决策树 1、梯度提升决策树(GBDT)1.1、Boosting方法1.2、GBDT的原理1.3、GBDT回归的损失函数1.4、梯度下降与梯度提升1.5、随机森林与GBDT1.6、GBDT的优缺点2、Scikit-Learn梯度提升决策树(GBDT)2.1、Scikit-Learn GBDT回归2.1.1、Scikit-Learn GBDT回归…

GNSS边坡监测站

TH-WY1随着科技的飞速发展&#xff0c;各种先进的监测技术不断涌现&#xff0c;为边坡安全监测提供了有力保障。其中&#xff0c;GNSS边坡监测站以其高精度、实时性强的特点&#xff0c;受到了广泛关注。 GNSS边坡监测站&#xff0c;全称为全球导航卫星系统边坡监测站&#xf…

3D Gaussian Splatting Windows安装

0.安装C++ 编译器 https://aka.ms/vs/17/release/vs_buildtools.exe 1.下载源码 git clone https://github.com/graphdeco-inria/gaussian-splatting --recursive 2.安装cuda NVIDIA GPU Computing Toolkit CUDA Toolkit Archive | NVIDIA Developer 3.安装COLMAP

卓越的 App UI 风格引领潮流

卓越的 App UI 风格引领潮流

【C++】哈希的概念及STL中有关哈希容器的使用

目录 前言一、unordered系列关联式容器1.1 标准库中的unordered_set1.1.1 unordered_set的介绍1.1.2 unordered_set的常用接口说明1.1.2.1 unordered_set对象的常见构造1.1.2.1.1 [无参构造函数](https://legacy.cplusplus.com/reference/unordered_map/unordered_map/)1.1.2.1…

探索序列到序列模型:了解编码器和解码器架构的强大功能

目录 一、说明 二、什么是顺序数据&#xff1f; 三、编码器解码器架构的高级概述&#xff1a; 3.1 编码器和解码器架构的简要概述&#xff1a; 3.2 训练机制&#xff1a;编码器和解码器架构中的前向和后向传播&#xff1a; 四、编码器解码器架构的改进&#xff1a; 4.1.…

Spring自定义标签体系和应用

我们知道&#xff0c;在使用Dubbo框架时&#xff0c;需要指定配置文件中的application、protocol、registry、provider、service等服务器端和客户端的配置项&#xff0c;典型的配置方法如下所示。通过这些配置项&#xff0c;我们可以基于Spring容器来启动Dubbo服务。 <!-- …

SpringBoot 实现RequestBodyAdvice封装统一接受类功能

一、相关往期文章 SpringBootVue实现AOP系统日志功能_aop的vue完整项目 Spring AOP (面向切面编程&#xff09;原理与代理模式—实例演示_面向切面aop原理详解 二、需求分析 按照一般情况&#xff0c;统一接受类可以像以下的方式进行处理&#xff1a; 如果不想使用 Request…

Shiro721 反序列化漏洞(CVE-2019-12422)

目录 Shiro550和Shiro721的区别 判断是否存在漏洞 漏洞环境搭建 漏洞利用 利用Shiro检测工具 利用Shiro综综合利用工具 这一篇还是参考别的师傅的好文章学习Shiro的反序列化漏洞 上一篇也是Shiro的反序列化漏洞&#xff0c;不同的是一个是550一个是721&#xff0c;那么这…