快速排序的partition策略分析

快速排序的partition策略分析一、快速排序概述

快速排序是一种高效的排序算法，其核心思想是通过分治策略将大问题分解为小问题来解决。算法的主要步骤包括：

1.选择一个基准元素（pivot）

2.对数组进行分区（partition），使得基准元素左侧的所有元素都不大于它，右侧的所有元素都不小于它

3.递归地对左右两侧的子数组进行相同的操作

二、Partition策略详解

Partition是快速排序中实现分治的关键步骤，其目标是按照基准元素将数组划分为两个子数组。以下是几种常见的Partition策略：

（一）Hoare分区法

Hoare分区法是最经典的Partition策略，其基本步骤如下：

1.选择基准元素，通常选取第一个或最后一个元素

2.初始化两个指针i和j，分别指向数组的开始和结束

3.移动指针i，直到找到一个不小于基准的元素

4.移动指针j，直到找到一个不大于基准的元素

5.交换i和j指向的元素

6.重复步骤3-5，直到i和j相遇

7.将基准元素与i（或j）相遇的位置的元素交换，完成分区

优点：

(1)平均时间复杂度为O(n)

(2)实现简单，代码可读性强

缺点：

(1)最坏情况下时间复杂度为O(n²)（当基准元素选择不当时）

（二）Lomuto分区法

Lomuto分区法是另一种常用的Partition策略，其步骤如下：

1.选择基准元素，通常选取最后一个元素

2.初始化一个指针p，指向比基准元素小的元素的最后一个位置

3.遍历数组，对于每个小于基准的元素，将其与p指向的元素交换，并移动p

4.最后将基准元素与p指向的元素交换

优点：

(1)实现更简单

(2)代码更直观

缺点：

(1)平均性能略逊于Hoare分区法

(2)最坏情况时间复杂度为O(n²)

（三）3-wayPartition

3-wayPartition将数组划分为三个部分：小于基准、等于基准、大于基准的元素，适用于包含大量重复元素的数组。其步骤如下：

1.选择基准元素

2.初始化三个指针lt、gt和i，分别指向小于基准、大于基准的元素的最后位置和当前遍历位置

3.遍历数组：

-如果当前元素小于基准，交换与lt+1的元素，移动lt和i

-如果当前元素等于基准，直接移动i

-如果当前元素大于基准，交换与gt-1的元素，移动gt，i不移动

4.最后将基准元素放到正确的位置

优点：

(1)对于包含大量重复元素的数组效率更高

(2)可以避免不必要的比较

缺点：

(1)实现相对复杂

(2)额外空间复杂度为O(1)

三、Partition策略的性能分析

（一）时间复杂度

1.平均情况：所有Partition策略的时间复杂度均为O(n)

2.最坏情况：

-Hoare分区法：当数组已经有序或倒序时，时间复杂度为O(n²)

-Lomuto分区法：同样如此

-3-wayPartition：即使最坏情况下也能保持O(n)

（二）空间复杂度

所有Partition策略的空间复杂度均为O(logn)（递归栈空间），3-wayPartition需要额外的O(1)空间。

（三）实际应用建议

1.对于一般情况，Hoare分区法更优

2.对于包含大量重复元素的数组，3-wayPartition更高效

3.Lomuto分区法在实现简单性上更有优势

四、Partition策略的优化措施

（一）随机选择基准元素

（二）三数取中法

从数组的首部、中部和尾部选择三个元素，取它们的中间值作为基准元素，进一步优化基准的选择。

（三）尾递归优化

在递归调用时，优先处理较小的子数组，可以减少递归深度，提升性能。

（四）小数组时切换到插入排序

当子数组规模较小时（如小于10个元素），插入排序可能更高效，可以结合使用提升整体性能。

---

一、快速排序概述

快速排序是一种基于分治（DivideandConquer）策略的高效排序算法。其基本思想是将一个待排序的原始数组分割成两个（可能不等）的子数组，其中左子数组的所有元素均小于或等于右子数组的所有元素，然后再递归地独立地对这两个子数组进行快速排序，最终实现整个数组的有序。快速排序因其平均时间复杂度低而被广泛应用。

