# 在給定范圍內對數組進行三向分區 > 原文： [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] << " "; } ```