快速排序是一种基于分治思想的排序算法，它能够以极快的速度将一个乱序的数组重新排列成有序的序列。不仅如此，快速排序还具有简洁的实现代码和良好的可扩展性，成为最受欢迎的排序算法之一。接下来，让我带你了解一下它的魅力吧！💫

快排基本思想:分而治之

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法.

快速排序的核心思想是“分而治之”。它将一个未排序的数组划分为两个子数组，然后对这两个子数组分别进行排序，最后再将排好序的子数组合并在一起。这个过程在递归的帮助下不断重复，直到整个数组有序为止。这种将问题切分成更小的子问题处理的方法，使得快速排序能够高效地处理大规模的数据。🌟

快速排序的核心操作是“划分”，通常是选择一个基准元素，将返回的基准位置分为左右两边，数组中比基准元素小的移到基准元素的左边，比基准元素大的移到基准元素的右边。这个过程称为“分区”，它保证了在完成一轮分区后，基准元素的位置是确定了的。接下来，基准元素的左右子数组将分别作为新的子问题继续递归处理。直到所有元素都排列在相应位置上为止。💥

1. div就在最终位置(排好序的位置)
2. 左边有序，右边有序，整题就有序了
3. 细节已写在代码注释上

// 假设按照升序对a 数组中[left, right]区间中的元素进行排序
void QuickSort(int* a, int left, int right)
{
//1、区间只有一个值
//2、区间不存在  就无需进行递归了
//递归的结束条件是子数组的长度小于等于1，此时子数组已经有序，不需要再进行排序。
 if(left >= right )
   return;
 // 按照基准值对a数组的 [left, right]区间中的元素进行划分
 int div = partSort(a, left, right); 
 //  返回的div已经确定了位置，无需在递归,只需要递归他的左右区间
 // [begin, div-1] div [div+1, end]
 // 划分成功后以div为边界形成了左右两部分 [left, div-1] 和 [div+1, right)
 // 递归排[left, div-1]
 QuickSort(a, left, div-1);
 // 递归排[div+1, right]
 QuickSort(a, div+1, right);
}

上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

• 将区间按照基准值划分为左右两半部分的常见方式有：

1.双路快排（三种方法）

 1. hoare版本

 2. 挖坑法版本

 3. 前后指针版本

2.三路划分

当然我们还会介绍我们的非递归方法完成快速排序.

以上的 非递归方法，双路快排，三路划分版本只需要学会两个即可 双路快排（任选之一方法），与非递归版本.

双路快排（三种方法）

hoare版本

Hoare版本的基本思想是::

选择序列的第一个元素作为基准值，并分别从序列的两端开始向中间遍历，交换不符合规则的元素，直到两个指针相遇。然后将基准值与指针相遇的位置的元素交换，此时基准值左侧的元素都小于等于它，右侧的元素都大于等于它。再对左右两个子序列分别递归进行同样的操作，直到排序完成。

单趟排序：

首先我们要确定第一个元素为基准值，命名为key.先从右边指针移动，查找比基准值（key）要少的值，在从左边指针开始移动，查找比基准值（key）要大的值，然后左右指针交换，直到两个指针相遇结束。将基准值与指针相遇的位置的元素交换. 此时基准值的左边元素都是比基准值小或者等于基准值，右边都比他大或者等于基准值。最后返回两个指针相遇位置下标

然后返回key，在递归他的左右区间，重复此过程，就完成整个排序了.蓝色标记的是基准值

• 代码实现

// Hoare版本
int Part_Sort1(int* a, int left, int right)
{
    int midIndex = GetMidIndex(a, left, right); // 获取基准值的索引
    swap(&a[left], &a[midIndex]); // 将基准值移到数组最左边
    int keyi = left; // 基准值的索引
    while (left < right)
    {
        // 右边找小于基准值的元素
        while (left < right && a[right] >= a[keyi])//left < right防止越界
        {
            right--;
        }
        // 左边找大于基准值的元素
        while (left < right && a[left] <= a[keyi])//left < right防止越界
        {
            left++;
        }
        swap(&a[left], &a[right]); // 交换左右两边的元素
    }
    swap(&a[keyi], &a[right]); // 将基准值放到正确的位置上
    return right; // 返回基准值的索引
}
void QuickSort(int* a, int left, int right)
{
 if(left >= right )
   return;
 // 按照基准值对a数组的 [left, right]区间中的元素进行划分
 int div = part_Sort1(a, left, right); 
 //  返回的div已经确定了位置，无需在递归,只需要递归他的左右区间
 // [begin, div-1] div [div+1, end]
 // 划分成功后以div为边界形成了左右两部分 [left, div-1] 和 [div+1, right)
 // 递归排[left, div-1]
 QuickSort(a, left, div-1);
 // 递归排[div+1, right]
 QuickSort(a, div+1, right);
}

