# 在给定范围内对数组进行三向分区 > 原文： [https://www.geeksforgeeks.org/three-way-partitioning-of-an-array-around-a-given-range/](https://www.geeksforgeeks.org/three-way-partitioning-of-an-array-around-a-given-range/) 给定一个数组和一个范围[ **lowVal** ， **highVal** ]，围绕该范围划分数组，以便将数组分为三部分。 1）所有小于 **lowVal** 的元素都在前。 2）接下来是 **lowVal** 至 **highVVal** 范围内的所有元素。 3）最后所有大于 **highVVal** 的元素。 三组中的各个元素可以按任何顺序出现。 **示例**： ``` Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32} lowVal = 14, highVal = 20 Output: arr[] = {1, 5, 4, 2, 1, 3, 14, 20, 20, 98, 87, 32, 54} Input: arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32} lowVal = 20, highVal = 20 Output: arr[] = {1, 14, 5, 4, 2, 1, 3, 20, 20, 98, 87, 32, 54} ```  **简单解决方案**是对数组进行排序。 此解决方案做了很多额外的重新安排，并且需要`O(n Log n)`时间。 **有效解决方案**基于[荷兰国旗的 QuickSort](https://www.geeksforgeeks.org/3-way-quicksort-dutch-national-flag/)。 我们从左遍历给定的数组元素。 我们跟踪两个指针，第一个（在下面的代码中称为`start`）从头开始存储较小元素（小于范围）的下一个位置； 第二个（在下面的代码中称为`end`）存储从`end`开始更大元素的下一个位置。 ## C/C++ ``` // C++ program to implement three way partitioning // around a given range. #include<iostream> using namespace std; // Partitions arr[0..n-1] around [lowVal..highVal] void threeWayPartition(int arr[], int n,                 int lowVal, int highVal) {     // Initialize ext available positions for     // smaller (than range) and greater lements     int start = 0, end = n-1;     // Traverse elements from left     for (int i=0; i<=end;)     {         // If current element is smaller than         // range, put it on next available smaller         // position.         if (arr[i] < lowVal)             swap(arr[i++], arr[start++]);         // If current element is greater than         // range, put it on next available greater         // position.         else if (arr[i] > highVal)             swap(arr[i], arr[end--]);         else             i++;     } } // Driver code int main() {     int arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87,                 98, 3, 1, 32};     int n = sizeof(arr)/sizeof(arr[0]);     threeWayPartition(arr, n, 10, 20);     cout << "Modified array \n";     for (int i=0; i<n; i++)         cout << arr[i] << " "; } ```