Lomuto 分区算法：深入解析与实战指南

在这篇文章中，我们将深入探讨排序算法中最核心但也最容易被忽视的基础组件之一——Lomuto 分区算法。如果你曾研究过快速排序的内部机制，那你一定见过它的影子。虽然算法本身看起来很短，但其背后的逻辑却非常精妙。我们将从零开始，一步步拆解它是如何工作的，为什么要这样设计，以及在实际工程开发中我们该如何应用它。准备好了吗？让我们开始这段探索之旅吧。

什么是数组分区？

首先，我们需要明确“分区”在算法中的确切含义。给定一个包含多个数字的数组，我们的任务是重新排列这些数字，使得数组被划分为两部分：一部分满足某个条件（例如小于某个值），另一部分则不满足（例如大于或等于该值）。

为了做到这一点，我们通常会从数组中选择一个特定的元素作为标准，我们称之为基准。在 Lomuto 算法中，我们约定俗成地选择数组的最后一个元素作为这个基准。

#### 核心目标

分区操作必须满足以下两个硬性条件：

• 左侧区域：所有严格小于基准的元素都必须排在基准的前面。
• 右侧区域：所有大于或等于基准的元素都必须排在基准的后面。

值得注意的是：对于一个给定的数组，合法的分区结果可能不止一种。只要元素的相对顺序满足上述大小关系，无论它们的具体位置如何，都是正确的。这一点在我们理解算法稳定性时非常重要。

#### 举个栗子

让我们通过一个直观的例子来看看我们的目标是什么。

场景 1：

假设输入数组是 arr[] = [5, 13, 6, 9, 12, 11, 8]。

• 最后一个元素 8 是我们的基准。
• 小于 INLINECODEb115d526 的元素是 INLINECODE3f12d2c4。
• 大于 INLINECODEe47472b5 的元素是 INLINECODE9c7dfe99。

执行分区后，一种可能的输出结果是：

> [5, 6, **8**, 13, 9, 12, 11]

此时，INLINECODE76159a8f 位于第 2 个索引（从 0 开始）。它左边的 INLINECODE5084b425 和 6 都比它小，右边的所有数都比它大。任务完成！

场景 2：

再看一个包含重复元素的例子：arr[] = [4, 10, 9, 16, 19, 9]。

• 基准是最后一个元素 9。
• 小于 INLINECODE14365873 的元素：INLINECODE36341326。
• 大于或等于 INLINECODE63585731 的元素：INLINECODE9bdf8db8。

分区后的结果可能是：

> [4, **9, 9**, 10, 16, 19] (注意这里有两个 9，一个是基准，一个是原数组中的)

Lomuto 分区算法：核心逻辑解析

现在让我们进入正题。Lomuto 分区算法之所以经典，是因为它实现起来非常直观，而且代码极其简洁。它的核心思想是：维护一个“边界”，将小于基准的元素逐渐“收编”到左边。

#### 算法的执行步骤

我们可以把这个过程想象成是在整理一摞杂乱的扑克牌。你手里拿着最后一张牌作为基准，你需要把桌上所有比这张牌小的牌都挪到左边。具体步骤如下：

• 确立基准：我们选定数组的最右端元素 arr[high] 作为基准。
• 初始化指针：我们设置一个指针 INLINECODE9278a3f5，通常初始化为比数组起始索引小 1 的位置（即 INLINECODE2d5c028a 或 -1）。这个指针的作用非常关键，它始终指向当前已经处理好的、小于基准的区域的最后一个位置。你可以把它想象成“已处理区”的界碑。
• 遍历与交换：我们使用另一个指针 INLINECODE2c1ffb58 来遍历数组（从 INLINECODE46b0ebc6 到 INLINECODEada09467）。对于每一个元素 INLINECODEb28c2df5：

– 检查：如果 arr[j] 小于基准，说明这个元素属于左边。

– 扩展边界：我们将 INLINECODE7c5c22af 向右移动一位（INLINECODE6a60cffc），为新元素腾出位置。