常见误区

• 常见误区1: 为什么中间两个while循环中判断条件是 a[right] >= a[keyi] 和 a[left] <=

a[keyi] 还要继续做++ 和 – 的操作尼？

其实很好理解，举个案例就完全清晰了.

假如是 a[right] > a[keyi] 和 a[left] < a[keyi]

假设 left 和 right 都达到了和key相同元素位置，就会造成一直交换，a[right] > a[keyi] 和 a[left] < a[keyi]没有机会进入循环做++和- -操作.最后造成死循环.

• 常见误区2: 为什么left的起始位置不是在keyi的后面，即keyi+1.

如果是写成 left = keyi + 1 是起始位置那这样对吗.

跟上面一样举个案例就完全清晰了.

此时left是从key+1出发的，right一路向左移动找比key小的，直到遇见了left.最后循环结束，将基准值与指针相遇的位置的元素交换.

如图所示，right 和 left 在 keyi+1 的位置相遇，可能导致错误的交换。因此，要避免这个问题，确保 left 不从 keyi+1 开始。

• 常见误区3: 能不能先从右边指针开始移动。

直接说结果: 如果是从左边做基准值是不行的，大家可以拿这个例子试试 {6,1,2,7,9,3,4,5,10,8}模拟一下过程.

结论：

1.左边做key，右边先走; 保障了相遇位置的值比key小

2.右边做key，左边先走; 保障了相遇位置的值比key大

我们说下这一种情况：左边做key，右边先走; 保障了相遇位置的值比key小 or 就是key

L和R相遇无非就是两种情况，L遇R和R遇l

1.情况一: L遇R，R是停下来，L在走，R先走，R停下来的位置一定比key小相遇的位置就是R   停下的位置，就一定比key要小.

2.情况二: R遇L，在相遇这一轮，L就没动，R在移动，跟L相遇，相遇位置就是L的位置，L的位置就是key的位置 or 交换过一些轮次，相遇L位置一定比key小

其实大家举个反例推理一下思路会更加清晰,一目了然了.

挖坑法版本

挖坑法版本相比hoare版本更加好理解，坑也没有hoare版本那么多，虽然他叫挖坑法哈哈.但是他会自己填坑.其思路其实是差不多的.

基本思想：

• 选择基准元素（通常是数组的第一个元素）。坑一开始的位置 (通常也是数组第一个元素

下标的位置) 。

• 从数组的右端开始移动，找到一个比基准元素小的元素，将其填入所在的坑位置，然后自

己形成一个新坑。

• 在从数组的左端开始移动，找到一个比基准元素大的元素，将其填入上一步形成的坑中。

然后自己在形成一个新的坑。

• 重复步骤2和步骤3，直到左右指针相遇。
• 循环结束后将基准元素放置到最后一个坑中。
• 返回最后一个坑位置下标

单趟排序：

• 为了更仔细的观看，我自己手动模拟一下,

通过这种方式，每一趟排序都会将一个基准元素放置到正确的位置上，并形成一个新的坑，然后再对左右两部分进行排序。这样不断重复，直到整个数组有序。挖坑法的关键在于通过交替填坑的方式实现元素的分割和排序。

每一趟的递归我就不写了这里，大家可以看看hoare版本那个图，只是单趟处理数据的方式不一样.

• 代码实现

// 挖坑法
int Part_Sort2(int* a, int left, int right)
{
    int midIndex = GetMidIndex(a, left, right); // 获取基准值的索引
    swap(&a[left], &a[midIndex]); // 将基准值移到数组最左边
    int key = a[left]; // 基准值
    int tmp = left; // 坑的位置
    while (left < right)
    {
        // 右边找小于基准值的元素
        while (left < right && a[right] >= key)
        {
            right--;
        }
        a[tmp] = a[right]; // 将找到的元素放入坑中
        tmp = right;
        // 左边找大于基准值的元素
        while (left < right && a[left] <= key)
        {
            left++;
        }
        a[tmp] = a[left]; // 将找到的元素放入坑中
        tmp = left;
    }
    a[tmp] = key; // 将基准值放入坑中
    return tmp; // 返回基准值的索引
}
void QuickSort(int* a, int left, int right)
{
  if(left >= right )
    return;
 // 按照基准值对a数组的 [left, right]区间中的元素进行划分
    int div = part_Sort2(a, left, right); 
 //  返回的div已经确定了位置，无需在递归,只需要递归他的左右区间
 // [begin, div-1] div [div+1, end]
 // 划分成功后以div为边界形成了左右两部分 [left, div-1] 和 [div+1, right)
 // 递归排[left, div-1]
   QuickSort(a, left, div-1);
 // 递归排[div+1, right]
   QuickSort(a, div+1, right);
}