【常见的六大排序算法】插入排序、希尔排序、选择排序、冒泡排序、堆排序、快速排序

在这里插入图片描述

个人主页
创作不易,感谢大家的关注!

在这里插入图片描述
在这里插入图片描述

文章目录

    • 前言
  • 🎡一、插入排序
  • 🌲二、希尔排序
  • 🎉三、选择排序
  • 🎀四、冒泡排序
  • 🚘五、堆排序
  • 🛵六、快速排序
    • 1. Hoare版本
    • 2. 挖坑法
    • 3. 前后指针法
    • 4. 非递归实现

前言

在实现排序前,我们要先知道什么是排序。排序:简单的来说就是把一串数据按照一定的方式依次排序。例如:可以按照数字的大小升序或降序排列,或者按照英文字母的先后顺序排列等。使用这一系列的方式,就可以将一串无序状态下的数据排列成有序的数据。

🎡一、插入排序

  1. 基本思路

    1. 默认第一个元素为有序的,从第二个元素开始排序。
    2. 取出下一个元素tmp,往前进行比较。
    3. 如果该元素比tmp大,则将该元素往后移动一位,直到找到比tmp小于或者等于的元素。
    4. 找到比tmp小于或者等于的元素,将tmp插入到该元素的下一位。
    5. 不断重复上述步骤。
  2. 动图演示:
    在这里插入图片描述

  3. 时间复杂度: 最坏情况下为 O(N ^ 2),此时待排序的序列状况为逆序或者接近逆序。最好情况下为 O(N),此时待排序列为升序,或者说接近升序。

  4. 空间复杂度: O(1)。

代码实现:

// 插入排序
void InsertSort(int* a, int n)
{//遍历数组for (int i = 0; i < n - 1; i++){//记录有序序列最后一个元素的下标int end = i;int tmp = a[end + 1];while (end >= 0){	//比插入的数大就往后移动if (a[end] > tmp){a[end + 1] = a[end];--end;}else{//比插入的数小就退出循环break;}}//将tmp放到比插入的数小的后面a[end + 1] = tmp;}
}

🌲二、希尔排序

  1. 基本思路

    希尔排序是插入排序的一个优化方案,其本质上还是插入排序。但它们的时间复杂度却并不相同。

    1. 先将待排序列进行预排序,使得待排序列接近有序,然后再进行插入排序。
    2. 将待排序的数据分为多个组,使每组间隔gap为2或3…。
    3. 如果第一个元素大于最后一个元素,则将它们两个元素进行交换。
    4. 不断重复上述操作,直到每组间隔只有1时,说明所有的数据已经完成排序。
  2. 动图演示:在这里插入图片描述

  3. 时间复杂度: O(N ^ 1.3)。

  4. 空间复杂度: O(1)。

代码实现:

// 希尔排序
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){// +1保证当n的值小于3时,gap最低为1,依次进行插入排序gap = gap / 3 + 1;for (size_t i = 0; i < n - gap; i += gap){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end = end - gap;}else{break;}}a[end + gap] = tmp;}}
}

🎉三、选择排序

  1. 基本思路
    1. 从待排序序列中选出最小值mini,放在序列的起始位置。
    2. 每次遇到比mini小的值就更新mini,直到遍历完整个序列。
    3. 然后将该值放到序列的排列好的有序序列的下一个位置。
    4. 重复上述步骤,直到待排序只剩下一个元素,说明排序完成。
  2. 动图演示:
    在这里插入图片描述
  3. 时间复杂度: O(N^2)。有n个数,每趟选一个最大或最小值,需要选n趟。
  4. 空间复杂度: O(1)。

代码实现

// 选择排序
void SelectSort(int* a, int n)
{//定义一个begin和end分别指向数组的头下标和尾下标int begin = 0;int end = n - 1;while (begin < end){//定义mini和begin分别表示最小值和最大值的下标int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; i++){if (a[i] > a[maxi])maxi = i;if (a[i] < a[mini])mini = i;}Swap(&a[begin], &a[mini]);//需要注意的是,当最大值在最小值位置的时候,a[maxi]的值会与a[mini]的值进行交换,因此需要提前将maxi置为miniif (begin == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);begin++;end--;}
}

总结: 效率相对较低,实际中很少使用。

🎀四、冒泡排序

  1. 基本思路
    根据序列中两个记录键值的比较结果来交换这两个记录在序列中的位置,一前一后两个下标的值进行比较,如果前一个值比后一个值大就进行交换。
  2. 动图演示:在这里插入图片描述
  3. 时间复杂度: O(N ^2)。该排序每次都要和相邻的两个数进行比较,最坏情况下比较n次,跑n躺。
  4. 空间复杂度: O(1)。

代码实现:

