排序算法(4)之快速排序(1)

 个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

排序算法(4)之快速排序(1)

收录于专栏【数据结构初阶
本专栏旨在分享学习数据结构学习的一点学习笔记,欢迎大家在评论区交流讨论💌

目录

1.常见排序算法

 2.快速排序

2.1快速排序的概念

2.2快速排序的版本

2.2.1 hoare版本

2.2.2 挖坑法

2.2.3 前后指针版本

3. 快速排序的时间复杂度

4.总结


1.常见排序算法

 

 2.快速排序

 2.1快速排序的概念

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

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int array[], int left, int right)
{if (right - left <= 1)return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int div = partion(array, left, right);
}
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div + 1, right);

上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。 

2.2快速排序的版本

将区间按照基准值划分为左右两半部分的常见方式有:

2.2.1 hoare版本

在 Hoare 版本中,划分过程如下:

  1. 选择基准值: 通常选择数组的第一个元素作为基准值,也可以随机选择数组中的某个元素。

  2. 划分过程: 使用两个指针,一个从左边开始(左指针),一个从右边开始(右指针)。它们分别向中间移动,直到找到需要交换的元素。

  3. 具体步骤:

    • 左指针移动: 从左往右找到第一个大于或等于基准值的元素。
    • 右指针移动: 从右往左找到第一个小于或等于基准值的元素。
    • 交换元素: 如果左指针所指元素大于基准值,并且右指针所指元素小于基准值,则交换这两个元素。
    • 继续移动指针: 继续移动左右指针,直到它们相遇。
  4. 交换基准值: 最后将基准值与右指针所指的元素进行交换,使得基准值左侧的元素都小于或等于基准值,右侧的元素都大于或等于基准值。

假设有一个数组 arr 如下:

arr = [6, 5, 3, 1, 8, 7, 2, 4] 

我们选择数组的第一个元素作为基准值(pivot)。现在,我们按照 Hoare 版本的方法来进行划分和排序。

  1. 初始状态:

    数组:[ [6, 5, 3, 1, 8, 7, 2, 4] ],左指针 (left) 初始在数组开头,右指针 (right) 初始在数组结尾。
  2. 第一轮划分过程:

    现在数组变为:[ [4, 5, 3, 1, 6, 7, 2, 8] ]

    继续交换 arr[left]arr[right]

    数组变为:[ [4, 5, 3, 1, 6, 2, 7, 8] ]

    现在 leftright 相遇,停止第一轮划分。

  3. 左指针 left 开始向右移动,直到找到一个大于或等于基准值 6 的元素。在这个例子中,left 移动到 8 处。
    • 右指针 right 开始向左移动,直到找到一个小于或等于基准值 6 的元素。在这个例子中,right 移动到 4 处。
    • 交换 arr[left] 和 arr[right],因为 8 > 6 且 4 < 6,所以交换它们。
  4. left 继续向右移动,移动到 7 处。
    • right 继续向左移动,移动到 6 处。
  5. 基准值位置确定:

    将基准值 6 与 arr[right](即 2)交换,数组变为:[ [4, 5, 3, 1, 2, 6, 7, 8] ]此时 6 左侧的元素小于或等于 6,右侧的元素大于或等于 6
  6. 递归调用:

    分别对基准值左右两侧的子数组递归进行快速排序。

 代码展示:

void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = left;int begin = left, end = right;while (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]);keyi = begin;//[left,keyi-1] keyi [keyi+1, right]QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}
  1. 函数定义和初始条件:

    void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = left; int begin = left, end = right;
    • QuickSort 函数接收一个整数数组 a,以及排序范围的左右边界 left 和 right
    • 如果 left >= right,即排序范围为空或只有一个元素,直接返回,不需要继续排序。
    • keyi 初始化为 left,表示选取第一个元素作为基准值的索引。
    • begin 和 end 初始化为 left 和 right,用于从两端向中间扫描。
  2. 分区过程:

    while (begin < end) { // 右边找小 while (begin < end && a[end] >= a[keyi]) { end--; } // 左边找大 while (begin < end && a[begin] <= a[keyi]) { ++begin; } Swap(&a[begin], &a[end]); } 这是 Hoare 分区的实现部分:
    • 交换这两个元素的位置,确保所有小于基准值的元素都位于基准值的左侧,所有大于基准值的元素都位于右侧。
    • 从数组的左端开始,找到第一个大于基准值 a[keyi] 的元素。
    • 从数组的右端开始,找到第一个小于基准值 a[keyi] 的元素。
  3. 确定基准值的最终位置:

    Swap(&a[keyi], &a[begin]); keyi = begin; 将基准值 a[keyi] 移动到它最终应该处于的位置 begin,并更新 keyi
  4. 递归调用排序左右子数组:

    QuickSort(a, left, keyi - 1); QuickSort(a, keyi + 1, right); 递归调用 QuickSort 函数对基准值左右两侧的子数组进行排序。

这里的递归过程就拿我们上面图解的序列举例

经过一次排序,我们得到左边比key小,右边比key大,然后便是递归的过程. 

2.2.2 挖坑法

 

void QuickSort(int* a, int left, int right) {if (left >= right)return;int key = a[left]; // 选择第一个元素作为基准值int low = left, high = right;while (low < high) {// 从右向左找到第一个小于基准值key的元素while (low < high && a[high] >= key)high--;if (low < high) {a[low] = a[high]; // 使用 a[high] 的值填充 a[low] 的坑low++;}// 从左向右找到第一个大于基准值key的元素while (low < high && a[low] <= key)low++;if (low < high) {a[high] = a[low]; // 使用 a[low] 的值填充 a[high] 的坑high--;}}a[low] = key; // 将基准值放入最终的坑中int pivot = low; // 基准值的最终位置QuickSort(a, left, pivot - 1); // 对左子数组递归排序QuickSort(a, pivot + 1, right); // 对右子数组递归排序
}

 

挖坑法(Lomuto分区)是快速排序的一种经典实现方式,与 Hoare分区方案相比,其主要区别在于如何选择基准元素和如何进行元素交换。下面是使用挖坑法实现的快速排序算法的详细解释:

实现步骤:

  1. 函数定义和初始条件

    QuickSort 函数接收整数数组 a,以及排序范围的左右边界 left 和 right。如果 left >= right,说明排序范围为空或只有一个元素,直接返回。
  2. 挖坑并进行分区:将找到的大于 key 的元素填充到 high 所指的坑中,并将 high 向左移动。接着从数组左端 low 开始,向右寻找第一个大于基准值 key 的元素。

    将找到的小于 key 的元素填充到 low 所指的坑中,并将 low 向右移动。从数组右端 high 开始,向左寻找第一个小于基准值 key 的元素。
  3. 填坑完成分区

    将基准值放入最终的坑中,确定基准值的最终位置
  4. 递归排序左右子数组

    pivot 是基准值的最终位置,左侧元素都小于基准值,右侧元素都大于基准值。递归地对左右两个子数组进行快速排序。
  5. 总结:

  • 挖坑法是快速排序的一种高效分区方案,其核心思想是通过不断填坑的方式将数组分为小于和大于基准值的两部分,然后递归地对这两部分进行排序。
  • 比较与 Hoare分区方案的区别在于处理基准值的交换策略和分区过程中的具体操作顺序。
  • 在实际应用中,挖坑法通常比 Hoare分区方案更高效,因为它减少了元素的移动次数。

2.2.3 前后指针版本

void QuickSort(int* a, int left, int right)
{if (left >= right)return;int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);cur++;}Swap(&a[prev], &a[keyi]);keyi = prev;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}
  • keyi 初始化为 left,作为当前分区的基准元素索引。
  • prev 初始化为 left,表示当前小于基准值的元素应该放置的位置。
  • cur 初始化为 prev + 1,从基准元素的下一个位置开始向右遍历数组。

while 循环中:

  • 如果 a[cur] 小于 a[keyi],则将 a[cur] 与 a[prev+1] 位置的元素交换,并增加 prev 的值。
  • 遍历完成后,将基准元素 a[keyi] 与 a[prev] 位置的元素交换,这样基准元素就被放置到了正确的位置,并返回基准元素的新索引 prev

在实现上,它遵循了快速排序的基本思路:选择一个基准元素,通过分区操作将数组分为两部分,然后递归地对每部分进行排序。 

图解:

3. 快速排序的时间复杂度

平均情况时间复杂度

在平均情况下,快速排序的时间复杂度为 O(n log n)

  • 分析
    • 快速排序的核心是分区操作,选择一个基准元素并将数组分为两部分。在理想情况下,每次分区后基准元素大约将数组划分为两个大小相等的子数组。
    • 假设每次分区的时间复杂度为 O(n),其中 n 是当前数组的长度。在最均匀的情况下,每次递归都会将问题规模减半。
    • 因此,递归树的高度是 O(log n),每层的分区操作总共需要 O(n) 的时间,因此总体时间复杂度是 O(n log n)。

最坏情况时间复杂度

