【八大排序】冒泡排序 | 快速排序 + 图文详解!!

在这里插入图片描述

📷 江池俊: 个人主页
🔥个人专栏: ✅数据结构冒险记 ✅C语言进阶之路
🌅 有航道的人,再渺小也不会迷途。


在这里插入图片描述

文章目录

    • 交换排序
    • 一、冒泡排序
      • 1.1 算法步骤 + 动图演示
      • 1.2 冒泡排序的效率分析
      • 1.3 代码实现
      • 1.4 冒泡排序特性总结
    • 二、快速排序
      • ✨为什么要三数取中?
      • ✨为什么要进行小区间优化?
      • 2.1 hoare版本 + 动图演示
      • 2.2 挖坑法 + 动图演示
      • 2.3 前后指针法 + 动图演示
      • 2.4 快排的`非递归`
      • 2.5 快速排序特性总结

在这里插入图片描述

交换排序

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


一、冒泡排序

冒泡排序(Bubble Sort)是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。

冒泡排序有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

1.1 算法步骤 + 动图演示

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

在这里插入图片描述

1.2 冒泡排序的效率分析

  1. 什么时候最快?
    当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。

  2. 什么时候最慢?
    当输入的数据是反序时(写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗)。

1.3 代码实现

void Swap(int* p1, int* p2)
{int temp = *p1;*p1 = *p2;*p2 = temp;
}// 冒泡排序
// 时间复杂度:O(N^2)
// 最好情况是多少:O(N)
void BubbleSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){bool exchange = false;for (int j = 1; j < n - i; j++){if (a[j - 1] > a[j]){Swap(&a[j - 1], &a[j]);exchange = true;}}if (exchange == false)break;}
}

1.4 冒泡排序特性总结

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:稳定

二、快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

建议:此处优化内容可以在学完一两个快排思路后再进行观看。
快速排序优化:

  1. 三数取中法选key(即尽可能将不大不小的数作为基准数)
  2. 递归到小的子区间时,可以考虑使用插入排序(小区间优化)

✨为什么要三数取中?

  1. 减少最坏情况发生的概率:在快速排序中,如果每次选择的基准值都是当前序列中的最大或最小元素,那么将导致最坏情况的发生,即每次划分只能将原序列分为两个子序列,一个为空,另一个几乎包含所有剩余元素。这种情况下,快速排序的时间复杂度会退化到O(n^2)。通过三数取中,可以减少选择到极端值作为基准值的可能性,从而提高算法的平均性能。
  2. 提高算法的稳定性:三数取中的方法通常涉及选取序列的左端、中间和右端三个元素,然后从中选择一个值作为基准值。这样的方法能够更好地反映整个序列的中位数,从而使得划分更加均衡。
  3. 适应不同的数据分布:不同的数据分布对基准值的选择有不同的影响。三数取中的方法能够在一定程度上适应不同的数据分布,提高算法的普适性和鲁棒性。

总的来说,三数取中是快速排序中的一种优化策略,旨在通过选择一个更好的基准值来提高排序效率,减少最坏情况的发生概率,并使算法更加稳定和鲁棒。

【三数取中代码实现】

算法步骤

  1. 首先,计算数组的中间位置midi
  2. 判断中间值与首尾值的关系,根据不同的关系来决定返回哪个值作为基准值。
  3. 如果首值大于中间值,则:
    • 如果中间值大于尾值,返回中间值。
    • 否则,如果首值大于尾值,返回尾值。
    • 否则,返回首值。
  4. 如果首值小于等于中间值(即a[begin] <= a[midi]),则:
    • 如果中间值小于尾值,返回中间值。
    • 否则,如果首值小于尾值,返回尾值。
    • 否则,返回首值。
// 三数取中
int GetMidi(int* a, int begin, int end)
{int midi = (begin + end) / 2;// begin midi end 三个数选中位数if (a[begin] > a[midi]){if (a[midi] > a[end])return midi;else if (a[begin] > a[end]) return end;else return begin;}else  // a[begin] <= a[midi]{if (a[midi] < a[end])return midi;else if (a[begin] < a[end]) return end;else  // a[end] <= a[begin] <= a[midi] return begin;}
}

