IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 17 快速排序2（Quick Sort） -> 正文阅读

[数据结构与算法]17 快速排序2（Quick Sort）

由于CSDN单篇帖子的字数限制，补充上一篇快速排序1中的对向双指针算法的图解：

2.2.2 对向双指针

在对向双指针的排序方式中，以key值为序列中点元素为例。图解如下：

待排序数组
3
5
7
4
6
8
2
1
9

取中点元素6，为key值，在对向双指针的排序中，key值所在的位置有可能被交换，所以需要在排序开始时保存key值保存到数组外部的变量中
记录key值
6
3
5
7
4
key
6
8
2
1
9

从左右两端对向查找符合条件的数，使用left指针从左向右查找大于等于key值的数，使用right指针从右向左查找小于等于key值的数，直到满足结束条件”left>right“
key
6
left->
3
5
7
4
6
8
2
1
<-right
9

left指针查找到第一个大于等于key:6的数为7，right指针查找到第一个小于等于key:6的数为1
key
6
3
5
left->
7
4
6
8
2
<-right
1
9

交换两者之后，left和right继续查找，left找到大于等于key:6的数6，right找到小于等于key:6的数2
key
6
3
5
1
4
left->
6
8
<-right
2
7
9

交换两者之后，left和right继续查找，left找到大于等于key:6的数8，right找到小于等于key:6的数2，此时满足结束条件“left>right”，第一轮排序结束
key
6
3
5
1
4
<-right
2
left->
8
6
7
9

区间以left和right指针的位置，分成了“小值/key/大值”的形式（也有可能形成“小值/大值”的形式）

大值8679
小值35142
9
7
6
left->
8
<-right
2
4
1
5
3

左右区间再分别进行递归快排

子递归:对右区间排序
子递归:对左区间排序
key
6
<-right
9
7
key
6
left->
8
key
1
<-right
2
4
key
1
5
left->
3

左区间找到3和1，右区间找到8和6

该位置的第二轮排序
该位置第二轮排序
key
6
9
7
<-right
6
left->
8
key
1
2
4
<-right
1
5
left->
3

分别交换之后，继续查找，左区间满足“left>right”完成该位置的第二轮排序，形成”小值/大值“的形式；右区间满足“left>right”完成该位置的第二轮排序，形成”小值/大值“的形式

该位置的第二轮排序后:小值6/大值879
该位置第二轮排序后:小值1/大值4352
key
6
9
7
left->
8
<-right
6
key
1
2
5
3
left->
4
<-right
1

左区间进行第三轮排序，key为3；右区间进行第三轮排序，key为7

该位置的第二轮排序
该位置的第三轮排序
该位置第二轮排序
该位置第三轮排序
left->
8
6
key
7
<-right
9
key
7
left->
4
1
key
3
<-right
2
5
key
3

左区间找到4和2；右区间找到8和7

该位置的第二轮排序
该位置的第三轮排序
该位置第二轮排序
该位置第三轮排序
left->
8
6
key
7
9
<-right
7
left->
4
1
key
3
<-right
2
5
3

分别交换之后，继续查找，左区间找到3和3；右区间满足“left>right”完成该位置的第三轮排序

该位置的第二轮排序
该位置的第三轮排序后:小值7/大值89
该位置第二轮排序
该位置第三轮排序
left->
7
6
key
7
9
<-right
8
2
1
key
3
4
5
left->
<-right
3

左区间交换找到的数（3与自身交换）之后，满足“left>right”完成该位置的第三轮排序；右区间进行第四轮排序，key为8

该位置的第二轮排序
该位置的第三轮排序
该位置的第四轮排序
该位置第二轮排序
该位置第三轮排序后
7
6
left->
8
key
8
<-right
9
<-right
2
1
key
3
4
left->
5
3

左区间进行第四轮排序，key为5；右区间满足“left>right”完成第四轮排序，至此右区间已有序

右区间第二轮排序后
该位置的第三轮排序
该位置的第四轮排序:小值8/大值9
子递归:对左区间排序
该位置第三轮排序
该位置第四轮排序
7
6
<-right
8
key
8
left->
9
3
2
1
left->
5
key
5
<-right
4

左区间找到5和4

右区间已有序
子递归:对左区间排序
该位置第三轮排序
该位置第四轮排序
9
8
7
6
3
2
1
left->
5
key
5
<-right
4

交换两者，继续查找，此时左区间满足“left>right”完成第四轮排序，形成”小值/大值“的形式，至此左区间已有序

右区间已有序
子递归:对左区间排序
该位置第三轮排序
该位置第四轮排序
9
8
7
6
3
2
1
<-right
4
key
5
left->
5

整个序列排序完成
1
2
3
5
4
6
7
8
9

  1. 快速排序：https://blog.csdn.net/SeeDoubleU/article/details/122421967 ??
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-01-12 00:15:37  更:2022-01-12 00:18:44 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 18:21:32-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码