// 冒泡排序
void BubbleSort(int arr[], int n)
{for (int i = 0; i < n - 1; i++){//假设没有发生判断,如果发生判断,就将flag置为,否则就退出int flag = 0;for (int j = 0; j < n - 1 - i; j++){int tmp = 0;tmp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tmp;flag = 1;}if (flag == 0){break;}}
}

结论: 该排序效率低下,实际中几乎不使用。

🚘五、堆排序

  1. 基本思路
    将一组无序的数据,按照升序或降序的方式对其进行排序。
    注意: 在堆排序中,升序建大堆,降序建小堆。 因为堆排序的逻辑是将根节点与最后一个节点依次发生交换。不断交换,大堆排序完,堆尾的数据就是最大的值,并且不断向堆顶的数据依次缩小;相反,小堆排序完后,堆尾的数据就是最小的值,并不断向堆顶的数据依次增大。
  2. 图片演示:**在这里插入图片描述
  3. 时间复杂度: O(N * log(N))堆排序建堆的时间复杂度为O(N),但是选数时都需要将堆顶和堆尾的数据进行交换,而堆的高度是log(N),而建堆的时间复杂的可以忽略不计,因此为O(N * log(N))。
  4. 空间复杂度: O(1)。

代码实现:

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}// 向下调整排序
void AdjustDown(int* a, int n, int parent)
{//假设左孩子大int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
//假设使用建小堆的方法
void HeapSort(int* a, int n)
{int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

总结: 排序效率高,实际中也可以使用。

🛵六、快速排序

一般我们使用快速排序方法的顺序:挖坑法 -> Hoare -> 前后指针法。

1. Hoare版本

  1. 基本思路
    1. 选出一个key,一般在最左边或在最右边。
    2. 定义一个begin为序列的头和end为序列的尾,begin从左向右开始走,end从右向左进行走。(注意: 如果选择最左边的数据为key,则需让end先走;若选择右边的数据为key,则让begin先走)
    3. 假设最左边为key,end开始先走。在走的过程中,如果end遇到比key小的数据,就停下,然后让begin开始走,直到begin遇到比key大的数据就停下,然后将begin里的值和end里的值进行交换,然后又继续从end开始先走,不断循环往复,直到begin和end相遇,则将相遇点的内容和key进行交换即可。
    4. 此时,key左边的数据都是小于key的,key右边的数据都是大于key的,说明key已在序列中排好序了。
    5. 因此,序列中划分出了三个区间,分别为 [left, key - 1],key,[key + 1, right] 这三个区间,然后不断对[left, key - 1]和[key + 1, right]这两个区间重复上述步骤,直到所有的key都排好序。
  2. 单趟的动图演示如下:
    在这里插入图片描述
    代码实现:
// 快速排序
void QuickSort(int* a, int left,int right)
{//只有一个数或区间不存在if (left >= right){return;}int begin = left, end = right;while (begin < end){//右边找小,begin < end是为了防止越界while (begin < end && a[end] >= a[keyi]){end--;}//左边找大while (begin < end && a[begin] <= a[keyi]){++begin;}//小的换到右边,大的换到左边Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);// [left,keyi-1] keyi [keyi+1,right],使用递归的方法QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}

代码优化:
在实际中,我们发现:快速排序在有序或接近有序数组中完成排序的效率低下。因此我们可以采用每次都取大小中等的值来作为数组中最左边的key,这样可以有效提升代码的运行效率,减少循环的次数。

// 三数取中
int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right])return midi;else if (a[left] < a[right])return right;else{return left;}}// a[left] > a[midi]else{if (a[midi] > a[right])return midi;// a[midi] < a[right]else if (a[left] < a[right])return left;elsereturn right;}
}

2. 挖坑法

  1. 基本思路
    1. 选出最左边的元素存入key中,在此位置中形成一个坑位。
    2. 定义left从左到右开始遍历,定义right从右向左开始遍历。
    3. 当right遍历找到比key小的数据,就放入left当中的位置。
    4. 当left遍历找到比key大的数据,就放入right当中的位置
    5. 如果left和right下标相遇,则把key中的数据放入相交处。
  2. 单趟动图演示:
    在这里插入图片描述
    代码实现:
//挖坑法
int QuickSort1(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);midi = left;int key = a[midi];while (left < right){// 左右开始遍历while (left < right && a[right] >= key){--right;}a[midi] = a[right];midi = right;while (left < right && a[left] <= key){++left;}a[midi] = a[left];midi = left;}a[midi] = key;return midi;
}

3. 前后指针法

  1. 基本思路
    1. 定义key来存储数组中最左边的数据,perv指向数组开始的位置,cur指向prev的下一个位置。
    2. 当cur下标中的元素小于key时,则让prev开始往后走。如果此时prev下标中的元素不等于cur下标中的元素,则两者进行交换。
    3. 否则cur一直往下走,当cur走完时,将prev下表中的元素和key中的数据进行交换
    4. 不断重复上述操作。
  2. 单趟动图演示:
    在这里插入图片描述
    代码实现:
//前后指针法
int QuickSort2(int* a, int left, int right)
{assert(a);int keyi = GetMidi(a, left, right);Swap(a[keyi], a[left]);keyi = left;int prev = left;int cur = prev + 1;while (cur <= right && a[cur] < a[keyi]){++prev;++cur;}while (cur <= right){while (cur <= right && a[cur] >= a[keyi]){++cur;}if (cur <= right){++prev;Swap(a[prev], a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);return prev;
}

4. 非递归实现

基本思路
1. 使用栈的形式,模拟递归实现
2. 因为每次都要对序列的左右边界进行传入,根据栈的性质:先进后出,后进先出。因此,我们要先传入左边界,再传入右边界,获取数据时要先取右边界,在获取左边界。
3. 注意:获取数据后要及时删除,避免影响栈头结点的数据。

代码实现:

// 非递归方法
void QuickSort3(int* a, int begin, int end)
{assert(a);Stack ST;StackInit(&ST);StackPush(&ST, begin);StackPush(&ST, end);while (!StackEmpty(&ST)){int right = StackTop(&ST);StackPop(&ST);int left = StackTop(&ST);StackPop(&ST);if (left >= right){continue;}int keyi = QuickSort2(a, left, right);StackPush(&ST, keyi + 1);StackPush(&ST, right);StackPush(&ST, left);StackPush(&ST, keyi - 1);}
}

今天的分享就到这里啦,后续我还会新增一个排序算法-------归并排序,希望这篇文章可以帮助大家解决排序算法中的问题。我们下次再见,拜拜啦!在这里插入图片描述

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

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

相关文章

VLAN的概念及优势

文章目录 VLAN的概念及优势分割广播域 广播域vlanVLAN的优势 VLAN的种类静态VLAN动态VLAN 静态VLAN的配置静态VLAN范围配置静态VLAN的步骤 TRUNK介绍与配置三层交换机转发原理三层交换技术mls基于CEF的MLSCEF是一种基于拓补转发的模型 三层交换机的配置层 VLAN的概念及优势 分…

使用onnxruntime加载YOLOv8生成的onnx文件进行目标检测

在网上下载了60多幅包含西瓜和冬瓜的图像组成melon数据集&#xff0c;使用 LabelMe 工具进行标注&#xff0c;然后使用 labelme2yolov8 脚本将json文件转换成YOLOv8支持的.txt文件&#xff0c;并自动生成YOLOv8支持的目录结构&#xff0c;包括melon.yaml文件&#xff0c;其内容…

C++的第一道门坎:类与对象(二)

目录 一.类中生成的默认成员函数详解 0.类的6个默认成员函数 1.构造函数 1.1概念 1.2特性 2.析构函数 2.1概念 2.2特性 3.拷贝构造函数 3.1概念 3.2特性 3.3拷贝构造的使用方法 4.运算符重载 5.赋值运算符重载 6.const修饰函数 7.取地址及const取地址操作符重载…

【漯河市人才交流中心_登录安全分析报告-Ajax泄漏滑动距离导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…

Windows10(家庭版)中DockerDesktop(docker)的配置、安装、修改镜像源、使用

场景 Windows10中Docker的安装与遇到的那些坑: Windows10中Docker的安装与遇到的那些坑_在 docker.core.logging.httpclientexceptionintercept-CSDN博客 上面讲Docker Desktop在windows10非家庭版上的安装&#xff0c;如果是家庭版&#xff0c;则需要执行如下步骤。 注&am…

【python】OpenCV—Tracking(10.2)

文章目录 BackgroundSubtractorcreateBackgroundSubtractorMOG2createBackgroundSubtractorKNN BackgroundSubtractor Opencv 有三种背景分割器 K-Nearest&#xff1a;KNN Mixture of Gaussian&#xff08;MOG2&#xff09; Geometric Multigid&#xff08;GMG&#xff09; …

K210视觉识别模块学习笔记4: 训练与使用自己的模型_识别字母

今日开始学习K210视觉识别模块: 模型训练与使用_识别字母 亚博智能的K210视觉识别模块...... 固件库: maixpy_v0.6.2_52_gb1a1c5c5d_minimum_with_ide_support.bin 文章提供测试代码讲解、完整代码贴出、测试效果图、测试工程下载 这里也算是正式开始进入到视觉识别的领域了…

matplotlib ---词云图

词云图是一种直观的方式来展示文本数据&#xff0c;可以体现出一个文本中词频的使用情况&#xff0c;有利于文本分析&#xff0c;通过词频可以抓住一篇文章的重点 本文通过处理一篇关于分析影响洋流流向的文章&#xff0c;分析影响洋流流向的主要因素都有哪些 文本在文末结尾 …

基于Freertos的工训机器人

一. 工训机器人 V1 1. 实物 将自制的F4开发板放置车底板下方&#xff0c;节省上方空间&#xff0c;且能保证布线方便整齐。 2. SW仿真 使用SolidWorks进行仿真&#xff0c;且绘制3D打印件。 工训仿真 3.3D打印爪测试 机械爪测试 二. 工训机器人 V2 1. 实物 工训机器人V2不同于…

IDEA 打开项目后看不到项目结构怎么办?

1、先把这个项目从 IDEA 中移除 2、再重新打开或导入 3、如果还没有解决&#xff0c;就先把这个项目拷贝出来把原来的路径上的项目给删除&#xff0c;然后再把拷贝后的项目放在一个路径下&#xff0c;再打开就可以了

沟通程序化(1):跟着鬼谷子学沟通—“飞箝”之术

沟通的基础需要倾听&#xff0c;但如果对方听不进你的话&#xff0c;即便你说的再有道理&#xff0c;对方也很难入心。让我们看看鬼谷子的“飞箝”之术能给我们带来什么样的启发吧&#xff01; “飞箝”之术&#xff0c;源自中国古代兵法家、纵横家鼻祖鬼谷子的智慧&#xff0…

​LabVIEW超声波检测

LabVIEW超声波检测 在现代工业生产和科学研究中&#xff0c;超声检测技术因其无损性、高效率和可靠性而被广泛应用于材料和结构的缺陷检测。然而&#xff0c;传统的超声检测仪器往往依赖于操作者的经验和技能&#xff0c;其检测过程不够智能化&#xff0c;且检测结果的解读具有…

Appium系列(2)元素定位工具appium-inspector

背景 如实现移动端自动化&#xff0c;依赖任何工具时&#xff0c;都需要针对于页面中的元素进行识别&#xff0c;通过识别到指定的元素&#xff0c;对元素进行事件操作。 识别元素的工具为appium官网提供的appium-inspector。 appium-inspector下载地址 我这里是mac电脑需要下…

使用Python突破网站验证码限制

之前有小伙伴说&#xff0c;在web自动化的过程中&#xff0c;经常会被登录的验证码给卡住&#xff0c;不知道如何去通过验证码的验证&#xff0c;今天专门给大家来聊聊验证码的问题。 常见的验证码一般分为两类&#xff0c;一类是图文验证码&#xff0c;一类是滑块验证码&#…

vue2+antv/x6实现er图

效果图 安装依赖 npm install antv/x6 --save 我目前的项目安装的版本是antv/x6 2.18.1 人狠话不多&#xff0c;直接上代码 <template><div class"er-graph-container"><!-- 画布容器 --><div ref"graphContainerRef" id"gr…

SpringCloud如何实现SSO单点登录?

目录 一、SpringCloud框架介绍 二、什么是SSO单点登录 三、单点登录的必要性 四、SpringCloud如何实现SSO单点登录 一、SpringCloud框架介绍 Spring Cloud是一个基于Spring Boot的微服务架构开发工具集&#xff0c;它整合了多种微服务解决方案&#xff0c;如服务发现、配置…

es的总结

es的collapse es的collapse只能针对一个字段聚合&#xff08;针对大数据量去重&#xff09;&#xff0c;如果以age为聚合字段&#xff0c;则会展示第一条数据&#xff0c;如果需要展示多个字段&#xff0c;需要创建新的字段&#xff0c;如下 POST testleh/_update_by_query {…

C#WPF数字大屏项目实战07--当日产量

1、第2列布局 第2列分三行&#xff0c;第一行分6列 2、当日产量布局 3、产量数据布局 运行效果 4、计划产量和完成度 运行效果 5、良品率布局 1、添加用户控件 2、用户控件绘制圆 2、使用用户控件 3、运行效果 4、注意点 这三个数值目前是静态的&#xff0c;可以由后台程序项…

构建高效稳定的短视频直播系统架构

随着短视频直播的迅猛发展&#xff0c;构建一个高效稳定的短视频直播系统架构成为了互联网企业的重要挑战。本文将探讨如何构建高效稳定的短视频直播系统架构&#xff0c;以提供优质的用户体验和满足日益增长的用户需求。 ### 1. 短视频直播系统的背景 短视频直播近年来蓬勃发…

ARM-V9 RME(Realm Management Extension)系统架构之系统安全能力的信任根服务

安全之安全(security)博客目录导读 目录 一、信任根服务 1、非易失性存储 2、根看门狗 3、随机数生成器 4、加密服务 5、硬件强制安全性 本节定义了系统架构必须支持的一般安全属性和能力&#xff0c;以确保RME安全性。 本章扩展了可能属于系统认证配置文件的一部分的其…