一文读懂快速排序
这是无量测试之道的第205篇原创
今天主要介绍下快速排序算法是如何实现的，主要的目标是：等很久之后忘了快速排序的思想时，找到这篇文章就可以帮助你很快的理解和回忆起来。
1.执行流程
- 1.从序列中选择一个轴点元素pivot从最后一个元素向前遍历
- 我们的策略是：每次选择第0位置的元素为轴点元素
- 2.利用pivot将数组分割成2个子数组
- 将小于pivot的元素放在pivot的左侧
- 将大于pivot的元素放在pivot的右侧
- 将等于pivot的元素放在pivot的哪侧都可以，本文选择左侧
- 3.对子序列进行步骤1和步骤2操作
- 直到不能再分割(子序列中只剩下一个元素)
先介绍了下快排的执行流程，脑海中先有个大致的思路。总结一下就是先把一个大数组通过第一个元素将之分割成2个小的数组，并且以该轴点为界，小于它的在左边，大于它的在右边，然后递归对2个小数组执行步骤1、2操作，直到不能再分割。也许理解了一部分，别担心，接下来我会通过一个例子来带你走一遍上述的流程。
2.例子演示
(注：图片中的单词start与begin同义)
解释下调头的事情：
- 开始的时候是从end往前遍历
- 大于pivot的值就end++；
- 小于pivot的值时，end不变，并且将end指向的值替换begin指向的值，begin++
- 从beigin往后遍历
- 小于pivot的值就begin++；
- 小于pivot的值时，begin不变，并且将begin指向的值替换end指向的值，end++
- 这样交替进行
想想这样做有什么好处？这只是一个处理值的方式，但是这样处理很巧妙，而且很有作用。记住即可，不必要纠结。不这样做当然也是可以的，就是需要一些临时变量进行存储，没这个既省事又有用。
3.代码实现
func quickSort(nums: inout [Int]) -> [Int] {
sort(nums: &nums, begin: 0, end: nums.count)
return nums
}
func sort(nums: inout [Int], begin: Int, end: Int) {
if end - begin < 2 { return }
var rBegin = begin; var rEnd = end
let mid = pivotIndex(nums: &nums, begin: &rBegin, end: &rEnd)
sort(nums: &nums, begin: begin, end:mid)
sort(nums: &nums, begin: mid + 1, end: end)
}
//【1个大数组被分割成了左边和右边2个数组】
// 将pivot的位置抛出来，作为递归的时候的左边数组的end和右边数组的begin
private func pivotIndex(nums: inout [Int], begin: inout Int, end: inout Int) -> Int {
let pivot = nums[begin]
end -= 1
while begin < end {
while begin < end {
if pivot < nums[end] {
end -= 1
}else {
nums[begin] = nums[end]
begin += 1
break
}
}
while begin < end {
if pivot > nums[begin] {
begin += 1
}else {
nums[end] = nums[begin]
end -= 1
break
}
}
}
//将轴点元素放到最终的位置
nums[begin] = pivot
return begin
}
结果：
对比之前图和这个打印图：第一次打印的遍历结果：[5, 4, 1, 2, 3, 6, 8, 7, 9]和我们上图的流程的结果是一致的。
3.1 关于调头逻辑的代码实现
这个真的是很难想到，通过while的break来实现的；
- 开始的时候是从end往前遍历
- 大于pivot的值就end++；就继续在while循环
- 小于pivot的值时，end不变，并且将end指向的值替换begin指向的值，begin++时，就会走while里面的if else中的break，完成调头
- 从begin往后遍历
- 小于pivot的值就begin++；就继续再while循环
- 小于pivot的值时，begin不变，并且将begin指向的值替换end指向的值，end++时，就会走while里面的if else中的break，完成调头
3.2 关于递归
前期的推文：leetcode 递归编程技巧-链表算法题有详细介绍过递归，递归是一种很有用的编程技巧，必须掌握。不懂的同学可以看下之前的文章。
总结
今天主要讲解了快速排序的执行流程，以及其中的来回交替的替换和调头操作，希望能帮助到大家。
end
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-05-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