– 交换：我们将 INLINECODEc91003c6 与 INLINECODE2a8b6a76 交换。这一步确保了所有小于基准的元素都紧凑地排列在数组的前部。

• 归位基准：当 INLINECODE033b32b7 遍历结束后，所有小于基准的元素都已经安全地待在了 INLINECODE03a1d570 的左侧。此时，我们只需将基准元素（此时还在 INLINECODE89c3a286）与 INLINECODE9a838a13 交换。基准此刻就坐在了它正确的位置上，它的左边全是小数，右边全是大于等于它的数。

代码实战与深入讲解

光说不练假把式。让我们用代码来把上面的逻辑实现出来。为了照顾不同开发者的习惯，我将提供 C++、C 和 Java 三种语言的实现，并加上详细的注释。

#### 1. C++ 实现

在 C++ 中，我们可以利用 STL 的 swap 函数让代码更简洁。

// C++ program to partition the array
// using Lomuto Partition Algorithm
#include 
#include 
using namespace std;

// 根据基准对数组进行分区的函数
void partition(vector &arr) {
    int n = arr.size();
    // 1. 选择最后一个元素作为基准
    int pivot = arr[n - 1];
    
    // 2. i 作为“较小区域”的边界指针
    // 初始化为 -1，表示初始时较小区域为空
    int i = -1;
    
    // 3. 使用 j 遍历数组中的元素（除最后一个基准外）
    for (int j = 0; j < n - 1; j++) {
        
        // 如果当前元素小于基准
        if (arr[j] < pivot) {
            i++; // 扩展边界
            swap(arr[i], arr[j]); // 将小元素移到边界左侧
        }
    }
    
    // 4. 遍历结束后，将基准放到正确位置（i + 1）
    // 此时 i 指向最后一个小于基准的元素
    swap(arr[i + 1], arr[n - 1]);
}

int main() {
    vector arr = {5, 13, 6, 9, 12, 11, 8};
    
    cout << "原始数组: ";
    for (int x : arr) cout << x << " ";
    cout << endl;
    
    partition(arr);
    
    cout << "分区后数组: ";
    for (int i = 0; i < arr.size(); i++) 
        cout << arr[i] << " "; 
        
    return 0;
}

代码解析：

注意看 INLINECODE392e7e16 循环中的条件 INLINECODE3ff68d67。我们不需要遍历最后一个元素，因为那就是基准本身，我们最后会专门处理它。

#### 2. C 语言实现

对于 C 语言开发者，我们需要手动实现交换逻辑，这能让你更清楚地看到内存中的数据流动。

// C program to partition the array
// using Lomuto Partition Algorithm
#include 

// 交换两个整数的辅助函数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数
void partition(int arr[], int n) {
    int pivot = arr[n - 1]; // 基准
    
    // i 是较小元素的边界索引
    int i = -1; 
    
    for (int j = 0; j < n - 1; j++) {
        // 发现小于基准的元素
        if (arr[j] < pivot) {
            i++; // 边界右移
            swap(&arr[i], &arr[j]); // 交换数据
        }
    }
    
    // 将基准元素放置到正确位置
    // i + 1 就是基准应该去的索引
    swap(&arr[i + 1], &arr[n - 1]);
}

int main() {
    int arr[] = {10, 80, 30, 90, 40, 50, 70};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    partition(arr, n);
    
    printf("分区结果: ");
    for (int i = 0; i < n; i++) 
        printf("%d ", arr[i]); 
    return 0;
}

#### 3. Java 实现

在 Java 中，我们通常在类中实现静态方法。注意 Java 的数组引用传递特性。

// Java program to partition the array
// using Lomuto Partition Algorithm
import java.util.Arrays;

class PartitionDemo {
  
