本文为原创文章，未经本人允许，禁止转载。转载请注明出处。

1.快速排序

排序算法的思想非常简单，在待排序的数列中，我们首先要找一个数字作为基准数（pivot）。为了方便，我们一般选择第1个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。这是典型的分治思想。

快速排序是对冒泡排序的一种改进。

2.快速排序图解

快速排序的操作是这样的：首先从数列的右边开始往左边找，我们设这个下标为i，也就是进行减减操作（i–），找到第1个比基准数小的值，让它与基准数交换；接着从左边开始往右边找，设这个下标为j，然后执行加加操作（j++），找到第1个比基准数大的值，让它与基准数交换；然后继续寻找，直到i与j相遇时结束，最后基准数所在的位置即k的位置，也就是说k左边的值均比k上的值小，而k右边的值都比k上的值大。

假设待排序序列（选择第一个元素作为基准数，加粗显示）：

j
47	29	71	99	78	19	24	47
							i

此时，i所指的元素为47，等于基准数，执行减减操作：

j
47	29	71	99	78	19	24	47
						i

此时，i指的是24，小于基准数，因此将其和基准数调换位置：

j
24	29	71	99	78	19	47	47
						i

现在开始移动j，对j执行加加操作：

	j
24	29	71	99	78	19	47	47
						i

此时，j指的是29，小于基准数，不需要交换位置，对j继续执行加加操作：

		j
24	29	71	99	78	19	47	47
						i

此时，j指的是71，大于基准数，交换位置：

		j
24	29	47	99	78	19	71	47
						i

此时重新开始移动i，对其进行减减操作：

		j
24	29	47	99	78	19	71	47
					i

此时，i指的是19，小于基准数，交换位置：

		j
24	29	19	99	78	47	71	47
					i

对j执行加加操作：

			j
24	29	19	99	78	47	71	47
					i

99>47，交换位置：

			j
24	29	19	47	78	99	71	47
					i

移动i：

			j
24	29	19	47	78	99	71	47
				i

47<78，不需要交换位置，继续移动i：

			j
24	29	19	47	78	99	71	47
			i

此时i=j，第一轮排序结束，基准数47左侧的值都小于等于47，右侧的值都大于等于47。

然后分别对左侧序列（24、29、19）和右侧序列（78、99、71、47）重复执行上述步骤，直至各个分区只有一个数为止。

3.代码地址

快速排序

4.参考资料

快速排序算法详解（原理、实现和时间复杂度）

【算法基础】【排序】快速排序

归并排序

1.快速排序

2.快速排序图解

3.代码地址

4.参考资料

CATALOG

FEATURED TAGS