在最坏情况下,快速排序的时间复杂度为 O(n^2)

  • 分析
    • 最坏情况发生在每次选择的基准元素都是当前子数组中的最大或最小元素,导致分区后一个子数组为空,另一个子数组包含 n-1 个元素。
    • 这种情况下,递归树退化为一个类似于冒泡排序的结构,递归深度为 n,每层的时间复杂度为 O(n)。
    • 因此,总体时间复杂度为 O(n) * O(n) = O(n^2)。

最佳情况时间复杂度

在最佳情况下,即每次分区都能均匀划分数组的情况下,时间复杂度也是 O(n log n)

4.总结

快速排序的平均时间复杂度为 O(n log n),它的实际性能优秀且适用于大部分情况。然而,在处理大部分已经有序的数组时,快速排序可能会退化到 O(n^2),这时可以考虑采用随机化快速排序或者其他改进版本来避免最坏情况的发生。这也就是我下个章节需要讲到的快速排序的优化以及用非递归实现快速排序.

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

langchain循序渐进之langchain 安装及使用

pip安装langchain pip install langchain安装langsmith(可选) langsmith官方提示是用来观察大模型复杂调用情况&#xff0c;可选项。 [LangSmith]点击注册然后把秘钥填进去就行&#xff0c;这里我略过了 export LANGCHAIN_TRACING_V2"true" export LANGCHAIN_A…

【C++】模版初阶以及STL的简介

个人主页~ 模版及STL 一、模版初阶1、泛型编程2、函数模版&#xff08;1&#xff09;概念&#xff08;2&#xff09;函数模版格式&#xff08;3&#xff09;函数模版的原理&#xff08;4&#xff09;函数模版的实例化①显式实例化②隐式实例化 &#xff08;5&#xff09;模版参…

精益六西格玛项目赋能,石油机械龙头企业质量效率双提升!

​国内某石油机械制造龙头&#xff0c;迎接挑战&#xff0c;迈向卓越&#xff0c;携手张驰咨询&#xff0c;启动精益六西格玛项目&#xff0c;开启管理革新新篇章。 在国家政策调整和市场竞争日益激烈的背景下&#xff0c;作为国内石油机械产品制造领域的龙头企业&#xff0c;…

算法 —— LRU算法

算法 —— LRU算法 LRULRU算法的工作原理&#xff1a;实现方法&#xff1a;性能考虑&#xff1a; 模拟过程splice函数对于std::list和std::forward_list基本语法&#xff1a;功能描述&#xff1a; 示例&#xff1a;注意事项&#xff1a; 如果大家已经学习过了Cache的替换算法和…

Linux——Shell脚本和Nginx反向代理服务器

1. Linux中的shell脚本【了解】 1.1 什么是shell Shell是一个用C语言编写的程序&#xff0c;它是用户使用Linux的桥梁 Shell 既是一种命令语言&#xff0c;有是一种程序设计语言 Shell是指一种应用程序&#xff0c;这个应用程序提供了一个界面&#xff0c;用户通过这个界面访问…

开放式耳机2024哪家品牌比较好?2024年爆火开放式耳机推荐

很多小伙伴在后台私信我&#xff0c;滴滴我说&#xff0c;最近开放式耳机这么火&#xff0c;他也想要入手一台问问我&#xff0c;有哪些开放式耳机值得现在入手的&#xff0c;作为一个尽职尽业的数码博主&#xff0c;我本来是一个个回复的&#xff0c;但是私信没想到这么多&…

[C++初阶]list的模拟实现

一、对于list的源码的部分分析 1.分析构造函数 首先&#xff0c;我们一开始最先看到的就是这个结点的结构体&#xff0c;在这里我们可以注意到这是一个双向链表。有一个前驱指针&#xff0c;一个后继指针。然后在有一个存储数据的空间 其次它的迭代器是一个自定义类型&#x…

pyinstall 打包基于PyQt5和PaddleOCR的项目为.exe

简介&#xff1a; 最近做了一个小项目&#xff0c;是基于PyQt5和PaddleOCR的。需要将其打包为.exe&#xff0c;然后打包过程中遇到了很多问题&#xff0c;也看了很多教程&#xff0c;方法千奇百怪的&#xff0c;最后也是一步一步给试出来了。记录一下&#xff0c;防止以后忘记…

CSS基础学习之元素定位(6)

目录 1、定位类型 2、取值 2.1、static 2.2、relative 2.3、absolute 2.4、fixed 2.5、stickty 3、示例 3.1、相对定位(relative) 3.2、绝对定位&#xff08;absolute&#xff09; 3.3、固定定位&#xff08;fixed&#xff09; 3.4、粘性定位&#xff08;sticky&…

