快速排序(快速排序算法)

今天主要介绍下快速排序算法是如何实现的，主要的目标是：等很久之后忘了快速排序的思想时，找到这篇文章就可以帮助你很快的理解和回忆起来。

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 }el { nums[begin] = nums[end] begin += 1 break } } while begin < end { if pivot > nums[begin] { begin += 1 }el { 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 el中的break，完成调头从begin往后遍历小于pivot的值就begin++；就继续再while循环小于pivot的值时，begin不变，并且将begin指向的值替换end指向的值，end++时，就会走while里面的if el中的break，完成调头3.2 关于递归

前期的推文：leetcode 递归编程技巧-链表算法题有详细介绍过递归，递归是一种很有用的编程技巧，必须掌握。不懂的同学可以看下之前的文章。

总结

  今天主要讲解了快速排序的执行流程，以及其中的来回交替的替换和调头操作，希望能帮助到大家。