快速排序的性能很大程度上取决于分区（Partition）步骤的效率和稳定性。分区操作的核心目标是围绕一个选定的基准元素（Pivot），重新排列数组，使得基准元素最终位于它排序后的正确位置，并且基准左侧的所有元素都不大于它，基准右侧的所有元素都不小于它。这一过程将原问题转化为两个规模更小的子问题。

二、Partition策略详解

Partition是快速排序中的关键环节，其目的是将数组分割为满足特定条件的两个部分。以下是几种常见的Partition策略及其详细说明：

（一）Hoare分区法

Hoare分区法由TonyHoare发明，是快速排序中最常用和最经典的分区策略。它的特点是使用两个指针（通常称为`i`和`j`）从数组的两端向中间扫描，并根据与基准元素的比较结果来交换元素，直到两个指针相遇。

Hoare分区法的详细步骤（StepbyStep）：

1.选择基准元素（Pivot）：

从数组中选择一个元素作为基准。常见的策略包括：

选择第一个元素。

选择最后一个元素。

选择数组首部、中部（中点）和尾部元素，然后取这三个元素的中值（例如，计算这三个元素的大小关系后取中间值）作为基准，以减少遇到最坏情况的概率。

假设数组为`arr[left...right]`，基准元素为`pivot=arr[left]`（选择第一个元素作为基准的常见做法）。

2.初始化指针：

初始化两个指针`i`和`j`。

`i`初始化为数组左边界的前一个位置，即`i=left-1`。

`j`初始化为数组右边界，即`j=right`。

3.遍历与交换：

循环条件：只要`i<j`，就继续执行分区操作。

移动指针`j`：

从右向左移动指针`j`，即`j--`。

在移动过程中，检查`arr[j]`是否小于或等于基准元素`pivot`。

如果`arr[j]<=pivot`，则说明`arr[j]`是应该位于基准左侧的元素，此时停止移动`j`。

移动指针`i`：

从左向右移动指针`i`，即`i++`。

在移动过程中，检查`arr[i]`是否大于基准元素`pivot`。

如果`arr[i]>pivot`，则说明`arr[i]`是应该位于基准右侧的元素，此时停止移动`i`。

交换元素：

如果此时`i<j`（即`i`和`j`尚未相遇），则交换`arr[i]`和`arr[j]`。这一步确保了基准左侧的元素不大于基准，基准右侧的元素不小于基准。

交换后，`i`和`j`的位置都需要更新：`i++`，`j--`。然后继续循环。

4.结束循环：

循环会持续到`i`和`j`相遇或交错，即`i>=j`。

5.放置基准元素：

当循环结束时，`i`和`j`相遇的位置（即`i==j`）是基准元素应该放置的位置。

交换基准元素`pivot`（位于`arr[left]`）与`arr[i]`（或`arr[j]`，因为`i==j`）。

最终，基准元素`pivot`位于数组中排序后的正确位置，`i`（或`j`）成为分界点。

Hoare分区法的优缺点：

优点：

(1)平均时间复杂度好，为O(n)。

(2)代码实现相对简洁。

(3)在处理重复元素较多的数组时，通常比Lomuto分区法表现更好，因为它能将大量相等的元素集中在一起，减少不必要的比较和交换次数。

(4)最坏情况发生概率相对较低（尤其是在基准选择得当的情况下）。

缺点：

(1)实现比Lomuto分区法稍复杂一些，特别是指针初始化和交换逻辑。

(2)在某些特定数据分布下，可能比Lomuto分区法有更多的交换操作。

（二）Lomuto分区法

Lomuto分区法由TonyLomuto提出，是另一种常用的Partition策略。其实现比Hoare分区法更简单直观，因此在教学和简单实现中更为常见。

Lomuto分区法的详细步骤（StepbyStep）：

1.选择基准元素（Pivot）：

