快速排序详解：三种单趟实现及非递归优化

快速排序的单趟排序 - 算法思想

在开始写代码时，理解算法的思路是不可或缺的一部分。接下来我们来理解一下快速排序的算法思想（以升序排序为主）。

核心思想：在待排序的数组中，选择一个值作为 key 值。key 值的选择会影响快速排序的效率。随后定义两个变量 left 和 right，控制待排序数组的区间。假定待排序数组的第一个元素就是 key 值，此时一定要让 right 变量先动，right 往前动的目的是找比 key 值小的数。之后让 left 变量往后动，left 往前动的目的是找比 key 值大的数。将这两个数进行位置上的交换。这个过程一直持续到 right 和 left 相遇，此时将 key 值一开始所在的位置与相遇位置的值进行互换。最终达到的效果是比 key 值小的数都在 key 值的左边，比 key 值大的数都在 key 值的右边。

基于上述例子进行步骤拆解。

最终效果：

快速排序的单趟排序 - 代码实现

上述思路由 Hoare 提出。该版本代码理解起来有一定难度，书写容易出错，主要是在选最左边的值为 key 时得让 right 先走。为此，后面又出现了挖坑法、以及前后指针法。

Hoare 版本

void QuickSortPart1(int* a, int left, int right) {
    // Hoare 版本 - 单趟排序
    // 我们选择最左边为 key 值，这里我们可以采用记录下标的方式。
    int keyi = left;
    while (left < right) {
        // 先让 right 动，因为我们选取的是左边的 key
        // right 的目的是找到比 key 值小的元素的位置
        while (right > left && a[right] >= a[keyi]) {
            --right;
        }
        // 之后在让 left 动
        // left 的目的是找到比 key 值大的元素的位置
        while (left < right && a[left] <= a[keyi]) {
            ++left;
        }
        // 到这里，就说明都完成了各自的使命，最后再将它们的位置上的数交换一下。
        Swap(&a[left], &a[right]);
    }
    
    Swap(&a[left], &a[keyi]);
    keyi = left;
}