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

数据结构初阶:排序算法(二)交换排序

🔥个人主页:胡萝卜3.0

🎬作者简介:C++研发方向学习者

📖个人专栏:  《C语言》《数据结构》 《C++干货分享》

⭐️人生格言:不试试怎么知道自己行不行

前言:在数据结构初阶:排序算法(一)中分析了插入排序(直接插入排序和希尔排序)和选择排序(直接选择排序和堆排序)两类算法,详细说明了其基本思想、代码实现和时间复杂度,接下来我们学习交换排序算法的相关内容。

目录

四、交换排序

4.1 冒泡排序

4.2 快速排序

4.2.1 hoare版本

4.2.2 挖坑法

4.2.3 lomuto前后指针法

4.3 快速排序--非递归

4.3.1 代码

4.3.2 代码解释:


四、交换排序

4.1 冒泡排序

冒泡排序(Bubble Sort)是一种简单直观的排序算法。它通过重复地遍历要排序的数列,一次比较两个相邻的元素,如果它们的顺序错误就交换它们的位置。这个过程会一直重复,直到没有需要交换的元素为止,也就是说数列已经排序完成(不断比较当前下标和下边的下一个进行对比,把筛选的数据对换)

  

4.1.1 代码
void BubbleSort(int* arr, int n)
{//趟数for (int i = 0; i < n; i++){//交换次数for (int j = 0; j < n-1-i; j++){if (arr[j] > arr[j + 1]){swap(&arr[j], &arr[j + 1]);}}}
}
4.1.2 冒泡排序的特性总结

1、时间复杂度O(N ^ 2)

2、空间复杂度O(1)

3、冒泡排序是一种非常容易理解的排序,具有教学意义;

4、稳定性稳定

4.2 快速排序

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

根据上面的基本思想,我们就可以得到快速排序算法的大致框架:

这时候就有同学想问了,这个递归函数的结束限制条件是怎么得来的?

那这个时候就有个问题了,怎么找基准值呢?我们聪明的先辈想出了三种找基准值的方法,接下来,让我们一一学习:

4.2.1 hoare版本

算法思路:
首先将0索引的位置作为基准值,创建左右指针,左指针从索引值为1的位置开始从左往右找比基准值大的值,右指针从右往左找比基准值小的值,找到之后,交换左右指针指向的数,交换完之后,左指针++,右指针--(必须做),重复此操作,直到左指针大于右指针,此时交换右指针所在的位置和默认基准值的位置(刚开始假设的0索引位置)右指针所在的位置就是基准值的位置,此时左边都是比基准数小的,右边都是比基准数大的,再依次递归基准数左边部分和右边部分,就实现了排序。

注意:一定要先从右边开始找比基准数小的,先从左边开始就无法达到效果


 

代码实现:

void swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
int _QucikSort(int* arr, int left, int right)
{int keyi = left;left++;while (left<=right){//left:从左往右找比基准值大的//right:从右往左找比基准值小的while (left <= right && arr[right] > arr[keyi]){right--;}while (left<=right && arr[left] < arr[keyi]){++left;}//跳出循环,说明找到相应的值if (left <= right){swap(&arr[left++], &arr[right--]);}}//跳出循环,此时right的位置就是基准值的位置swap(&arr[keyi], &arr[right]);return right;
}
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值--keyiint keyi = _QucikSort(arr, left, right);QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}

接下来,我们来看几个问题,通过这个问题的学习,我们可以更好的掌握代码。

问题1--内层循环为什么不能加上“=”?

问题2--为什么left==right时,不跳出循环?

问题3--为什么交换完之后,left++和right--?

问题4--为什么if语句中要加上“=”?

4.2.2 挖坑法

单趟的动图演示:

思路:
创建左右指针。首先将0索引的位置作为坑位,坑位所在的值作为基准值,右指针从右往左找比基准值小的值,找到之后立即放到坑中,让该右指针所在的位置成为新的坑位,左指针从左往右找比基准值大的值,找到之后立即放到坑中,并让该左指针所在的位置成为新的坑位,重复上面操作,直到左右指针相遇,相遇的坑位为基准值的位置,返回当前坑的下标

代码

int _QucikSort(int* arr, int left, int right)
{int hole = left;int keyi = arr[hole];while (left < right){while (left < right && arr[right] > keyi){right--;}arr[hole] = arr[right];hole = right;while (left < right && arr[left] < keyi){++left;}arr[hole] = arr[left];hole = left;}//left==right时跳出循环,此时的位置为基准值的位置arr[hole] = keyi;return hole;
}void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值--keyiint keyi = _QucikSort(arr, left, right);QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}
4.2.3 lomuto前后指针法

单趟动态演示:

前后指针法的单趟排序的基本步骤如下:
 1、选出一个key,一般是最左边或是最右边的。
 2、起始时,prev指针指向序列开头,cur指针指向prev+1。
 3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容(prev和cur指向的不是同一个数据时才交换),然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur指针越界,此时将key和prev指针指向的内容交换即可。

 经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。

 然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作。

代码:

int _QucikSort(int* arr, int left, int right)
{int keyi = left;int prev = left, cur = prev + 1;while (cur <= right){if (arr[cur] < arr[keyi] && ++prev != cur){swap(&arr[prev], &arr[cur]);}cur++;}//跳出循环,prev的位置为基准值的位置swap(&arr[prev], &arr[keyi]);return prev;
}
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值--keyiint keyi = _QucikSort(arr, left, right);QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}

4.2.4 快速排序算法的时间复杂度

如果快速排序算法的基准值找的不好的情况下,时间复杂度为:n^2

快速排序特性总结:

  1. 时间复杂度: O(nlogn)
  2. 空间复杂度: O(logn)
4.3 快速排序--非递归

回顾上面的学习,我们发现快速排序算法的最关键的地方就在于找基准值,先对整个序列找基准值,然后对左右序列找基准值。

不难发现,找基准值的关键所在就在于左右的界限,知道左右的界限,我们就可以根据lomuto双指针法找基准值,那我们怎么存储相应的界限呢?

这就要用到数据结构--栈,让我们一起看一下这个非递归版本是怎么实现的。

快速排序的非递归算法基本思路:
 1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
 2、当栈不为空时,读取栈中的信息(一次读取两个:一个是L,另一个是R),然后调用某一版本的单趟排序,排完后获得了key的下标,然后判断key的左序列和右序列是否还需要排序,若还需要排序,就将相应序列的L和R入栈;若不需排序了(序列只有一个元素或是不存在),就不需要将该序列的信息入栈。
 3、反复执行步骤2,直到栈为空为止。

4.3.1 代码
void QuickSort(int* arr, int left, int right)
{ST st;StInit(&st);Stpush(&st, right);Stpush(&st, left);while (!STEmpty(&st)){int begin = STtop(&st);Stpop(&st);int end = STtop(&st);Stpop(&st);int keyi = begin;int prev = begin, cur = prev + 1;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){swap(&arr[cur], &arr[prev]);}++cur;}swap(&arr[prev], &arr[keyi]);keyi = prev;//左序列:[begin,keyi-1]//右序列:[keyi+1,end]if (keyi + 1 < end){Stpush(&st, end);Stpush(&st, keyi + 1);}if (begin < keyi - 1){Stpush(&st, keyi - 1);Stpush(&st, begin);}}STDestory(&st);
}
4.3.2 代码解释:

时间复杂度: O(nlogn)

http://www.xdnf.cn/news/1305217.html

相关文章:

  • Boost库中boost::function函数使用详解
  • Redis面试精讲 Day 22:Redis布隆过滤器应用场景
  • 测控一体化闸门驱动灌区信息化升级的核心引擎
  • 波浪模型SWAN学习(1)——模型编译与波浪折射模拟(Test of the refraction formulation)
  • yolo安装
  • es7.x中分片和节点关系以及查看节点数
  • WEB安全--Java安全--Servlet内存马
  • 前端基础知识版本控制系列 - 01( 对版本管理的理解)
  • pyqt5无法显示opencv绘制文本和掩码信息
  • Map、Dictionary、Hash Table:到底该用哪一个?
  • 机械学习---- PCA 降维深度解析
  • 朗空量子与 Anolis OS 完成适配,龙蜥获得抗量子安全能力
  • redis-保姆级配置详解
  • 焊接机器人保护气体效率优化
  • 18- 网络编程
  • NAS播放器的新星,一站式全平台媒体库管理工具『Cinemore』体验
  • 文档对比(java-diff-utils)
  • HTML5新增属性
  • 【机器学习深度学习】OpenCompass 评测指标全解析:让大模型评估更科学
  • 从前端框架到GIS开发系列课程(26)在mapbox中实现地球自转效果,并添加点击事件增强地图交互性
  • 物联网(IoT)系统中,通信协议如何选择
  • 20250815在荣品RD-RK3588-MID开发板的Android13下调通TP芯片FT8206
  • 智慧零碳园区——解读2025 零碳产业园区实施路径规划【附全文阅读】
  • MqSQL中的《快照读》和《当前读》
  • SQL182 连续两次作答试卷的最大时间窗
  • C++第二十课:快递运费计算器 / 黑白配+石头剪刀布小游戏
  • Linux入门(十九)定时备份数据库
  • 第1篇_Go语言初探_环境搭建与HelloWorld
  • 802.11 Wi-Fi 竞争机制深度分析:CSMA/CA 与 DCF
  • 机器学习之PCA降维