通常选择数组的最后一个元素作为基准。即`pivot=arr[right]`。

2.初始化指针/变量：

初始化一个指针或索引`p`，用于标记小于基准元素的元素的最后一个位置。`p`初始化为`left-1`。

3.遍历数组：

从左向右遍历数组，依次检查每个元素`arr[i]`（从`left`到`right-1`）。

对于当前元素`arr[i]`：

如果`arr[i]<=pivot`，则说明`arr[i]`应该位于基准的左侧。

执行以下操作：

将`p`的值加1，即`p++`。

交换`arr[p]`和`arr[i]`。这一步将一个小于基准的元素移动到了小于基准元素的子数组区间的末尾。

4.结束遍历：

遍历完所有元素后，`p`的位置已经标记了小于基准元素的子数组的最后一个元素。

5.放置基准元素：

将基准元素`pivot`（位于`arr[right]`）与`arr[p+1]`交换。

交换后，基准元素`pivot`就位于它排序后的正确位置，`p+1`成为分界点，左侧所有元素都小于等于基准，右侧所有元素都大于等于基准。

Lomuto分区法的优缺点：

优点：

(1)实现非常简单，逻辑清晰，易于理解和编写代码。

(2)代码可读性高。

缺点：

(1)平均性能通常不如Hoare分区法，尤其是在数组中存在大量重复元素时。因为指针`i`总是从左向右移动，可能会进行更多不必要的比较和交换。

(2)最坏情况时间复杂度为O(n²)，例如当数组已经有序或倒序时，如果总是选择最后一个元素作为基准，每次分区只得到一个子数组，递归深度达到n。

(3)在某些情况下，可能会导致不平衡的分区，从而影响递归的效率。

（三）3-wayPartition（三向切分）

3-wayPartition是针对包含大量重复元素的数组进行优化的分区策略。它将数组划分为三个部分：小于基准的元素、等于基准的元素、大于基准的元素。这样可以避免在Hoare或Lomuto分区法中对大量重复元素进行不必要的比较和交换，从而提升效率。

3-wayPartition法的详细步骤（StepbyStep）：

1.选择基准元素（Pivot）：

通常选择数组的第一个元素作为基准。即`pivot=arr[left]`。

2.初始化指针：

初始化三个指针：

`lt`(LessThan)：指向小于基准的元素的最后一个位置，初始值为`left-1`。

`gt`(GreaterThan)：指向大于基准的元素的第一个位置，初始值为`right+1`。

`i`(Current)：当前正在检查的元素的位置，初始值为`left`。

3.遍历与分类：

当`i<gt`时，循环处理当前元素`arr[i]`：

情况1：`arr[i]<pivot`

表示`arr[i]`应该移动到基准左侧的小于部分。

将`lt`加1，`i`加1，并交换`arr[lt]`和`arr[i]`。交换后，`arr[i]`被移动到了小于部分的正确位置，`i`继续向后检查。

即：`lt++`；`i++`；`swap(arr[lt],arr[i])`

情况2：`arr[i]==pivot`

表示`arr[i]`等于基准，属于等于部分。

只需要将`i`加1，让`i`继续向后检查下一个元素。

即：`i++`

情况3：`arr[i]>pivot`

表示`arr[i]`应该移动到基准右侧的大于部分。

将`gt`减1，并与`arr[gt]`交换。交换后，`arr[i]`被移动到了大于部分的正确位置。此时`i`保持不变，因为交换过来的`arr[gt]`是一个新的元素，需要再次检查。

即：`gt--`；`swap(arr[i],arr[gt])`

4.结束遍历：

循环结束后，数组已经被划分为三个部分：

`arr[left...lt]`：所有元素都小于基准。

`arr[lt+1...gt-1]`：所有元素都等于基准。

`arr[gt...right]`：所有元素都大于基准。

5.（可选）处理等于基准的部分：

在某些实现中，可以选择递归地对小于基准和大于基准的子数组进行排序。

