C++ 中围绕一个元素的三向分区

2025年5月14日 | 阅读12分钟

在数组操作和排序问题中，当涉及到枢轴元素时，所使用的经典算法技巧是三路分区。其主要目标是根据指定的枢轴值重新排列数组，将其划分为三个不同的部分。

小于枢轴的元素：数组元素位于数组的开头。
等于枢轴的元素：这些元素组位于中间。
大于枢轴的元素：它们位于数组的末尾附近。

当我们要查找带有重复值的数组时，此方法通过额外的迭代可以更快地工作。我们在许多算法中使用它，例如快速排序或荷兰国旗问题，其中需要通过与枢轴或特定标准进行比较或根据枢轴或特定标准进行排序和重排。

用例

三路分区解决了传统双路分区技术的一个常见限制，即双路分区仅将数组分为两部分：小于枢轴的元素和大于枢轴的元素。对于包含大量等于枢轴的元素的数组进行双路分区可能需要不必要的比较和交换，这使得整个分区效率低下。三路分区显式处理枢轴元素的方法可最大程度地减少这些冗余操作并提高性能。

该技术在以下问题中特别有益：

数组包含许多重复元素，从性能角度来看，这些元素只处理一次。
例如，我们要根据三个类别对元素进行排序：对 0、1、2 等的数组进行排序。
要解决此问题，需要线性时间复杂度 (O(n)) 和最小空间复杂度 (O(1) 附加空间)。

关键概念

三路分区算法使用 low、mid 和 high 三个指针，在单次遍历中有效地分割数组。该技术根据枢轴元素将数组分为三个段：小于枢轴、等于枢轴或大于枢轴。Low 跟踪小于枢轴区域的边界，Mid 扫描正在测试的当前元素，High 标记大于枢轴的边界。

该算法是单次遍历，运行时间为 O(n)，空间复杂度为 O(1)，非常适合原地重排。它解决了荷兰国旗问题、快速排序的优化版本，并且在数组包含重复元素时表现出色。总而言之，三路分区是数组操作的强大工具，为许多应用中的系统性、直接排序提供了非常通用的手段。

方法 1：暴力方法

暴力方法是三路分区的一种显而易见的方法，即多次遍历数组以根据枢轴对元素进行分类。其附加的空间要求和易于实现的特性使得此方法易于实现但效率不高。

最后一步是将三个段连接到一个新数组中。暴力方法确保正确分区，但存在需要额外内存（O(n) 空间复杂度）和需要多次遍历（O(n) 时间复杂度）的巨大缺点。

示例

