17 快速排序2（Quick Sort）

本文主要是介绍17 快速排序2（Quick Sort），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

2.2.2 对向双指针

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

待排序数组

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

从左右两端对向查找符合条件的数，使用left指针从左向右查找大于等于key值的数，使用right指针从右向左查找小于等于key值的数，直到满足结束条件”left>right“

left指针查找到第一个大于等于key:6的数为7，right指针查找到第一个小于等于key:6的数为1

交换两者之后，left和right继续查找，left找到大于等于key:6的数6，right找到小于等于key:6的数2

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

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

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

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

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

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

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

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

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

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

左区间找到5和4

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

整个序列排序完成

这篇关于17 快速排序2（Quick Sort）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！