也可以选择不立即递归排序等于基准的部分，而是将等于基准的部分的元素收集起来，在排序完成后统一处理（例如，将这部分元素插入到最终排序数组中合适的位置）。这取决于具体的应用场景。

3-wayPartition法的优缺点：

优点：

(1)在包含大量重复元素的数组上效率极高，时间复杂度可以接近O(n)，因为它将重复元素分离出来，减少了递归的深度和比较次数。

(2)对于重复元素分布均匀的情况也能提供很好的性能。

缺点：

(1)实现相对复杂，比Hoare和Lomuto分区法更难理解和编写。

(2)需要使用三个指针，增加了代码的复杂性。

三、Partition策略的性能分析

Partition策略的选择和实现直接影响快速排序的整体性能。

（一）时间复杂度

平均情况：

对于Hoare分区法和Lomuto分区法，在平均情况下，每次Partition操作将数组大致分成大小相等的两部分（或差异不大），递归树的深度接近log(n)。每次Partition操作需要遍历整个数组（或大部分数组），时间复杂度为O(n)。因此，快速排序的平均时间复杂度为O(nlogn)。

对于3-wayPartition法，特别是当数组中存在大量重复元素时，其平均时间复杂度可以非常好，接近O(n)。

最坏情况：

最坏情况通常发生在每次Partition操作只得到一个元素大小的子数组（例如，当数组已经有序或倒序，且每次总是选择第一个或最后一个元素作为基准时）。

在这种情况下，Partition操作的时间复杂度为O(n)，而递归的深度达到n。因此，最坏情况时间复杂度为O(n²)。

3-wayPartition法在一定程度上可以缓解最坏情况的发生概率，但最坏情况时间复杂度仍然是O(n²)。

（二）空间复杂度

快速排序是原地排序算法，不需要额外的存储空间。

Partition操作本身通常只需要常数级的额外空间（用于存储基准元素和几个指针）。

但快速排序的递归调用需要栈空间来存储递归调用的上下文。在平均情况下，递归树的深度为log(n)，因此空间复杂度为O(logn)。

在最坏情况下（递归深度为n），空间复杂度为O(n)。

3-wayPartition法在实现中可能需要额外的变量，但其空间复杂度通常仍然是O(logn)（不计输入数组本身）。

（三）实际应用建议

选择哪种Partition策略取决于具体的应用场景和数据特性：

1.一般情况/教学目的：

Hoare分区法通常是首选，因为它在平均性能上更好，尤其是在处理重复元素时。

Lomuto分区法因其简单性也常被使用，特别是在不需要考虑大量重复元素的场景。

2.包含大量重复元素：

3-wayPartition法是最佳选择，可以显著提升排序效率。

3.实现简单性优先：

Lomuto分区法更容易实现和理解。

4.基准选择优化：

无论使用哪种Partition法，选择一个好的基准都非常重要。避免在每次Partition时总是选择固定位置（如第一个或最后一个）的元素。可以采用“三数取中法”（选择首、中、尾三个元素的中值作为基准）或随机选择一个元素作为基准，来减少遇到最坏情况的概率，提升算法的平均性能和鲁棒性。

四、Partition策略的优化措施

为了进一步提升快速排序的性能，可以在Partition操作或快速排序的整体实现中加入一些优化措施：

（一）随机选择基准元素（RandomizedPivotSelection）

目的：减少遇到最坏情况时间复杂度O(n²)的概率。

方法：在进行Partition之前，不从固定位置（如第一个或最后一个）选择基准，而是从待排序的子数组中随机选择一个元素作为基准。

操作：可以使用随机数生成器生成一个介于`left`和`right`之间的随机索引`randomIndex`，然后将`arr[randomIndex]`与`arr[right]`交换，这样就可以使用Lomuto或Hoare分区法（此时基准是`arr[right]`，即原`arr[randomIndex]`）。

（二）三数取中法（Median-of-Three）

目的：进一步减少选择到最坏基准元素的概率。

