图解快速排序（c++、递归）c/c++猫叔压力大-

假设有如下数组：

A = {15,10,6,1}
B = {1}
C = {20,5}

对数组进行从小到大的排序，随机取一个数组里的值记为BaseValue，
然后将所有小于BaseValue值放在左边，所有大于BaseValue的放在右边（相等的就不动了）。
对于数组B来说不用进行操作就完成了目标，对于C来说进行一次上述操作就能完成排序。

但是对A数组来说就不是那么简单了。

我们用递归的方式来对数组进行拆分，直到数组长度<= 1（也就是B数组一样的状态）

1.先选择数组第一位作为随机值保存为基准值BaseValue,并将第一位用做调换位置的空位。

注意：有红色斜杆的格子意思是空位可覆盖。

2.向左遍历，发现arr[3]比BaseValue值小，放到左边第一个空位

3.当前空位在arr[3]

4.把大于BaseValue的放在右边空位

5.当前空位在arr[1]

6.重新从右向左遍历，发现arr[2] <= BaseValue ,放到左边空位

7.当 i <= j的时候，终止while循环

8.将基准值放到当前空位 arr[i]或arr[j].这样所有小于BaseValue的都在左边，大于的都在右边了。

9.再将数组拆分成左右俩个部分（不需要包含基准值了，位置已经正确）通过递归拆分成越来越小的部分，

直到startIndex >= endIndex。

10.如果选择第一位作为基准值必须先从右往左遍历，选择最后一位作为基准值就必须从左往右开始遍历。

 void qsort1(std::vector<int> &v, int startIndex, int endIndex) {  if(startIndex >= endIndex)   return;   int tmp, i,j, BaseValue;  i = startIndex;  j = endIndex;  //取数组第一个值作为基准值 根据大小的对比将数组分成左右俩边  //存储了起始位置的值，为了空出一个位置来做调换。  BaseValue = v[startIndex];   while(i < j)  {   //从右开始向左遍历，找到小于基准值的那个数值的索引j(等于基准值的不管，跳过)   while(i < j && v[j] >= BaseValue)    --j;   //将小于基准值的放到数组的左边   v[i] = v[j];   //从左向右遍历，找到大于基准值的那个数值的索引i(等于基准值的不管，跳过)   while(i < j && v[i] <= BaseValue)    ++i;    //将大于基准值的放到数组的右边   v[j] = v[i];   }  //将基准值放回当前的空位上  v[i] = BaseValue;   //继续对当前基准值左、右边的内容进行重复的操作,直到拆分的数组长度<=1也就是startIndex>=endIndex  //基准值的位置(当前是i和j,i=j)就不用变了。  qsort1(v, startIndex, i - 1);  qsort1(v, i + 1, endIndex);  }  int main(int argc, char const *argv[]) {    std::vector<int> arr = {6,1,1,3,15,6,8,20,2,7,7,10};   qsort1(arr, 0, arr.size()-1);  printf("n快速排序的结果：n");   for (int i = 0; i < arr.size(); ++i)  {   printf("%d ", arr[i]);   }   return 0; }

如果有用顺手点个赞不过分吧？