前后指针版本

基本思路：：需要两个指针，一个指针命名cur，一个指针命名prev；

1.选择数组的第一个元素下标作为基准值key。

2.初始化两个指针cur和prev，分别指向数组的起始位置和起始位置的下一个位置。

3.当cur遇到比keyi的大的值以后，只需要++cur，因为他们之间的值都是比key大的值，

4.如果cur指针指向的元素小于基准值，先将prev指针向右移动一位，然后在将快指针指向的元素与慢指针指向的元素交换。

5.重复步骤3到步骤4，直到cur指针超出数组范围。结束循环.

6.将基准值的元素与prev指针位置的元素交换。此时基准值的左边元素都是比基准值小或者等于基准值，右边都比他大或者等于基准值。

7.最后返回prev下标。

单趟排序：

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

• 代码实现

// 前后指针版本
int Part_Sort3(int* a, int left, int right)
{
    int keyi = left; // 基准值的索引
    int prev = left; // 前指针
    int cur = left + 1; // 后指针
    while (cur <= right)
    {
    //如果当前元素小于基准值，将其与前指针指向的元素交换，并移动前指针
        if (a[cur] < a[keyi])
        {
          //这样写每次相同的元素都要交换 
            ++prev;
            swap(&a[prev], &a[cur]);
        }
        //可以优化成这样，这样相同下标位置的值就不用交换
    /*if (a[cur] < a[keyi] && ++prev != cur)
        {
            swap(&a[prev], &a[cur]);
        }*/
        ++cur;
    }
    swap(&a[prev], &a[keyi]); // 将基准值放到正确的位置上
    return prev; // 返回基准值的索引
}

以上代码大家可以自己手动模拟一下，配合着代码相信你们会更加能吃透.

三路划分版本

快速排序的三路划分是为了解决数组中存在大量重复元素时，快速排序算法性能下降的问题。在传统的快速排序算法中，选择一个基准元素，将数组划分为两个子数组，其中一个子数组中的元素都小于基准元素，另一个子数组中的元素都大于基准元素，然后对两个子数组进行递归排序。

然而，当数组中存在大量重复元素时，传统的快速排序算法会导致不必要的比较和交换操作，从而降低算法的效率。三路划分的主要目的是将数组划分为三个部分，分别存放小于、等于和大于基准元素的元素，以减少不必要的比较和交换操作。

通过三路划分，可以将相等的元素集中在一起，减少了对相等元素的重复比较和交换操作，提高了算法的效率。尤其在面对存在大量重复元素的情况下，三路划分可以有效地改善快速排序的性能。

三路划分本质:

1、小的甩到左边，大的甩到右边

2、跟key相等的值推到中间

• 三路划分的基本思想是将数组分成三个部分，分别存放小于、等于和大于基准元素的元

素。

基本思路：

1.选择一个基准元素。（通常是数组的第一个元素）

2.初始化三个指针：begin指针指向基准值的索引位置，cur指针指向begin + 1的位置，end指针指向数组末尾的位置

3.从数组的起始位置开始遍历到末尾位置。

4.a[c] < key如果当前元素小于基准元素，则将当前cur指针指向的元素交换到begin指针的位置，并将begin指针右移，cur指针右移。

5.a[c] > key如果当前cur指针元素大于基准元素，则将当前cur指针指向元素交换到end指针的位置，并将end指针左移。由于交换后的元素是未经比较的新元素，所以cur指针不移动。

6.a[c] == key如果当前元素等于基准元素，则将cur指针右移。

7.重复步骤4-6，直到cur指针遇见end指针则遍历完成。循环结束。

8.最后， 数组被划分为了小于基准元素、等于基准元素和大于基准元素的三个部分。接下来，需要对小于和大于基准元素的两个部分分别进行递归排序。

• 对小于基准元素的部分进行递归排序：将小于基准元素的部分作为新的子数组，重复进行

上述三路划分和递归排序的过程。

• 对大于基准元素的部分进行递归排序：将大于基准元素的部分作为新的子数组，重复进行

上述三路划分和递归排序的过程。

• 代码实现 (因为有可能 划分 出来是一个区间，我就直接在一个函数里面操作了，不封装

其他函数来完成了)

• 为了更仔细的体会，我自己手动模拟一下一组数据,

• 最后对小于和大于基准元素的两个部分分别进行递归排序。

//三路划分版本：解决数组中存在大量重复元素
//三路划分本质:
//1、小的甩到左边，大的甩到右边
//2、跟key相等的值推到中间
void Quicl_Sors_Dfp(int* a, int left, int right)
{
    if (left >= right)
        return;  
    int key = a[left];
    int begin = left;
    int cur = left + 1;
    int end = right;
    while (cur < end)
    {
        //a[c] < key，交换c和b位置的值，++b，++c
        if (a[cur] < key)
        {
            swap(&a[cur], &a[begin]);
            ++cur;
            ++begin;
        }
        //a[c] > key，交换c和e位置的值，--e
        else if (a[cur] > key)
        {
            swap(&a[cur], &a[end]);
            --end;
        }
        //a[c] == key，++c
        else
        {
            ++cur;
        }
    }
    //小  【b - e 相同】  大
    //[left begin-1] [begin end] [end+1 right]
    Quicl_Sors_Dfp(a, left, begin - 1);
    Quicl_Sors_Dfp(a, end + 1, right);
}