方法：在进行Partition之前，从待排序的子数组的第一个元素`arr[left]`、中间元素`arr[mid]`（其中`mid=left+floor((right-left)/2)`）和最后一个元素`arr[right]`中选择一个值作为基准。通常选择这三个值的中值作为基准。

操作：

1.计算中间索引`mid`。

2.比较三个元素`arr[left]`、`arr[mid]`、`arr[right]`的大小关系。

3.将这三个元素中的中值与`arr[right]`交换（或者直接将中值作为基准值）。

优点：能更好地避免在已经部分有序的数组上性能急剧下降的问题。

（三）尾递归优化（TailRecursionOptimization）

目的：减少递归调用的栈空间消耗。

方法：在递归排序时，优先处理规模较小的子数组，后处理规模较大的子数组。可以通过循环来处理较小的子数组，仅对较大的子数组进行递归调用。

原理：快速排序的递归调用形式通常是先递归左子数组，再递归右子数组。如果左子数组规模远小于右子数组，那么先递归左子数组会导致较深的递归调用栈。通过先循环处理左子数组（直到其规模小于某个阈值，如10），再递归处理右子数组，可以保持递归栈的深度大致为log(n)。

（四）小数组时切换到插入排序（InsertionSortforSmallArrays）

目的：利用插入排序在小规模数组上的高效性。

方法：当待排序的子数组规模小于某个预定的阈值（例如10或20）时，不继续使用快速排序的递归调用，而是切换到插入排序来处理这个小数组。

原理：快速排序的递归开销在小数组上可能并不划算。插入排序在处理小数组时非常快，且代码简单。这种混合策略（称为混合排序算法，如Introsort）可以结合快速排序的高效性和插入排序在小规模数据上的优势，进一步提升整体性能。

一、快速排序概述

快速排序是一种高效的排序算法，其核心思想是通过分治策略将大问题分解为小问题来解决。算法的主要步骤包括：

1.选择一个基准元素（pivot）

2.对数组进行分区（partition），使得基准元素左侧的所有元素都不大于它，右侧的所有元素都不小于它

3.递归地对左右两侧的子数组进行相同的操作

二、Partition策略详解

Partition是快速排序中实现分治的关键步骤，其目标是按照基准元素将数组划分为两个子数组。以下是几种常见的Partition策略：

（一）Hoare分区法

Hoare分区法是最经典的Partition策略，其基本步骤如下：

1.选择基准元素，通常选取第一个或最后一个元素

2.初始化两个指针i和j，分别指向数组的开始和结束

3.移动指针i，直到找到一个不小于基准的元素

4.移动指针j，直到找到一个不大于基准的元素

5.交换i和j指向的元素

6.重复步骤3-5，直到i和j相遇

7.将基准元素与i（或j）相遇的位置的元素交换，完成分区

优点：

(1)平均时间复杂度为O(n)

(2)实现简单，代码可读性强

缺点：

(1)最坏情况下时间复杂度为O(n²)（当基准元素选择不当时）

（二）Lomuto分区法

Lomuto分区法是另一种常用的Partition策略，其步骤如下：

1.选择基准元素，通常选取最后一个元素

2.初始化一个指针p，指向比基准元素小的元素的最后一个位置

3.遍历数组，对于每个小于基准的元素，将其与p指向的元素交换，并移动p

4.最后将基准元素与p指向的元素交换

优点：

(1)实现更简单

(2)代码更直观

缺点：

(1)平均性能略逊于Hoare分区法

(2)最坏情况时间复杂度为O(n²)

（三）3-wayPartition

3-wayPartition将数组划分为三个部分：小于基准、等于基准、大于基准的元素，适用于包含大量重复元素的数组。其步骤如下：

1.选择基准元素

2.初始化三个指针lt、gt和i，分别指向小于基准、大于基准的元素的最后位置和当前遍历位置

3.遍历数组：

-如果当前元素小于基准，交换与lt+1的元素，移动lt和i

-如果当前元素等于基准，直接移动i