✨为什么要进行小区间优化?

  1. 减少递归深度:当快速排序处理的数组或子数组较小时,递归的深度会减少,从而能够更快地完成排序,减少函数调用开销。
  2. 避免栈溢出:对于较小的子数组使用非递归的方法可以避免在深层递归时出现栈溢出的问题。
  3. 提升平均性能:小区间优化通过结合递归和迭代,能够有效平衡不同情况下的性能,从而提升快速排序的平均性能。

综上所述,小区间优化是快速排序中一个重要的性能提升措施,它有助于降低算法在实际应用中的最坏情况时间复杂度,提高整体的排序效率。

【小区间优化快排代码】

// 快排(霍尔法 + 小区间优化)
void QuickSort1(int* a, int begin, int end)
{if (begin >= end)return;// 小区间优化if (end - begin + 1 <= 10) // 数组元素个数为小于10时调用直接插入排序{InsertSort(a + begin, end - begin + 1);}else{// 三数取中,优化快排// begin midi end 三个数选中位数int midi = GetMidi(a, begin, end);Swap(&a[begin], &a[midi]);int left = begin, right = end;int keyi = begin;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);keyi = left;// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);}
}

2.1 hoare版本 + 动图演示

算法步骤:

  1. 选择基准值:从待排序数列中选取第一个数作为基准值。
  2. 分区:重新排列数列,所有比基准值小的元素移到基准值的左边,所有比基准值大的元素移到基准值的右边。这个过程称为一趟快速排序。
  3. 递归排序:对基准值左、右两边的子序列重复上述步骤,直到所有子序列长度不超过1,此时待排序数列就变成了有序数列。

在这里插入图片描述