让我们以一个示例来说明使用暴力方法在 C++ 中围绕元素进行三路分区。

 
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
//Function to print the array
void printArray(const vector<int>& arr, const string& message) {
    cout << message << ": ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}
//Function to get user input for the array
vector<int> getUserInput() {
    vector<int> arr;
    string input;
    cout << "Enter the elements of the array (space-separated integers): ";
    getline(cin, input);
    stringstream ss(input);
    int num;
    // Read integers from the input string
    while (ss >> num) {
        arr.push_back(num);
    }
    return arr;
}
//Function to get pivot input from the user
int getPivot() {
    int pivot;
    cout << "Enter the pivot element: ";
    cin >> pivot;
    return pivot;
}
// Brute force function to partition the array
vector<int> threeWayPartitionBruteForce(const vector<int>& arr, int pivot) {
    vector<int> lessThanPivot;
    vector<int> equalToPivot;
    vector<int> greaterThanPivot;
    // First pass: Collect elements less than the pivot
    for (int num : arr) {
        if (num < pivot) {
            lessThanPivot.push_back(num);
        }
    }
    // Second pass: Collect elements equal to the pivot
    for (int num : arr) {
        if (num == pivot) {
            equalToPivot.push_back(num);
        }
    }
    // Third pass: Collect elements greater than the pivot
    for (int num : arr) {
        if (num > pivot) {
            greaterThanPivot.push_back(num);
        }
    }
    // Print intermediate results
    printArray(lessThanPivot, "Elements less than pivot");
    printArray(equalToPivot, "Elements equal to pivot");
    printArray(greaterThanPivot, "Elements greater than pivot");
    // Concatenate all three parts
    vector<int> result;
    // Add less than pivot elements
    for (int num : lessThanPivot) {
        result.push_back(num);
    }
    // Add equal to pivot elements
    for (int num : equalToPivot) {
        result.push_back(num);
    }
    // Add greater than pivot elements
    for (int num : greaterThanPivot) {
        result.push_back(num);
    }
    return result;
}
// Function to validate the input array
bool validateArray(const vector<int>& arr) {
    if (arr.empty()) {
        cout << "Error: The array is empty. Please provide valid input." << endl;
        return false;
    }
    return true;
}
//Function to validate the pivot value
bool validatePivot(int pivot, const vector<int>& arr) {
    bool found = false;
    for (int num : arr) {
        if (num == pivot) {
            found = true;
            break;
        }
    }
    if (!found) {
        cout << "Warning: The pivot element is not present in the array." << endl;
    }
    return true;
}
// Main Function
int main() {
    cout << "Three-Way Partitioning (Brute Force Approach)" << endl;
    // Get user input for the array
    vector<int> arr = getUserInput();
    // Validate the input array
    if (!validateArray(arr)) {
        return 1; // Exit if the array is invalid
    }
    // Get the pivot value from the user
    int pivot = getPivot();
    // Validate the pivot value
    validatePivot(pivot, arr);
    // Print the original array
    printArray(arr, "Original array");
    // Perform three-way partitioning using brute force approach
    vector<int> partitionedArray = threeWayPartitionBruteForce(arr, pivot);
    // Print the partitioned array
    printArray(partitionedArray, "Partitioned array");
    cout << "Partitioning Complete " << endl;
    return 0;
}   

输出

 
Three-Way Partitioning (Brute Force Approach)
Enter the elements of the array (space-separated integers): 2 3 7 45 6 23 43 68 94 57
Enter the pivot element: 43
Original array: 2 3 7 45 6 23 43 68 94 57 
Elements less than pivot: 2 3 7 6 23 
Elements equal to pivot: 43 
Elements greater than pivot: 45 68 94 57 
Partitioned array: 2 3 7 6 23 43 45 68 94 57 
Partitioning Complete

说明

输入处理

读取数组元素的函数调用由 getUserInput() 函数完成。getline() 函数将整个输入作为字符串获取，然后 stringstream 将字符串解析为单独的整数。这些整数被添加到用于存储数组元素的 vector 数组中。
第一部分，getPivot() 函数要求用户输入一个枢轴元素，该元素是分区将围绕其进行的参考值。

验证

在继续之前，validateArray() 函数会检查数组是否为空。如果数组为空，程序会发出错误消息并停止（提前）整个程序，因为它试图处理无效输入。
validatePivot() 函数确保枢轴元素也存在于数组中。如果找不到，它会发出警告并继续运行，从而在处理枢轴不存在的边缘情况时具有灵活性。

分区逻辑

算法的主要部分是 threeWayPartitionBruteForce() 函数。它通过遍历数组三次来执行实际分区：

第一次遍历：枢轴是它收集所有小于枢轴的元素到其中的向量。
第二次遍历：在第二次遍历中，各部分将所有等于枢轴的元素收集到 equalToPivot 中。
第三次遍历：所有大于枢轴的元素构成 greaterThanPivot 函数。
在将元素收集到三个单独的向量中后，这些向量按顺序连接：LessThanPivot、EqualToPivot 和 GreaterThanPivot。枢轴元素围绕一个新数组，其元素已根据枢轴正确分区。
程序将打印出分区数组的三个段。它告诉我们数组是如何根据小于枢轴、等于枢轴和大于枢轴的元素重新排列的。
最后，打印出的分区数组就完成了。
其思想是重新排列数组，使所有小于枢轴的元素排在前面，所有等于枢轴的元素排在中间，所有大于枢轴的元素排在后面。上述过程涉及在三次遍历数组的过程中将元素收集到不同的组中。
暴力方法简单易懂且易于实现。但是，由于空间开销要求和在数组上进行多次线性扫描，上述方法对于大型数据集来说效率不高。

复杂度分析

时间复杂度

在分区过程中对数组执行的操作数量决定了时间复杂度。

第一次遍历：我们获取小于枢轴的元素。时间复杂度：O(n)，其中 n 是我们数组中的元素数量。
第二次遍历：再次，遍历数组右侧的元素以收集等于枢轴的元素。这也需要 O(n) 的时间。
第三次遍历：枢轴用于在数组中创建枢轴的外观，再次遍历数组以收集大于枢轴的元素。这同样需要 O(n) 的时间。

由于所有三次遍历都是独立的，因此总时间复杂度是这些单独遍历的总和。

总时间复杂度的复杂度将是 O(n) + O(n) + O(n) = O(3n) = O(n)。
这意味着暴力方法进行比较的次数（时间复杂度）为 O(n)，其中 n 是数组索引。大 O 忽略了常数因子 3。

空间复杂度

空间复杂度由存储分区段的附加空间决定。

我们创建了三个单独的向量来存储小于枢轴、等于枢轴和大于枢轴的元素。每个向量的最坏情况是存储多达 n 个元素，这使得其总空间与数组的大小成正比。
因此，它是 O(n) 的空间，因为创建了三个新向量，并且它们的空间消耗与输入的大小成比例。

方法 2：两次遍历原地分区

两次遍历原地交换分区是围绕枢轴进行三路分区的另一种方法。虽然在运行时比荷兰国旗算法慢，但这种方法在空间方面比暴力方法更快，因为它只使用恒定的额外空间。

该方法在两次遍历数组中进行：

第一次遍历：第一次遍历将所有小于枢轴的元素移到数组的左侧，所有大于枢轴的元素移到右侧。它是原地进行的，但它不处理等于枢轴的元素。
第二次遍历：第二次遍历将处理等于枢轴的元素，使它们位于较小和较大的元素之间。

步骤：

第一次遍历：根据枢轴对数组进行排序，然后将数组分为两部分：小于枢轴的元素和大于或等于枢轴的元素。

避免使用两个或更多指针来访问数组元素。将枢轴元素与数组元素进行比较，如果小于数组元素，则将其与数组左侧的元素交换。

第二次遍历：第一次遍历后，我们仍然可能在第一个数组中看到左侧大于枢轴的元素，在第二个数组中看到右侧小于枢轴的元素。在此遍历中，我们将所有等于的元素移到中间。
最终排列：两次遍历后，数组按左侧小于枢轴的元素、中间等于枢轴的元素以及右侧大于枢轴的元素进行分区。

示例

让我们以一个示例来说明使用两次遍历原地分区方法在 C++ 中围绕元素进行三路分区。

 
#include <iostream>
#include <vector>
#include <sstream>
#include <string>
using namespace std;
//Function to print the array
void printArray(const vector<int>& arr) {
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;
}
//Function to get input from the user and convert it into a vector of integers
vector<int> getUserInput() {
    string input;
    vector<int> arr;
    //Loop until we get a valid array input
    while (true) {
        cout << "Enter elements of the array (space-separated): ";
        getline(cin, input);
        // Check if the input is empty (only spaces or no input)
        if (input.empty()) {
            cout << "Error: The array cannot be empty. Please enter valid elements." << endl;
            continue; // Ask the user to try again
        }
        // Use stringstream to extract integers from the input string
        stringstream ss(input);
        int num;
        bool validInput = false;
        // Try extracting integers from the input string
        while (ss >> num) {
            arr.push_back(num);
            validInput = true;
        }
        // If no valid numbers were entered
        if (!validInput) {
            cout << "Error: No valid integers entered. Please enter valid elements." << endl;
            continue; // Ask the user to try again
        }
        // If valid integers were found, break out of the Loop
        break;
    }
    return arr;
}
//Function to validate the pivot (check if pivot exists in the array)
bool validatePivot(const vector<int>& arr, int pivot) {
    for (int elem : arr) {
        if (elem == pivot) {
            return true;
        }
    }
    return false;
}
//Function to get the pivot from the user
int getPivot(const vector<int>& arr) {
    int pivot;
    cout << "Enter the pivot element: ";
    cin >> pivot;
    // Check if a pivot exists in the array
    if (!validatePivot(arr, pivot)) {
        cout << "Warning: Pivot element is not in the array!" << endl;
    }
    return pivot;
}
//Function for two-pass partitioning around the pivot
void twoPassPartition(vector<int>& arr, int pivot) {
    int n = arr.size();
    // First pass: Move elements less than pivot to the left side and elements greater to the right
    int i = 0, j = 0, k = n - 1;
    while (j <= k) {
        if (arr[j] < pivot) {
            // Swap arr[i] and arr[j], increment i and j
            swap(arr[i], arr[j]);
            i++;
            j++;
        } else if (arr[j] == pivot) {
            // No action needed, just increment j
            j++;
        } else {
            // Swap arr[j] and arr[k], decrement k
            swap(arr[j], arr[k]);
            k--;
        }
    }
    // Second pass: Check if the pivot needs to be handled specifically (optional step)
    // This ensures that the partitioning is maintained with the pivot placed correctly
    // but it's not strictly needed if the array is partitioned correctly in the first pass.
}
// Main Function to drive the logic
int main() {
    // Step 1: Get array input from the user
    vector<int> arr = getUserInput();
    // Step 2: Ensure the array is not empty
    if (arr.empty()) {
        cout << "Error: The array cannot be empty." << endl;
        return 1; // Exit the program if the array is empty
    }
    // Step 3: Get a pivot from the user
    int pivot = getPivot(arr);
    // Step 4: Perform two-pass partitioning around the pivot
    twoPassPartition(arr, pivot);
    // Step 5: Output the partitioned array
    cout << "Partitioned array: ";
    printArray(arr);
    return 0;
}   

输出

 
Enter elements of the array (space-separated): 12 32 84 64 56 89 23 42
Enter the pivot element: 23
Partitioned array: 12 23 64 56 89 84 42 32

说明

输入处理

此处，系统提示用户输入一个空格分隔的整数列表。它会验证输入是否非空且为有效整数。如果输入的数据无效，它会提示用户输入正确的数据。

枢轴验证

最后，程序收集数组并要求用户输入枢轴元素。它首先检查枢轴是否在数组中。如果找不到枢轴，它会继续进行，并发出警告。

分区逻辑

数组分两次遍历进行分区。

第一次遍历元素会将小于枢轴的元素移到左侧，等于枢轴的元素移到中间，大于枢轴的元素移到右侧。
第二次遍历仅确保枢轴元素位于较小和较大值之间。

现在，向下分区以将枢轴元素置于小于和大于枢轴的元素之间，然后打印数组。

复杂度分析

时间复杂度

输入解析：此程序遍历输入，然后通过 stringstream 将其转换为整数。就数组中的元素数量而言，其时间复杂度为 O(n)。
枢轴验证：选择枢轴需要 O(1) 时间，但检查它是否存在于数组中需要 O(n) 时间。
分区：分区算法需要 O(n) 时间，因为它在两次遍历分区步骤中执行了两次顺序扫描。
因此，算法的总时间复杂度为 O(n)。

空间复杂度

事实上，该程序使用另一个数组来存储输入的整数，这需要 O(n) 的空间。
因此，除了这个之外，它不需要额外的空间，使其为 O(n)。

下一主题C++ 中的 Motzkin 数

C++ 中围绕一个元素的三向分区

用例

关键概念

方法 1：暴力方法

示例

说明

复杂度分析

方法 2：两次遍历原地分区

步骤：

示例

说明

复杂度分析

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 中围绕一个元素的三向分区

用例

关键概念

方法 1：暴力方法

示例

说明

复杂度分析

方法 2：两次遍历原地分区

步骤：

示例

说明

复杂度分析

相关帖子

C++ 中的 std::uninitialized_value_construct

C++ 最近点对

C++ 中使用硬编码元素初始化 Vector

C++ 中的 YAML 解析器

C++ 中的朗达数

C++ 中的内联汇编

C++ std::ranges::lazy_split 函数

C++ 中如何将 Enum 转换为 String

C++ 好友配对问题