每次写快速排序，写过一次搞明白了，过一段时间写又忘记了。这次采用牛郎织女的故事，加深记忆。

牛郎织女从两边往中间走见面，牛郎在左边，织女在右边. 他们选取路上最左的一个数字作为交流信号。
织女先向左走，大于等于就走，小于就停。牛郎向右走，小于等于就走，大于就停，然后两人打电话交换脚下的数据。
接着走，接着打电话交换数据，直到两人相遇。相遇后，把两人脚下的数据和心中的数字做交换。
至此，相遇点左边都是比心中数字小，相遇点右边都是比心中数字大。

1. 快速排序

1.1 原理

原始数据 “6 1 2 7 9 3 4 5 10 8”，目标：左边小于参考值，右边大于参考值

把第一个值 6 作为参考值，分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于 6 的数，再从左往右找一个大于 6 的数，然后交换他们。

这里可以用两个变量 i 和 j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵 i”和“哨兵 j”。刚开始的时候让哨兵 i 指向序列的最左边（即 i=1），指向数字 6。让哨兵 j 指向序列的最右边（即 j=10），指向数字 8。

首先哨兵 j 开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵 j 先出动，这一点非常重要（后面会解释）。哨兵 j 一步一步地向左挪动（即 **j–**），直到找到一个小于 6 的数停下来。接下来哨兵 i 再一步一步向右挪动（即 **i++**），直到找到一个数大于 6 的数停下来。最后哨兵 j 停在了数字 5 面前，哨兵 i 停在了数字 7 面前。

现在交换哨兵 i 和哨兵 j 所指向的元素的值。交换之后的序列如下：6 1 2 5 9 3 4 7 10 8，到此，第一次交换结束。

接下来开始哨兵 j 继续向左挪动（再友情提醒，每次必须是哨兵 j 先出发）。他发现了 4（比基准数 6 要小，满足要求）之后停了下来。哨兵 i 也继续向右挪动的，他发现了 9（比基准数 6 要大，满足要求）之后停了下来。

此时再次进行交换，交换之后的序列如下：6 1 2 5 4 3 9 7 10 8，第二次交换结束。

“探测”继续。哨兵 j 继续向左挪动，他发现了 3（比基准数 6 要小，满足要求）之后又停了下来。哨兵 i 继续向右移动，糟啦！此时哨兵 i 和哨兵 j 相遇了，哨兵 i 和哨兵 j 都走到 3 面前。说明此时“探测”结束。

我们将基准数 6 和 3 进行交换。

交换之后的序列如下：3 1 2 5 4 6 9 7 10 8。

到此第一轮“探测”真正结束。此时以基准数 6 为分界点，6 左边的数都小于等于 6，6 右边的数都大于等于 6。回顾一下刚才的过程，其实哨兵 j 的使命就是要找小于基准数的数，而哨兵 i 的使命就是要找大于基准数的数，直到 i 和 j 碰头为止。

OK，解释完毕。现在基准数 6 已经归位，它正好处在序列的第 6 位。此时我们已经将原来的序列，以 6 为分界点拆分成了两个序列，左边的序列是“3 1 2 5 4”，右边的序列是“ 9 7 10 8 ”。

接下来开始递归把。

1.2 代码

package main

import "fmt"

func main() {
	arr := []int{2, 1, 11, 34, 11, 122, 80}
	fmt.Println("origin", arr)
	QuickSort(arr, 0, len(arr)-1)
	fmt.Println("sort", arr)
}

func QuickSort(arr []int, left int, right int) {
	if left < right {
		partIndex := PartIndex(arr, left, right)
		QuickSort(arr, left, partIndex-1)
		QuickSort(arr, partIndex+1, right)
	}
}

func PartIndex(arr []int, left int, right int) int {
	mid := arr[left]
	origin := left
	for left < right {
		for arr[right] >= mid && left < right {
			right--
		}
		for arr[left] <= mid && left < right {
			left++
		}
		arr[left], arr[right] = arr[right], arr[left]
	}

	arr[left], arr[origin] = arr[origin], arr[left]
	return left
}

2. 实现的问题

2.1 为什么从右往左

因为你是正序排，以 4, 11, 9 为例。

先左走，后右走
mid = 4，左边的 <= 4 才走，走到下标 1。右边的 >= 4 才走，也走到下标1（左<右）。
一交换，11，4，9 不对了。
停的值会比选的值大，我们希望停的位置比选的值小。
先右走，后左走
右边的 >= 4 才走，走到下标0，mid = 4，左边的 <= 4 才走，不走，下标0（左<右）。
交换后正常。

2.2 为什么大于等于，而不是大于

如果就两个数： 2，1。

大于等于时
mid = 2，右边的 >= 2 才走，不动。左边的 <= 2 才走，会走到下标 1。
在下标 1 相遇后，和开头交换。
大于时
mid = 2，右边的 > 2 才走，不动。左边的 < 2 才走，不动。
死循环。

3. 头脑风暴

先写一个分区函数，需要返回index，上层根据这个index递归调用。
一个大循环套两个小循环，右边比较先走，左边比较再走，然后交换。
两个碰在一起，和选的中间值交换，然后返回index即可。

Levon's Blog

快速排序的深刻理解