【初阶数据结构篇】冒泡排序和快速排序（中篇）

embedded/2024/9/23 1:24:22/

文章目录

冒泡排序和快速排序

前言

本篇以排升序为例

代码位置

gitee

冒泡排序

动图理解
在这里插入图片描述

  • 作为第一个接触的算法>排序算法，冒泡排序想必大家已经很熟悉了
    • 总共n个数据，要排n-1趟
    • 第i（i从0开始取）趟要比较n-1-i次
    • 等差数列求和，最坏时间复杂度为O(n2)
  • 定义exchange变量，当数组已经有序时不进入交换，直接跳出循环
    • 最好时间复杂度为O(n)
  • 空间复杂度O(1)
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n-1; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){//升序if (arr[j] < arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){break;}}
}
  • 与直接插入排序法相比，比较次数一致，但冒泡排序的交换需要执行三次，而直接插入排序因为使用了tmp临时变量存储要插入的数据，只用执行一次，所以直接插入排序法效率明显更高
  • 与直接选择排序法相比，直接选择排序法无论数组是否有序都要执行到结束条件，不存在最好最坏时间复杂度。而冒泡排序因为使用了exchange变量进行优化，可以在最好时间复杂度上达到线性的结果。所以冒泡排序更胜一筹
  • 虽然但是，实际中还是不会使用冒泡排序，但它的教学意义是我们不能忽视的😂

快速排序

  • 快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法
  • 其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列 在相应位置上为⽌。

递归法实现

快速排序实现主框架：

void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//[left,right]--->找基准值midint keyi = _QuickSort(arr, left, right);//左子序列：[left,keyi-1]QuickSort(arr, left, keyi - 1);//右子序列：[keyi+1,right]QuickSort(arr, keyi + 1, right);
}

  • 快速排序最重要的就是找基准值:

    • 基准值左边元素都小于它，右边都大于，显然的基准值所在的位置就是所有数据排序好后它应该在的位置上

    • 每次将这个数据（即基准值）放在正确的位置上，然后对其左右序列递归，最后所有数据都被放在了正确的位置上，排序就完成了

将区间中的元素进⾏划分的 _QuickSort ⽅法主要有以下⼏种实现⽅式：

hoare_86">hoare版本

算法思路

  • 假设将序列第一个数作为基准值

  • 定义左右指针

    • left：从左找比基准值大的 ，right：从右找比基准值小的
    • 找到后交换，left++，right–，进入下次循环

  • 跳出循环后交换基准值到正确位置

可以大致写出代码:

int _QuickSort1(int* arr, int left, int right)
{int keyi = left;++left;while (left <right){while (left < right && arr[right] > arr[keyi]){right--;}while (left < right && arr[left] < arr[keyi]){left++;}//right leftif (left < right){Swap(&arr[left++], &arr[right--]);}}Swap(&arr[keyi], &arr[right]);return right;
}

于是这里就抛出几个问题：

  1. 外层循环结束条件是否应该取=?
  2. 内层循环当right或left处数据和基准值相等时是否应该跳出循环?
  3. 最后跳出外层循环我们将基准值交换到正确位置时应该与right还是left处数据交换?

问题1：
在这里插入图片描述

  • 二者相遇时在9的位置，如果不取等，第一次交换完后就跳出循环，此时9和6交换，显然不行

外层循环需要取等，同时在内层循环时相应left和right判断处也要取等，不然left和right相等就死循环了

问题3：

  • 既然跳出循环时是left>right，right处在left扫描过的区域，都是不大于基准值的数据，而left处在right扫描过的区域，都是不小于基准值的数据
  • 显然我们将right处数据和基准值交换，基准值就来到了正确的位置

跳出外层循环应该与right处数据交换，right处数据就是基准值的位置

经过上面两层分析：

改进如下：

int _QuickSort1(int* arr, int left, int right)
{int keyi = left;++left;while (left <= right)//left和right相遇的位置的值比基准值要大{while (left <= right && arr[right] > arr[keyi]){·right--;}//right找到比基准值小/  等于？while (left <= right && arr[left] < arr[keyi]){left++;}//right leftif (left <= right){Swap(&arr[left++], &arr[right--]);}}//right keyi交换Swap(&arr[keyi], &arr[right]);return right;
}

问题2：

  • 假设数组全是相同的数据

在这里插入图片描述

  • 取等于，第一次循环right就和left都在下标为1的位置，此时返回去的基准值就是下标1，左序列只有一个数据，右边序列还有n-2个数据
  • 同样的下次循环的左序列也只有一个数据
  • 像这样一次排一个数据时间复杂度很高

所以不应该取等于，尽量让左右子序列的数据个数平均一些

所以上述改进版本就是最终的hoare排序法

挖坑法

基本思路

创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）

动图解析：

在这里插入图片描述

  • 动图演示的很清楚
  • 这里同样有两个问题
    • left和right是否取等？
    • 当right或left处数据与基准值key相等时是否继续循环

问题1：

  • 以上面动图为例，如果取等最后当left和right相遇时left还要++一次，导致hole所在位置偏移，发生错误，所以不取等

问题2：

  • 同hoare版本，如果全是相等数据时每次只会排序一个数据，时间复杂度太高，所以不取等
//挖坑法
int _QuickSort2(int* arr, int left, int right)
{int hole = left;int key = arr[hole];while (left < right){while (left < right && arr[right] > key){--right;}arr[hole] = arr[right];hole = right;while (left < right && arr[left] < key){++left;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}
lomuto前后指针

基本思想

创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边。

动图解析：

在这里插入图片描述

  • 这种方法比较好理解代码也简单，就不赘述了（就是想不到一点🤣）
//lomuto前后指针法
int _QuickSort(int* arr, int left, int right)
{int prev = left, cur = left + 1;int keyi = left;while (cur <= right){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[keyi], &arr[prev]);return prev;
}
  • 这里当cur和keyi数据相同时是否交换？
  • 假设仍然全是重复数据，代入后会发现二者都是一样的，如果不加等号最后prev下标在0；反之prev下标在end。可见其对重复数据无法通过此来进行优化
递归法复杂度分析
  • 时间复杂度：每一层的总时间复杂度都是O（n），因为需要对每一个元素遍历一次。而且在最好的情况下，同样也是有logn层，所以快速排序最好的时间复杂度为O（nlogn）。
  • 空间复杂度：二叉树递归最大深度为logn，即O（nlogn）
  • 以上是最好情况，最坏情况则是上面说的一次排序一个数据，时间复杂度O(n2)，空间复杂度O(n)。不过现实中基本不会出现这种情况。

注意：在以上找基准值方法中，我们默认都是把基准值定为left所在位置，这种方法当数组接近升序时会导致分割的序列也出现“一边倒”的情况，在高阶数据结构中会讲到如何优化，敬请期待😘

非递归法实现

借助栈这样一种数据结构

有关栈的相关知识，不了解的小伙伴可以看看这篇：
栈的实现方法

  • 栈是先进后出，所以插入先插入right后插入left
  • 找基准值方法使用双指针法最简单
  • 根据基准值划分左右区间
    • 左区间：[begin,keyi-1]
    • 右区间：[keyi+1,end]
  • 循环直到栈为空

在这里插入图片描述

//非递归版本快排
//--借助数据结构--栈
void QuickSortNonR(int* arr, int left, int right)
{ST st;STInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){//取栈顶元素---取两次int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);//[begin,end]---找基准值int prev = begin;int cur = begin + 1;int keyi = begin;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[keyi], &arr[prev]);keyi = prev;//根据基准值划分左右区间//左区间：[begin,keyi-1]//右区间：[keyi+1,end]if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi + 1);}if (keyi - 1 > begin){StackPush(&st, keyi - 1);StackPush(&st, begin);}}STDestroy(&st);
}

以上就是冒泡排序和快速排序方法的介绍啦，各位大佬有什么问题欢迎在评论区指正，您的支持是我创作的最大动力！❤️
请添加图片描述


http://www.ppmy.cn/embedded/88272.html

相关文章

c＋＋STL容器中vector的使用，模拟实现及迭代器使用注意事项和迭代器失效问题

c＋＋STL容器中vector的使用，模拟实现及迭代器使用注意事项和迭代器失效问题

目录 前言&#xff1a; 1.vector的介绍及使用 1.2 vector的使用 1.2 1 vector的定义 1.2 2 vector iterator&#xff08;迭代器&#xff09;的使用 1.2.3 vector 空间增长问题 1.2.4 vector 增删查改 1.2.5vector 迭代器失效问题。 2.vector模拟实现 2.1 std::vect…
阅读更多...
实验2-4-6 求交错序列前N项和

实验2-4-6 求交错序列前N项和

//实验2-4-6 求交错序列前N项和//本题要求编写程序&#xff0c;计算交错序列 1-2/33/5-4/75/9-6/11... 的前N项之和。 #include<stdio.h> #include<math.h> int main(){int n;scanf("%d",&n);//输入在一行中给出一个正整数N。double sum0;for(int i1…
阅读更多...
Day81 代码随想录打卡|贪心算法篇---跳跃游戏 II

Day81 代码随想录打卡|贪心算法篇---跳跃游戏 II

题目&#xff08;leecode T45&#xff09;&#xff1a;给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说&#xff0c;如果你在 nums[i] 处&#xff0c;你可以跳转到任意 nums[i j] 处: 0 < j…
阅读更多...
Vue中使用wangEditor富文本编辑器|图片上传（含后端代码）

Vue中使用wangEditor富文本编辑器|图片上传（含后端代码）

一、效果 二、安装依赖 npm install wangeditor --save npm install wangeditor/editor-for-vuenext --save 三、使用 在src下common文件夹下创建wangEditor文件夹&#xff0c;并在其文件夹下创建index.vue文件 <template><div style"border: 1px solid #ccc…
阅读更多...
基于opencv的答题卡识别

基于opencv的答题卡识别

文章目录 一、背景需求二、处理步骤图片预处理检测到答题卡轮廓透视变换找每个圆圈的轮廓轮廓排序判断是否答题正确 一、背景需求 传统的手动评分方法耗时且容易出错&#xff0c;自动化评分可以可以显著提高评分过程的速度和准确性、减少人工成本。 答题卡图片处理效果如下&am…
阅读更多...
达梦数据库系列—41.表连接方式

达梦数据库系列—41.表连接方式

目录 连接方式 NEST LOOP&#xff08;嵌套循环连接&#xff09; HASH JOIN&#xff08;哈希连接&#xff09; MERGE JOIN&#xff08;排序归并连接&#xff09; 连接方式 创建测试表&#xff1a; create table tab1(c1 int,c2 int ,c3 int); create table tab2(c1 int,c…
阅读更多...
C++ | Leetcode C++题解之第283题移动零

C++ | Leetcode C++题解之第283题移动零

题目&#xff1a; 题解&#xff1a; class Solution { public:void moveZeroes(vector<int>& nums) {int n nums.size(), left 0, right 0;while (right < n) {if (nums[right]) {swap(nums[left], nums[right]);left;}right;}} };
阅读更多...
环境如何搭建部署Nacos

环境如何搭建部署Nacos

这里我使用的是Centos7&#xff0c; Nacos 依赖 Java环境来运行。如果您是从代码开始构建并运行Nacos&#xff0c;还需要为此配置 Maven环境&#xff0c;请确保是在以下版本环境中安装使用 ## 1、下载安装JDK wget https://download.oracle.com/java/17/latest/jdk-17_linux-x6…
阅读更多...
最新文章

Copyright @ 2022~2023