    // 分区函数
    static void partition(int[] arr) {
        int n = arr.length;
        int pivot = arr[n - 1];
        
        // i 指向小于基准的最后一个元素
        int i = -1; 
        
        for (int j = 0; j < n - 1; j++) {
            // 如果当前元素小于基准
            if (arr[j] < pivot) {
                i++;
                
                // 交换 arr[i] 和 arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // 最后交换基准元素
        int temp = arr[i + 1];
        arr[i + 1] = arr[n - 1];
        arr[n - 1] = temp;
    }
    
    public static void main(String[] args) {
        int[] arr = {5, 13, 6, 9, 12, 11, 8};
        partition(arr);
        
        System.out.println("分区结果: " + Arrays.toString(arr));
    }
}

深入理解：进阶视角与优化

作为一名追求卓越的开发者，仅仅知道“怎么写”是不够的，我们还需要知道“为什么这么写”以及“有没有更好的办法”。

#### 1. 为什么要将 i 初始化为 -1？

你可能会疑惑，为什么 INLINECODE2209a67a 要从 INLINECODEed042791 开始，而不是从 0 开始？这是为了处理边界情况最优雅的方式。

• 当我们找到第一个小于基准的元素时，INLINECODEe191f754 变为 INLINECODE277b1622，然后我们将 INLINECODE39242ff6 与 INLINECODE4dfc5ce4（它自己）交换。这是完全安全的。
• 如果数组中没有任何元素小于基准（例如数组已经是升序排列），INLINECODEeb6a805e 将保持 INLINECODEdcc9bd47。循环结束后，我们执行 INLINECODEb1e6740b，即 INLINECODE89363805。这完美地将基准移到了数组的最前面，这也是唯一正确的位置。
• 如果我们从 i = 0 开始，逻辑会变得非常复杂，因为你无法区分“还没有找到小元素”和“第一个元素就是小元素”这两种情况。

#### 2. 返回基准的索引

在标准库实现（如 C++ 的 INLINECODE697242c8 或快速排序）中，分区函数通常会返回基准最终所在的索引（即上面的 INLINECODE0c43d30d）。这非常重要，因为快速排序随后会递归地对基准左侧（INLINECODEfd453e31 到 INLINECODE2c093ffb）和右侧（INLINECODEa83876f0 到 INLINECODEfc423b9f）的子数组进行排序。如果你打算手写快速排序，记得修改上面的代码，让它 return i + 1。

#### 3. Lomuto vs. Hoare

Lomuto 并不是唯一的分区算法。另一种著名的是 Hoare 分区方案（使用两个指针分别从两端向中间扫描）。

• Lomuto 的优势：逻辑简单，代码容易记忆和理解。即使有重复元素，也能处理得当。
• Lomuto 的劣势：它所做的交换次数通常比 Hoare 方案多，特别是在数组已经有序或接近有序时，这会降低性能。此外，它将所有等于基准的元素都放在了右边，这可能导致在大量重复元素的数组上分区不平衡。

#### 4. 实战建议与性能陷阱

• 最坏情况：如果数组本身就是升序排列的，Lomuto 算法每次选择的基准都是最大的元素。这意味着第一次分区将不做任何交换（i 保持在 -1），然后将基准换到第一个位置。这将导致分区极度不平衡（一边是 0 个元素，另一边是 n-1 个元素），时间复杂度会退化到 $O(n^2)$。解决方案：尽量随机选择基准，而不是总选最后一个，或者使用“三数取中法”来选择基准。
• 重复元素：Lomuto 算法处理重复元素的能力是稳定的，但如果你的数组中有海量重复元素，Dijkstra 的三路分区（将数组分为小于、等于、大于三部分）会是更好的选择。

总结

在这篇文章中，我们不仅学习了 Lomuto 分区算法的代码实现，更重要的是，我们理解了它通过维护“边界”来逐步有序化的思维方式。它是构建更复杂算法（如快速排序）的基石。虽然它在某些极端情况下性能不是最优的，但其逻辑的清晰度使其成为学习和理解算法原理的最佳起点。

希望这篇文章能帮助你彻底搞懂 Lomuto 分区。下次当你遇到需要将数组按特定规则重组的问题时，别忘了这个简单却强大的工具。