void Swap(int* p1, int* p2)
{int temp = *p1;*p1 = *p2;*p2 = temp;
}
// 快速排序递归实现
// hoare版快排的单趟排序
int PartSort1(int* a, int begin, int end)
{// 三数取中,优化快排// begin midi end 三个数中选中位数int midi = GetMidi(a, begin, end);Swap(&a[begin], &a[midi]);int left = begin, right = end;int keyi = begin;while (left < right){// 注意:第一步是先从右边开始找小// 右边找小while (left < right && a[right] >= a[keyi]){--right;}// 左边找大while (left < right && a[left] <= a[keyi]){++left;}Swap(&a[left], &a[right]);}Swap(&a[left], &a[keyi]);return left;
}
// 快排
void QuickSort(int* a, int begin, int end)
{// 递归出口if (begin >= end)return;int keyi = PartSort1(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

2.2 挖坑法 + 动图演示

算法步骤:

  1. 选择基准值:从待排序数列中选取第一个数作为基准值。
  2. 挖坑:将基准值放在待排序数列中的一个“坑”的位置上,这个“坑”的位置相当于基准值的索引。
  3. 分区:将比基准值小的元素移到基准值的左边,将比基准值大的元素移到基准值的右边。这一步实际上是在填平“坑”的过程,同时也使得基准值左边的元素都比它小,右边的元素都比它大。
  4. 递归排序:对基准值左、右两边的子序列重复上述步骤,直到所有子序列长度不超过 1,此时待排序数列就变成了有序数列。

在这里插入图片描述

void Swap(int* p1, int* p2)
{int temp = *p1;*p1 = *p2;*p2 = temp;
}
// 挖坑法
int PartSort2(int* a, int begin, int end)
{// 三数取中,优化快排// begin midi end 三个数选中位数int midi = GetMidi(a, begin, end);Swap(&a[begin], &a[midi]);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; // 返回基准值的正确下标
}
// 快排
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort2(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

2.3 前后指针法 + 动图演示

算法步骤:

  1. 选择基准值:从待排序数列中选取第一个数作为基准值(key)
  2. 创建前后指针:创建两个指针,prevcurprev指向数组序列首元素位置cur指向prev的下一个位置。
  3. 遍历:通过遍历,如果cur指针找到比key小的数,然后判断prev的下一个位置是否为cur所处的位置,如果不是,则将两个值进行交换,如果是,则继续往后遍历,直到cur遍历结束。
  4. 归位:最后要将key基准值与prev指向的值进行互换,最终确认基准值处于数组序列的中间位置。
  5. 递归排序:递归地对基准值左边和右边的子数组进行排序。

在这里插入图片描述

void Swap(int* p1, int* p2)
{int temp = *p1;*p1 = *p2;*p2 = temp;
}
// 前后指针法
int PartSort3(int* a, int begin, int end)
{// 三数取中,优化快排// begin midi end 三个数选中位数int midi = GetMidi(a, begin, end);Swap(&a[begin], &a[midi]);int keyi = begin;int prev = begin;int cur = prev + 1;while (cur <= end){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[keyi], &a[prev]);return prev;
}
// 快排
void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = PartSort3(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort(a, begin, keyi - 1);QuickSort(a, keyi + 1, end);
}

2.4 快排的非递归

快速排序的非递归实现可以使用来模拟递归过程。以下是算法步骤和思想:

算法步骤

  1. 初始化栈:创建一个空栈,用于 存储待处理的子数组的起始和结束位置
  2. 初始状态入栈:将整个待排序数组的起始和结束位置作为初始状态入栈。
  3. 循环处理栈中的状态:当 栈不为空时,执行以下操作:
    • 弹出栈顶元素,即当前待处理的子数组的起始和结束位置
    • 进行分区操作,找到基准值的正确位置,如果 左右两个子数组起始位置小于结束位置则将左右两个子数组的起始和结束位置入栈
  4. 分区操作:在每个子数组上执行分区操作,将小于基准值的元素放在左边,大于基准值的元素放在右边。
  5. 更新栈:根据分区结果,将左子数组的起始和结束位置以及右子数组的起始和结束位置入栈
  6. 重复循环:重复步骤3-5,直到栈为空,此时整个数组已经有序

算法思想

  1. 模拟递归:通过使用栈来模拟递归调用的过程,避免了函数调用的开销。
  2. 迭代处理:通过循环处理栈中的状态,实现了对整个数组的遍历和排序。
  3. 分区操作:在每个子数组上执行分区操作,将小于基准值的元素放在左边,大于基准值的元素放在右边。
  4. 更新栈:根据分区结果,将左子数组的起始和结束位置以及右子数组的起始和结束位置入栈,以便后续处理。

总的来说,快速排序的非递归实现利用了栈来模拟递归过程,通过迭代的方式对整个数组进行遍历和排序。这种方法可以避免函数调用的开销,并且可以更直观地理解快速排序的工作原理。

辅助栈代码:

typedef int STDataType;typedef struct Stack
{STDataType* a;int top;		// 标识栈顶位置的int capacity;
}ST;// 初始化栈
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;// 表示top指向栈顶元素的下一个位置pst->top = 0;// 表示top指向栈顶元素//pst->top = -1;
}
// 栈的销毁
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}
// 栈顶元素出栈
void STPop(ST* pst)
{assert(pst);// 不为空assert(pst->top > 0);pst->top--;
}
// 取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);// 不为空assert(pst->top > 0);return pst->a[pst->top - 1];
}
// 判断栈空
bool STEmpty(ST* pst)
{assert(pst);/*if (pst->top == 0){return true;}else{return false;}*/return pst->top == 0;
}
// 获取栈的大小
int STSize(ST* pst)
{assert(pst);return pst->top;
}

快排的非递归代码:

// 快排(非递归)
void QuickSortNonR(int* a, int begin, int end)
{ST s;STInit(&s);// 把区间 [begin, end]压栈STPush(&s, end);STPush(&s, begin);while (!STEmpty(&s)){int left = STTop(&s);STPop(&s);int right = STTop(&s);STPop(&s);int keyi = PartSort3(a, left, right); // 三种方法都可// [left, keyi-1] keyi [keyi+1, right]// 判断当前基准值左右区间是否满足条件(即区间内的元素个数是否大于1),满足就将区间位置压入栈中if (keyi + 1 < right){STPush(&s, right);STPush(&s, keyi + 1);}if (left < keyi - 1){STPush(&s, keyi - 1);STPush(&s, left);}}STDestroy(&s);
}

