C/C++教程

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 ↩︎

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