智慧互联新时代,Vatee万腾平台引领行业变革

在科技日新月异的今天&#xff0c;我们正步入一个前所未有的智慧互联新时代。这个时代&#xff0c;信息如潮水般涌来&#xff0c;数据成为新的石油&#xff0c;驱动着各行各业发生深刻变革。在这场变革的浪潮中&#xff0c;Vatee万腾平台以其卓越的智慧互联技术和前瞻性的战略布…

vue3前端开发-执行npm run dev提示报错怎么解决

vue3前端开发-执行npm run dev提示报错怎么解决&#xff01;今天在本地安装初始化了一个vue3的案例demo。但是当我执行npm run dev想启动它时报错了说&#xff0c;找不到dev。让我检查package.json文件是否包含dev。如下图所示&#xff1a; 实际上&#xff0c;不必惊慌&#xf…

2024全球和国内最常用的弱密码,有没有你的?

密码管理器NordPass分析了来自公开来源的超过4.3TB 的密码数据&#xff0c;找出了当前为止&#xff08;2024年&#xff09;最常用&#xff08;最脆弱&#xff09;的密码。 这些密码主要有下面这些特征&#xff1a; 简单且常用&#xff0c;万年弱密码&#xff0c;比如123456、a…

获利能力段部分特征值不更新,需要手动点派生才更新的问题

一、问题描述&#xff1a;销售订单修改某些特征值字段&#xff0c;保存后&#xff0c;获利能力段对应的字段值没更新。 比如&#xff1a;把销售订单销售组从Z09修改为Z04&#xff0c;保存后&#xff0c;获利能力段重的销售组还是旧值Z09。 1、修改销售组为Z04,然后保存 2、销售…

mac拆分pdf mac如何拆分pdf成多个文件

在数字化办公日益普及的今天&#xff0c;pdf文件因其良好的兼容性和便捷性&#xff0c;已经成为工作和学习中的重要文件格式。然而&#xff0c;有时候我们可能会遇到需要将一个大的pdf文件拆分成多个小文件的情况&#xff0c;以便于管一理和分享。本文将为您详细介绍两种简单易…

【BUG】已解决:java.lang.reflect.InvocationTargetException

已解决&#xff1a;java.lang.reflect.InvocationTargetException 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#xff0c;我是博主英杰&#xff0c;211科班出身&#xff0c;就职于医疗科技公司&#xff0c;热衷分享知识&#xff0c;武汉城市开发…

[word] word如何编写公式? #微信#知识分享

word如何编写公式&#xff1f; word如何编写公式&#xff1f;Word中数学公式是经常会使用到的&#xff0c;若是要在文档中录入一些复杂的公式&#xff0c;要怎么做呢&#xff1f;接下来小编就来给大家讲一讲具体操作&#xff0c;一起看过来吧&#xff01; 方法一&#xff1a;…

【机器学习】--过采样原理及代码详解

过采样&#xff08;Oversampling&#xff09;是一个在多个领域都有应用的技术&#xff0c;其具体含义和应用方法会根据领域的不同而有所差异。以下是对过采样技术的详细解析&#xff0c;主要从机器学习和信号处理两个领域进行阐述。 一、机器学习中的过采样 在机器学习中&…

完美的用户体验:如何设计一个直观和有效的网站导航?

APP的顶部导航栏对我们来说很熟悉。导航栏是UI设计中不可或缺的一部分&#xff0c;几乎每个页面都使用导航栏。虽然导航栏看起来很简单&#xff0c;不需要太多精力&#xff0c;但是设计一个与产品需求和客户目标高度匹配的导航栏并不是那么容易的。导航栏的设计标准有很多细节需…

JavaWeb服务器-Tomcat(Tomcat概述、Tomcat的下载、安装与卸载、启动与关闭、常见的问题)

Tomcat概述 Tomcat服务器软件是一个免费的开源的web应用服务器。是Apache软件基金会的一个核心项目。由Apache&#xff0c;Sun和其他一些公司及个人共同开发而成。 由于Tomcat只支持Servlet/JSP少量JavaEE规范&#xff0c;所以是一个开源免费的轻量级Web服务器。 JavaEE规范&…

JavaScript 中怎么看数据返回值

文章目录 前言console.log()1. 输出简单的文本2. 输出变量3. 输出表达式的结果4. 输出对象和数组5. 输出多个参数6. 使用模板字符串7. 输出错误信息 alert()基本用法使用场景注意事项 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 我只知道后端程序跑…