-如果当前元素大于基准，交换与gt-1的元素，移动gt，i不移动

4.最后将基准元素放到正确的位置

优点：

(1)对于包含大量重复元素的数组效率更高

(2)可以避免不必要的比较

缺点：

(1)实现相对复杂

(2)额外空间复杂度为O(1)

三、Partition策略的性能分析

（一）时间复杂度

1.平均情况：所有Partition策略的时间复杂度均为O(n)

2.最坏情况：

-Hoare分区法：当数组已经有序或倒序时，时间复杂度为O(n²)

-Lomuto分区法：同样如此

-3-wayPartition：即使最坏情况下也能保持O(n)

（二）空间复杂度

所有Partition策略的空间复杂度均为O(logn)（递归栈空间），3-wayPartition需要额外的O(1)空间。

（三）实际应用建议

1.对于一般情况，Hoare分区法更优

2.对于包含大量重复元素的数组，3-wayPartition更高效

3.Lomuto分区法在实现简单性上更有优势

四、Partition策略的优化措施

（一）随机选择基准元素

（二）三数取中法

从数组的首部、中部和尾部选择三个元素，取它们的中间值作为基准元素，进一步优化基准的选择。

（三）尾递归优化

在递归调用时，优先处理较小的子数组，可以减少递归深度，提升性能。

（四）小数组时切换到插入排序

当子数组规模较小时（如小于10个元素），插入排序可能更高效，可以结合使用提升整体性能。

---

一、快速排序概述

快速排序是一种基于分治（DivideandConquer）策略的高效排序算法。其基本思想是将一个待排序的原始数组分割成两个（可能不等）的子数组，其中左子数组的所有元素均小于或等于右子数组的所有元素，然后再递归地独立地对这两个子数组进行快速排序，最终实现整个数组的有序。快速排序因其平均时间复杂度低而被广泛应用。

快速排序的性能很大程度上取决于分区（Partition）步骤的效率和稳定性。分区操作的核心目标是围绕一个选定的基准元素（Pivot），重新排列数组，使得基准元素最终位于它排序后的正确位置，并且基准左侧的所有元素都不大于它，基准右侧的所有元素都不小于它。这一过程将原问题转化为两个规模更小的子问题。

二、Partition策略详解

Partition是快速排序中的关键环节，其目的是将数组分割为满足特定条件的两个部分。以下是几种常见的Partition策略及其详细说明：

（一）Hoare分区法

Hoare分区法由TonyHoare发明，是快速排序中最常用和最经典的分区策略。它的特点是使用两个指针（通常称为`i`和`j`）从数组的两端向中间扫描，并根据与基准元素的比较结果来交换元素，直到两个指针相遇。

Hoare分区法的详细步骤（StepbyStep）：

1.选择基准元素（Pivot）：

从数组中选择一个元素作为基准。常见的策略包括：

选择第一个元素。

选择最后一个元素。

选择数组首部、中部（中点）和尾部元素，然后取这三个元素的中值（例如，计算这三个元素的大小关系后取中间值）作为基准，以减少遇到最坏情况的概率。

假设数组为`arr[left...right]`，基准元素为`pivot=arr[left]`（选择第一个元素作为基准的常见做法）。

2.初始化指针：

初始化两个指针`i`和`j`。

`i`初始化为数组左边界的前一个位置，即`i=left-1`。

`j`初始化为数组右边界，即`j=right`。

3.遍历与交换：

循环条件：只要`i<j`，就继续执行分区操作。

移动指针`j`：

从右向左移动指针`j`，即`j--`。

在移动过程中，检查`arr[j]`是否小于或等于基准元素`pivot`。

如果`arr[j]<=pivot`，则说明`arr[j]`是应该位于基准左侧的元素，此时停止移动`j`。

移动指针`i`：

从左向右移动指针`i`，即`i++`。

在移动过程中，检查`arr[i]`是否大于基准元素`pivot`。

如果`arr[i]>pivot`，则说明`arr[i]`是应该位于基准右侧的元素，此时停止移动`i`。

