此时 left < right 交换两者下标对应元素后 left++，right--，各变量对应关系如图三所示：
图三：
此时left和while仍满不测层while循环条件，继续重复上述步调直至如图四所示。
图四：
此时已经跳出外层循环，将 keyi 与 right 对应下标元素交换后，此时 right 左侧元素均小于 5，右侧元素均大于5，而right就是我们所找的基准值。
递归实现部分代码：
void QuickSort3(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int key = _QuickSort3(arr, left, right);
QuickSort3(arr, left, key - 1);
QuickSort3(arr, key+1, right);
}
复制代码
递归过程：
对于初学者而言，在分析过程中容易忽略 left值 和 right值 的变化，在上述递归的过程中，可以看到，key的改变会影响下次递归 left 和 right 的值，正是 left 和 right 改变，才能使递归满足停止条件，从而返回。 注：其他题目。 1、为什么外层的 while 要去等号？ 分析：
以下图为案例：
假设坑（hole）的位置在 left 处，并且将 left 处对应的元素临时存放在 keyi 中，我们先从 right 开始向左找比keyi小，找到第一个位置处时，将 hole 位置处的值赋为 right 位置处的值，同时将 hole 移动到 right 位置处，此时新坑位于 right 处，此时各变量对应关系如下图所示：
然后我们再从 left 向右开始找比keyi大的值，找到第一个位置处 9 时，我们重复上述的过程，把元素 9 赋值给 hole 位置处，然后把 hole 移到 left 位置处，此时各变量对应关系如下图所示：
注：其实此时我们能够发现，left 和 right 位置对应的值已经发生改变，第二次循环开始时，已然满足内层循环的 while 条件，因此 right 可以继续向左减减找小值，而 left 也能够向右加加找大值。
重复上述过程，终极各个变量对应关系如下图：
注：为什么内层循环要多一个 left < right 的判断条件? 分析：可以看到，如果没有这个条件，left 会继续向右找大值，即到下标为5的位置处，会让 hole 多一次变化，而这一次变化，会导致所找的基准值发生错误，因此内层的 while 循环需要多这一个条件。当while循环结束时，我们再把临时值 keyi 赋值给 hole 位置处，此时 hole 位置就是对应基准值的位置，各个变量关系如下图所示
2.2.1.3：lumoto法
找基准值代码：
int _QuickSort(int* arr, int left, int right)
{
int prev = left;
int keyi = left;
int cur = prev + 1;
while (cur <= right)
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
swap(&arr[cur], &arr[prev]);
}
cur++;
}
swap(&arr[keyi], &arr[prev]);
return prev;
}
复制代码
图例分析：
起始时，各变量对应关系图下图：
界说一个前后变量 prev 和 cur，同时界说临时值 keyi = 5 。当 cur 中对应的值小于 keyi时，同时 ++prev 不等于 cur 时，我们让 prev 对应的值与 cur 对应的值交换，内层循环的 if 隐含着一些码字菜鸟（我）容易忽略的信息，为什么++prev 而不是 prev++，首先这个条件是为了克制重复交换，其次 ++prev 后此时虽然不满足 if 条件，但是 prev 的值照旧 +1 了，因此此时 prev 和 cur 已经指向了同一个位置，只不过不会发生交换而已，各个变量关系如下图所示：
判断完 if 条件后，让 cur 持续++。观察上述数组，能够发现，3 背面的两个元素均大于临时值 keyi，此时 prev会来到元素 2 的位置处，而 2 已经满足内层 if 条件，因此我们将 prev+1 后 与 cur 位置对应的元素交换，此时各个变量关系对应如图所示：
重复上述过程，终极各个变量的对应关系如图所示：
当外层 while 循环结束时，我们交换 下标0 与 prev位置对应的元素，即得到了我们想要的数组，同时 prev 为基准值对应的位置处。
2.2.1.4：递归版本快速排序的特性：
前言：非递归版本的快速排序是借助栈的方式来实现的，将数组首尾下标入队后，取栈内两个数据作为数组尾和头再出栈，通过lumoto方法找到该数组对应的基准值key，再将 left ~ key-1 的下标，以及 key+1 ~ right 的下标入堆，重复上述过程，直至堆中不再有任何元素。 注：因为传递的是数组的地址，入栈的也只是数组对应的下标，当出栈时，固然可以通过下标去访问原先的数组，同时令原先数组发生改变。
代码：
void QuickSortNonR(int* arr, int left, int right)
{
ST s;
STInit(&s);
STPush(&s, left);
STPush(&s, right);
while (!BoolEmpty(&s))
{
int end = STTop(&s);
STPop(&s);
int begin = STTop(&s);
STPop(&s);
int prev = begin;
int keyi = begin;
int cur = prev + 1;
while (cur <= end) //找基准值同时对数组进行排序
{
if (arr[cur] < arr[keyi] && ++prev != cur)
{
swap(&arr[cur], &arr[prev]);
}
cur++;
}
swap(&arr[keyi], &arr[prev]);
int key = prev;
if (key - 1 > begin) //模拟返回的过程，若不满足条件则不入栈
{
STPush(&s, begin);
STPush(&s, key-1);
}
if (key + 1 < end)
{
STPush(&s, key+1);
STPush(&s, end);
}
}
}
复制代码
图例演示一下这个while循环的过程：
初始时，将下标 0 和下标 8 入栈
由此我们开始分析while循环部分，以栈为空作为外层 while 循环的结束条件
进入外层 while 循环后取栈顶元素并且出栈，这种取元素再出栈的操纵包管了我们能够取到我们想要的元素，同时将这两个元素作为 lumoto法找基准值中的 cur 的结束位置和 prev 初始巨细。 注：注意入栈的次序，入栈次序会影响后续读取栈顶元素时，begin 和 end 的取值。
当我们取到下标 0 和 8 时，通过下标访问数组元素，同时基于lumoto法实现找基准值的方法，这里不在过多追叙，此时各变量关系如图所示：
此时显然满足 begin < key - 1、 key+1 < end ，因此将下标 begin、key-1、key+1、end 分别入栈，当第二次进入循环时，首两次出栈会取到下标 key+1 和 end ，这正对应了2.2.2.1中提到的递归过程一样，left的值发生变化的过程，（编者菜，会觉得left一直等于0，其实正如刚才的递归过程一样，每个子节点的向右递归left值会发生改变），于是我们先对这对范围内的数组进行找基准值和分列操纵，操纵完成后，再次向栈中，push下标，直至不在满足 if 条件为止，不过此时栈中元素不为空，因为原先找的基准值 4 左边的数组尚未进行排序，接下来从栈中取出的元素，正是对左半部分进行找基准值和排序的操纵，如此循环往复直至结束。
上图为对基准值右半部分的循环过程，可以看到当不满足 begin < key - 1、 key+1 < end 时，不再入栈，右半部分循环结束，此时栈中还保存着基准值左半部分的下标位置，取出栈内元素后，可以对左半部分进行找基准值和分列操纵。