2.5 快速排序特性总结

  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
  2. 时间复杂度:O(N*logN)
    在这里插入图片描述
  3. 空间复杂度:O(logN)(递归开销)
  4. 稳定性:不稳定

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

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

相关文章

图片热区功能

一、需求描述及效果图 1.需求描述&#xff1a; 根据后端返回的坐标及人员信息&#xff0c;在图片上的相应位置添加图片热区功能&#xff0c;点击可展示出对应的人员信息。 图片可进行缩放 2.示例&#xff1a; &#xff08;定位是随便写的&#xff0c;仅做示例&#xff09; …

探索设计模式的魅力:为什么你应该了解装饰器模式-代码优化与重构的秘诀

设计模式专栏&#xff1a;http://t.csdnimg.cn/nolNS 开篇 在一个常常需要在不破坏封装的前提下扩展对象功能的编程世界&#xff0c;有一个模式悄无声息地成为了高级编程技术的隐形冠军。我们日复一日地享受着它带来的便利&#xff0c;却往往对其背后的复杂性视而不见。它是怎样…

Ingress

文章目录 环境准备什么是 Ingress认识 Ingress 资源Ingress 控制器(controller)Ingress 规则pathType 路径类型多重匹配Ingress 类TLS生成证书创建密钥 环境准备 下面的 yaml 文件内容&#xff0c;是使用 sts 创建两个 web 服务&#xff0c;并配置对应的 servcie。web 服务的首…

【MybatisPlus篇】查询条件设置(范围匹配 | 模糊匹配 | 空判定 | 包含性判定 | 分组 | 排序)

文章目录 &#x1f384;环境准备⭐导入依赖⭐写入User类⭐配置启动类⭐创建UserDao 的 MyBatis Mapper 接口&#xff0c;用于定义数据库访问操作⭐创建配置文件&#x1f6f8;创建测试类MpATest.java &#x1f354;范围查询⭐eq⭐between⭐gt &#x1f354;模糊匹配⭐like &…

基于flask的个人博客项目从0到1

项目展示(持续完善中…) 首页 文章时间线页面 笔记页面 留言页面 关于页面 后台页面-文章管理 后台页面-笔记页面 后台页面-分类 后台管理-新增标签 后台管理-标签页面 后台管理-新增标签 后台管理-关于页面 2.项目详述 该博客开源地址点击跳转&#xff0c;该项目已部署上…

flowable 设置自定义属性教程

概述 由于工作需要给flowable工作流设计器添加自定义属性&#xff0c;以满足功能实现。所以这篇文章介绍下用flowable 开源的的flowable-ui 前端添加自定义属性&#xff0c;后端解析属性值的例子。 技术栈 序号技术点名称版本1Flowable6.8.0 使用的是flowable6.8.0 版的代码…

如何在Windows部署GoLand并通过SSH远程连接Linux服务器

文章目录 1. 安装配置GoLand2. 服务器开启SSH服务3. GoLand本地服务器远程连接测试4. 安装cpolar内网穿透远程访问服务器端4.1 服务器端安装cpolar4.2 创建远程连接公网地址 5. 使用固定TCP地址远程开发 本文主要介绍使用GoLand通过SSH远程连接服务器&#xff0c;并结合cpolar内…

二叉树(1)

1 树概念及结构 1.1树的概念 树是一种非线性的数据结构&#xff0c;它是由n&#xff08;n>0&#xff09;个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;而叶朝下的。 有一个特殊的结点&a…

c++设计模式之适配器模式

作用 适配器模式的作用是可以让不兼容的接口在一起工作 案例 假如现在有一台电脑和一台投影仪&#xff0c;现在需要把电脑和投影仪进行连接 在此基础上我们再假设&#xff0c;电脑只能连接VGA接口&#xff0c;而投影仪的种类繁多&#xff0c;有VGA接口、HAMI接口等多种种类…

初探分布式链路追踪

本篇文章&#xff0c;主要介绍应用如何正确使用日志系统&#xff0c;帮助用户从依赖、输出、清理、问题排查、报警等各方面全面掌握。 可观测性 可观察性不单是一套理论框架&#xff0c;而且并不强制具体的技术规格。其核心在于鼓励团队内化可观察性的理念&#xff0c;并确保由…

