快速排序

1. 算法定义
2. 算法步骤
   1. 第一轮分区
   2. 第二轮分区

算法定义

快速排序采用”分而治之”的思想，通过选择基准值（pivot）将数组分为两部分，左边小于基准值，右边大于基准值，然后递归处理两个子数组。

算法步骤

先选择基准值pivot，一般情况下选择第一个或最后一个，步骤如下：

1. 左指针逐个格子向右移动，当遇到大于或等于基准值时停下来；
2. 右指针逐个格子向左移动，当遇到小于或等于基准值时停下来；
3. 将两个指针指向的值交换；
4. 重复1-3步骤，直到两个指针重合，或左指针移动到右指针的右边；
5. 将基准值与左指针指向的值交换；

对数组 [0,5,2,1,6,3] 排序：

这里选择pivot=3，left、right表示数组的下标。

第一轮分区

pivot=3, left=1, right=5

1. left=1，arr[1]=0 < 3, left++
2. left=2, arr[2]=5 > 3, 停止移动，启动右指针
3. right=5, arr[5]=6 > 3, right–
4. right=4, arr[4]=1 < 3, 停止移动
5. 交换arr[2]和arr[4]，数组变成： [0,1,2,5,6,3]
6. 再次启动左指针，left=3, arr[3]=2 < 3, left++
7. left=4, arr[4]=5 > 3, 停止移动，启动右指针
8. right=4, arr[4]=5 > 3, 停止移动， 交换arr[4]和pivot，数组变成： [0,1,2,3,6,5]

第二轮分区

将数组已基准值分为[0,1,2]、[3,6,5]进行重复第一轮分区的操作