交换元素：

如果此时`i<j`（即`i`和`j`尚未相遇），则交换`arr[i]`和`arr[j]`。这一步确保了基准左侧的元素不大于基准，基准右侧的元素不小于基准。

交换后，`i`和`j`的位置都需要更新：`i++`，`j--`。然后继续循环。

4.结束循环：

循环会持续到`i`和`j`相遇或交错，即`i>=j`。

5.放置基准元素：

当循环结束时，`i`和`j`相遇的位置（即`i==j`）是基准元素应该放置的位置。

交换基准元素`pivot`（位于`arr[left]`）与`arr[i]`（或`arr[j]`，因为`i==j`）。

最终，基准元素`pivot`位于数组中排序后的正确位置，`i`（或`j`）成为分界点。

Hoare分区法的优缺点：

优点：

(1)平均时间复杂度好，为O(n)。

(2)代码实现相对简洁。

(3)在处理重复元素较多的数组时，通常比Lomuto分区法表现更好，因为它能将大量相等的元素集中在一起，减少不必要的比较和交换次数。

(4)最坏情况发生概率相对较低（尤其是在基准选择得当的情况下）。

缺点：

(1)实现比Lomuto分区法稍复杂一些，特别是指针初始化和交换逻辑。

(2)在某些特定数据分布下，可能比Lomuto分区法有更多的交换操作。

（二）Lomuto分区法

Lomuto分区法由TonyLomuto提出，是另一种常用的Partition策略。其实现比Hoare分区法更简单直观，因此在教学和简单实现中更为常见。

Lomuto分区法的详细步骤（StepbyStep）：

1.选择基准元素（Pivot）：

通常选择数组的最后一个元素作为基准。即`pivot=arr[right]`。

2.初始化指针/变量：

初始化一个指针或索引`p`，用于标记小于基准元素的元素的最后一个位置。`p`初始化为`left-1`。

3.遍历数组：

从左向右遍历数组，依次检查每个元素`arr[i]`（从`left`到`right-1`）。

对于当前元素`arr[i]`：

如果`arr[i]<=pivot`，则说明`arr[i]`应该位于基准的左侧。

执行以下操作：

将`p`的值加1，即`p++`。

交换`arr[p]`和`arr[i]`。这一步将一个小于基准的元素移动到了小于基准元素的子数组区间的末尾。

4.结束遍历：

遍历完所有元素后，`p`的位置已经标记了小于基准元素的子数组的最后一个元素。

5.放置基准元素：

将基准元素`pivot`（位于`arr[right]`）与`arr[p+1]`交换。

交换后，基准元素`pivot`就位于它排序后的正确位置，`p+1`成为分界点，左侧所有元素都小于等于基准，右侧所有元素都大于等于基准。

Lomuto分区法的优缺点：

优点：

(1)实现非常简单，逻辑清晰，易于理解和编写代码。

(2)代码可读性高。

缺点：

(1)平均性能通常不如Hoare分区法，尤其是在数组中存在大量重复元素时。因为指针`i`总是从左向右移动，可能会进行更多不必要的比较和交换。

(2)最坏情况时间复杂度为O(n²)，例如当数组已经有序或倒序时，如果总是选择最后一个元素作为基准，每次分区只得到一个子数组，递归深度达到n。

(3)在某些情况下，可能会导致不平衡的分区，从而影响递归的效率。

（三）3-wayPartition（三向切分）

3-wayPartition是针对包含大量重复元素的数组进行优化的分区策略。它将数组划分为三个部分：小于基准的元素、等于基准的元素、大于基准的元素。这样可以避免在Hoare或Lomuto分区法中对大量重复元素进行不必要的比较和交换，从而提升效率。

3-wayPartition法的详细步骤（StepbyStep）：

1.选择基准元素（Pivot）：

通常选择数组的第一个元素作为基准。即`pivot=arr[left]`。

2.初始化指针：

初始化三个指针：

