数据结构 ——— 快速排序算法的实现(挖坑法版本)

embedded/2024/11/29 9:46:27/

目录

前言

快速算法>排序算法(挖坑版本)的思想

单躺排序逻辑的实现

快速算法>排序算法的实现(挖坑法)


前言

在上一章学习了 hoaer 版本的快速算法>排序算法的实现
数据结构 ——— 快速算法>排序算法的实现(hoare版本)-CSDN博客
可是 hoaer 版本的快速算法>排序算法存在缺陷
比如说:如果把最左边的值当作 key 的话,那么就必须让右边先走,也就是要让右边先找到比 key 小的值,否则的话最后排出来的就是乱序
因为 left 是找比 key 大的值,right 是找比 key 小的值,只有让 right 先走,才能保证当他们快要相遇时,相遇的值比 key 小,否则让 left 先走的话,最后相遇的位置就不一定是比 key 小的值

所以基于上述原因,对 hoare 版本的快速算法>排序算法进行了改进,避免了这些缺陷


快速算法>排序算法(挖坑版本)的思想

同样是 left 往右边走,找比 key 小的值; right 往左边走,找比 key 大的值;且 key 是最左边的值
不同之处在于是把 key 的值先保存下来,那么就可以形象的理解为 key 的位置被挖了一个坑
然后 right 找到比 key 小的值时,就把小的值放在 key 的位置,也就是放在坑的位置
那么 right 这个位置就形成了新的坑,然后 left 再找,当 left 找到比 key 大的值时,就放到 right 这个坑的位置,最后 left 和 right 相遇的位置也肯定是一个坑,再把保存的 key 放入坑中
这时的数组同样能保证 key 左边的值比 key 小,key 右边的值比 key 大,且就算 left 先走也同样可以完成

以上就是挖坑法单躺排序的思想


单躺排序逻辑的实现

int PartSort_DigPit(int* a, int left, int right)
{// 保存 key 的值int key = a[left];// 坑的下标int hole = left;while (left < right){// 先找右边比 key 小的元素的下标while (left < right && a[right] >= key)right--;// 填坑a[hole] = a[right];// 赋值新坑的下标hole = right;// 再找左边比 key 大的元素的下标while (left < right && a[left] <= key)left++;a[hole] = a[left];hole = left;}// 把 key 放在最终位置a[hole] = key;return hole;
}

快速算法>排序算法的实现(挖坑法)

void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}int key = PartSort_DigPit(a, begin, end);// [begin,key-1] key [key+1,end]QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}

除了挖坑法单躺的思想和 hoare 版本单躺的思想有差异,其他的思路都是一样的
这里就不过多赘述,直接看结论

代码验证:


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

相关文章

SQL面试题——in和not in 不支持怎么办

in和not in 不支持怎么办 这是来自读者群的一位同学的问题,说是别人问他in和not in 不支持怎么办,现在我们来看一下这个问题 in 不支持 其实很多朋友都能写出这样的SQL,其实这个SQL 在没有底层优化的时候还是很可怕的 SELECT a.key, a.value FROM a WHERE a.key in (SEL…

LeetCode题练习与总结:替换后的最长重复字符--424

一、题目描述 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符&#xff0c;并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后&#xff0c;返回 包含相同字母的最长子字符串的长度。 示例 1&#xff1a; 输入&#xff1a;s &quo…

什么是 Token 和 MD5 ?

目录 一&#xff1a;Token和MD5分别是什么 1&#xff1a;Token 2&#xff1a;MD5 二&#xff1a;简易Token的实现 1&#xff1a;Base64。 2&#xff1a;验证Token 三&#xff1a;MD5的使用 一&#xff1a;Token和MD5分别是什么 1&#xff1a;Token Token 的中文有人翻译成…

nvm 常用命令

nvm 常用命令 参考1 参考2 nvm list available 查看nodejs有哪些版本 npm install 10.13.0 下载10.13.0版本 nvm use 10.13.0 切换到10.13.0版本 nvu list 查看已安装版本

迁移学习和无监督学习是什么

迁移学习和无监督学习都是机器学习中的重要方法&#xff0c;它们在湍流速度场超分辨率重建任务中有着独特的作用。让我们通过简单的语言和例子来解释它们如何帮助解决这个问题。 1. 迁移学习&#xff1a; 迁移学习是一种方法&#xff0c;它利用一个领域&#xff08;例如某种类…

R语言处理JSON文件

R语言处理JSON文件 引言 JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;易于人阅读和编写&#xff0c;同时也易于机器解析和生成。它基于JavaScript编程语言的一个子集&#xff0c;但JSON是独立于语言的文本格式&#xff0c…

网络--传输层协议--UDP

传输层作用:负责数据能够从发送端传输到接收端。 1、再谈端口号 端口号标识了一个主机上进行通信的不同的应用程序。 1.1、端口号划分范围 0 - 1023 : 知名端口号,HTTP、FTP、SSH等这些广为使用的应用层协议,他们的端口号都是固定的。 10234 - 65536:操作系统动态分配的…

金铲铲S13双城之战自动拿牌助手

金铲铲S13双城之战自动拿牌助手 基于python&#xff0c;pyautogui和金铲铲自带备战助手实现 B站视频演示效果 shuangcheng.py import timeimport pyautogui import datetimeprint(请关注您的分辨率&#xff0c;此程序需要配合thumbs_x_y.txt文件同时使用) print(简介&#x…