低版本MATLAB打开高版本Simulink文件的方法

打开simulink&#xff0c;依次点击“建模”、“环境”、“simulink预设项”&#xff0c;如图所示&#xff1a; 然后在弹出的窗口中&#xff0c;点击“模型文件”&#xff0c;并取消勾选“不要加载用更新版本的simulink创建的模型”&#xff0c;接着点击“应用”即可。如图所示&…

跟着cherno手搓游戏引擎【19】抽象纹理

引入&#xff1a; 导入stb_image: GitHub - nothings/stb: stb single-file public domain libraries for C/C 下载复制stb_image.h的内容&#xff08;8000多行&#xff09;&#xff0c;然后粘到如图位置 stb_image.cpp: #include"ytpch.h" #define STB_IMAGE_IM…

Revit中使用依赖注入

依赖注入的技术已经很成熟&#xff0c;本文主要是说明一下Revit中的适用版本与介绍相关的开源项目。 版本问题 版本 目前的依赖注入包无法支持Revit 2020 以下的版本&#xff0c;原因是因为包中的依赖项与Revit本身的依赖项不一致导致的&#xff0c;所以说如果使用Revit DI…

题目:有1,2,3,4共四个数字,能组成多少个不相同而且无重复数字的三位数有多少个,都是多少?lua

这是作者的思路&#xff0c; 创建三个表&#xff0c; 第一个数是从四个数遍历&#xff0c; 第二个是数剔除第一个数进行遍历 第三个是剔除第一第二个数遍历 脚本如下 local a{1,2, 3, 4} local b{} local c{} local d{} local function copy(tbl) local ctbl{} for k,v in…

机器学习复习(4)——CNN算法

目录 数据增强方法 CNN图像分类数据集构建 导入数据集 定义trainer 超参数设置 数据增强 构建CNN网络 开始训练 模型测试 数据增强方法 # 一般情况下&#xff0c;我们不会在验证集和测试集上做数据扩增 # 我们只需要将图片裁剪成同样的大小并装换成Tensor就行 test_t…

nginx初学者指南

一、启动、停止和重新加载配置 前提&#xff1a;先要启动nginx 在Windows上启动nginx的步骤如下&#xff1a; 1. 下载并安装nginx。可以从nginx官网下载适合自己操作系统的版本&#xff0c;一般是zip压缩包&#xff0c;解压到指定目录中。 2. 进入nginx的安装目录&#xff…

LeetCode:138. 随机链表的复制之如何有效copy

自己复制的话&#xff0c;很容易写出来一个时间复杂度O&#xff08;n ^ 2&#xff09; 空O&#xff08;n&#xff09;的做法 我们可以参考基因的复制&#xff0c; 目录 题目&#xff1a; 实现思路&#xff08;基因复制式的copy&#xff09;&#xff1a; 官方快慢指针解法&…

基于Python的招聘网站爬虫及可视化的设计与实现

摘要&#xff1a;现在&#xff0c;随着互联网网络的飞速发展&#xff0c;人们获取信息的最重要来源也由报纸、电视转变为了互联网。互联网的广泛应用使网络的数据量呈指数增长&#xff0c;让人们得到了更新、更完整的海量信息的同时&#xff0c;也使得人们在提取自己最想要的信…

山东淄博刑侦大队利用无人机抓获盗窃团伙

山东淄博刑侦大队利用无人机抓获盗窃团伙 近期&#xff0c;山东淄博临淄区发生多起盗窃案件。通过视频追踪和调查访问&#xff0c;推断临淄区某村可能为嫌疑人藏匿地点。刑侦大队无人机应急小组迅速到达现场&#xff0c;经无人机高空侦查&#xff0c;发现并锁定了嫌疑人的藏匿…

【开源】SpringBoot框架开发城市桥梁道路管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示四、核心代码4.1 查询城市桥梁4.2 新增城市桥梁4.3 编辑城市桥梁4.4 删除城市桥梁4.5 查询单个城市桥梁 五、免责说明 一、摘要 1.1 项目介绍 基于VueSpringBootMySQL的城市桥梁道路管理系统&#xff0c;支持…