此篇基于我在分析快速排序的时间复杂度时遇到的问题，我没能较好地理解它的运算模式。分治与递归是这个算法重要的两个部分，也比较难弄透，这篇详细分解下。

分治法将一个复杂的问题拆分成多个易解的小问题，最后将所有的解合并起来得到最终的答案。因为在拆分的过程中会出现逐层嵌套和分解的情况，所以这时候递归显得十分的适用。分治和递归像是一对好伙伴，经常在一起工作，因此也产生了许多高效的算法。快速排序就是很经典的一个运用，可是虽然了解实现原理，写起来也不是很熟练，因为里面包含一些边界问题和结束条件比较难把握。

了解算法运行过程最有效的方法就是分解其运行过程，下面分解下快速排序{6,10,12,14,3,5,23}的过程。

数组本身是无序的，我在这默认每次取当前排序组合中的第一位作为基准数，那么第一次排的数就是6，函数执行一遍后会将比6小的数都排在6之前，比6大的排在6之后。i，j分别表示当前组合的第一个索引位和最后一个索引位。这里有个边界问题，就是如果和基准数一样大的数该如何排列。其实一样大的数放在左边和右边都可以，最后的排序结果就是一样大的连在一起，选择一种即可。这里我写的是大于等于放在右边，小于放在左边。还有一个边界就是在步进后如果重合了，就不执行操作了。

1
2
3
4
5
6
7
8
9
10
11
while (i < j) {
	while (i < j && array[j] >= x)//边界：小于x才满足放在左边的条件，所以j>=x的时候是去找下一个数
		j--;
	if (i < j)//边界：i，j重合，不执行操作
		array[i++] = array[j];

	while (i < j && array[i] < x)
		i++;
	if (i < j)
		array[j--] = array[i];
}

()表示i的索引位置，[]表示j的索引位置。
排序开始：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
初始：6为基准数
(6),10,12,14,3,5,[23]

1: j-
(5),10,12,14,3,[5],23

2: i+
5,(10),12,14,3,[10],23

3: j-
5,(3),12,14,[3],10,23

4: i+
5,3,(12),14,[12],10,23

5: j- 与i重合
5,3,[(12)],14,12,10,23

将基准数填入重合索引位:
5,3,6,14,12,10,23

此时以6为基准数的第一遍排序已经完成，这时候原来的7位数的排序问题就被分成了2个小数组排序的问题。这里也有一个边界问题，就是6的所在位置就是它的最终位置，所以剩下的两个无序数组为：5，3和14，12，10，23。开始递归剩下来的数组时，就可以把6的位置排除了。

1
2
3
//递归调用
quick_sort(array, left, i - 1);//i为重合处索引
quick_sort(array, i + 1, right);

第一行递归：

1
2
3
4
5
6
7
8
9
10
11
初始：5为基准数
(5),[3]

1: j未减已满足比5小
(3),[3]

2：i++
3,([3])

将基准数填入重合索引位:
3,5

此时left=0，i=1，即调用quick_sort(array, left, i - 1)->quick_sort(array,0,0);到达了函数的终止条件。这个终止条件并没有显示的写出，可以再看下函数的限制：

1
2
3
if (left < right) {
	...
}

也就是说，当left和right相同时，不满足函数的继续执行条件，而对递归的调用也在方法块中，自然也不会执行。这个递归就到此结束了。这时候第一行递归已经全部完成，执行第二行递归。这里用的数组较小，如果没排完将一直循环递归下去，直到当前组合全部排序完毕。此时3，5，6的最终位置都已完成，最后将6右边比6大的数组按照以上同样的方式递归完后，整个数组排序就完成了。

last-updated: 2018-03-15

参考：
MoreWindows 白话经典算法系列之六