`lt`(LessThan)：指向小于基准的元素的最后一个位置，初始值为`left-1`。

`gt`(GreaterThan)：指向大于基准的元素的第一个位置，初始值为`right+1`。

`i`(Current)：当前正在检查的元素的位置，初始值为`left`。

3.遍历与分类：

当`i<gt`时，循环处理当前元素`arr[i]`：

情况1：`arr[i]<pivot`

表示`arr[i]`应该移动到基准左侧的小于部分。

将`lt`加1，`i`加1，并交换`arr[lt]`和`arr[i]`。交换后，`arr[i]`被移动到了小于部分的正确位置，`i`继续向后检查。

即：`lt++`；`i++`；`swap(arr[lt],arr[i])`

情况2：`arr[i]==pivot`

表示`arr[i]`等于基准，属于等于部分。

只需要将`i`加1，让`i`继续向后检查下一个元素。

即：`i++`

情况3：`arr[i]>pivot`

表示`arr[i]`应该移动到基准右侧的大于部分。

将`gt`减1，并与`arr[gt]`交换。交换后，`arr[i]`被移动到了大于部分的正确位置。此时`i`保持不变，因为交换过来的`arr[gt]`是一个新的元素，需要再次检查。

即：`gt--`；`swap(arr[i],arr[gt])`

4.结束遍历：

循环结束后，数组已经被划分为三个部分：

`arr[left...lt]`：所有元素都小于基准。

`arr[lt+1...gt-1]`：所有元素都等于基准。

`arr[gt...right]`：所有元素都大于基准。

5.（可选）处理等于基准的部分：

在某些实现中，可以选择递归地对小于基准和大于基准的子数组进行排序。

也可以选择不立即递归排序等于基准的部分，而是将等于基准的部分的元素收集起来，在排序完成后统一处理（例如，将这部分元素插入到最终排序数组中合适的位置）。这取决于具体的应用场景。

3-wayPartition法的优缺点：

优点：

(1)在包含大量重复元素的数组上效率极高，时间复杂度可以接近O(n)，因为它将重复元素分离出来，减少了递归的深度和比较次数。

(2)对于重复元素分布均匀的情况也能提供很好的性能。

缺点：

(1)实现相对复杂，比Hoare和Lomuto分区法更难理解和编写。

(2)需要使用三个指针，增加了代码的复杂性。

三、Partition策略的性能分析

Partition策略的选择和实现直接影响快速排序的整体性能。

（一）时间复杂度

平均情况：

对于Hoare分区法和Lomuto分区法，在平均情况下，每次Partition操作将数组大致分成大小相等的两部分（或差异不大），递归树的深度接近log(n)。每次Partition操作需要遍历整个数组（或大部分数组），时间复杂度为O(n)。因此，快速排序的平均时间复杂度为O(nlogn)。

对于3-wayPartition法，特别是当数组中存在大量重复元素时，其平均时间复杂度可以非常好，接近O(n)。

最坏情况：

最坏情况通常发生在每次Partition操作只得到一个元素大小的子数组（例如，当数组已经有序或倒序，且每次总是选择第一个或最后一个元素作为基准时）。

在这种情况下，Partition操作的时间复杂度为O(n)，而递归的深度达到n。因此，最坏情况时间复杂度为O(n²)。

3-wayPartition法在一定程度上可以缓解最坏情况的发生概率，但最坏情况时间复杂度仍然是O(n²)。

（二）空间复杂度

快速排序是原地排序算法，不需要额外的存储空间。

Partition操作本身通常只需要常数级的额外空间（用于存储基准元素和几个指针）。

但快速排序的递归调用需要栈空间来存储递归调用的上下文。在平均情况下，递归树的深度为log(n)，因此空间复杂度为O(logn)。

在最坏情况下（递归深度为n），空间复杂度为O(n)。

3-wayPartition法在实现中可能需要额外的变量，但其空间复杂度通常仍然是O(logn)（不计输入数组本身）。

（三）实际应用建议

选择哪种Partition策略取决于具体