快速排序中的分治思想
今天我们利用分治法实现一维数组的快速排序。
首先，我们回顾分治算法的思想：就是把一个复杂的问题分成两个或更多的相同或相似的问题，再把子问题分成更小的子问题......直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
前面的课程，我们已经通过“二分查找”实例对分治算法进行了学习和理解。今天我们还是通过一个实例来进一步理解分治算法的思想。今天的实例是对一维数组的快速排序。
快速排序的思路是这样的：对于一个无序的一维数组。首先选择一个基准数，然后把数组中的所有元素与该基准数进行比较，并把所有小于基准数的数放在基准数的左边，把大于基准数的数放在基准数的右边，这是一轮基准数位置的确定，即通过这一轮处理，这个基准数就找到了排序后它所应该在的位置。下面分别对基准数左边的数列（无序的）和基准数右边的数列（无序的）进行上述类似的操作，直到所有的数都确定位置为止。整个数组就变成了一个由小到大的有序序列。
根据上面的描述，我们来一步步思考完成整个数组的排序，要做哪些工作，我们以如下的一维数组为例：
第一步：
确定一个基准数：我们一般的把数组的第一个元素作为基准数。这里，我们确定6为基准数。
（下面就是要确定基准数6的位置，必须把小于6的数都放在6的左边，大于6的数都放在6的右边。就是后面的数要与6比较，然后还要交换位置。）
第二步：
后面的数与基准数进行比较，怎样比较这个是关键。具体是这样做的：
2.1我们设定两个探测指针i和j，分别指向数组最左边的数和最右边的数的位置。如下图所示：
2.2先从右边开始寻找小于6的数，即a[j]与6进行比较，如果a[j]>=6，则j--，继续向前探测，直到发现一个数小于6时，右边停止探测。比如上述的数组，开始探测时，a[9]>6，则j--后，j=8，继续比较a[8]>6，j继续减1，j=7，比较a[7]<6，这时候找到一个小于基准数6的数，右边就停止探测。
2.3然后从左边开始寻找大于6的数，即a[i]与6进行比较，如果a[i]=<6，则i++,继续向后探测，直到发现一个数大于6时，左边也停止探测。比如上面的数组，左边开始探测，a[0]=<6，则i++，这时候i=1，继续比较a[1]<6，i继续加1，这时候i=2，比较a[2]<6，i再加1，i=3，继续比较a[3]>6，这时候找到一个大于基准数6的数，左边也停止探测。
2.4这时候右边找到一个小于基准数6的数，位置在j=7；左边找到一个大于基准数6的数，位置在i=3。如下图所示：
2.5下面我们交换位置i=3和位置j=7上的两个数。交换后如图所示：
第三步：
下面的步骤就是探测器j继续向前探测， i继续向后探测，重复步骤2的操作，右边找到小于6的数，左边找到大于6的数，停止探测，进行交换。比如上述的数组，j=6的时候，探测到4小于6，停止，i=4的时候探测到9大于6，也停止，这时候交换数组位置4和6上的数，即9和4，交换后的结果如图所示：
第四步：
继续探测，即先右边j继续向前探测，这时候j=7，探测到a[7]<6，j停止探测，然后左边i继续向后探测，发现i和j相等了，即相遇了，这时候说明了所有的数都探测过了，即探测结束了，我们把基准数6和最后一个探测的数3进行位置交换。交换后的示意图如下：
（交换前）
（交换后）
到此为止，第一轮探测和确定基准数的位置结束。我们已经找到了第一个数6在未来由小到大的有序数组中的位置。我们从图中可以看到6的左边的数都比6小，右边的数都比6大。也就是说经过这一轮的操作，我们已经确定了一个数的位置，下面就是继续确定其它数的位置。
如何确定其它数的位置呢？同学们可以看到，6的左边是一个无序数组，6的右边也是一个无序的数组，我们完全可以按照前面的操作实现确定每个子数组的第一个基准数的位置。只不过数组的规模变小了。这是不是就是我们所说的“分治算法”的思想呢？
下一步就是确定基准数3的位置和基准数9的位置。然后依次类推，直到子数组的长度变为1，即完成了所有数的位置确定。
程序代码
void quickSort(int left, int right, vector<int>& arr)
{
if(left >= right)
return;
int i, j, base, temp;
i = left, j = right;
base = arr[left]; //取最左边的数为基准数
while (i < j)
{
while (arr[j] >= base && i < j)
j--;
while (arr[i] <= base && i < j)
i++;
if(i < j)
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//基准数归位
arr[left] = arr[i];
arr[i] = base;
quickSort(left, i - 1, arr);//递归左边
quickSort(i + 1, right, arr);//递归右边
}
最后需要说明的是：基准数可以选数组第一个元素，也可以选数组最后一个元素，如果选择数组第一个元素，探测就从右边开始，如果选择数组最后一个元素，探测就从左边开始。
长按二维码添加关注