# 在給定範圍內對數組進行三向分區

## 問題陳述

1. 第一個分區的元素將小於lowValue，
2. 元素位於給定範圍內的下一個分區將在此分區中，並且
3. 大於highValue的數字將是數組的第三個分區。

## 例

```arr[]={2,5,87,56,12,4,9,23,76,1,45}

lowValue = 15

highValue = 30```
`2 5 1 12 4 9 23 76 56 45 87`

lowValue為15，因此左側的數字將小於lowValue。

highValue是30，所有大於highValue的數字都將在右側。

## 算法

```1. Set the startingValue to 0 and endingValue to n-1.
2. Traverse the array.
1. Check if the current array element is less than the value of lowValue if true then swap the arr[i] and arr[startingValue] and increase both startingValues and i by 1.
2. Else check if the current array is greater than the highValue, swap the arr[i] and arr[endingValue] and increase the value of i and decrease the value of endingValue by 1.
3. Else increase the value of i by 1.
3. Print the array.```

## 推薦碼

### C ++代碼解決給定範圍內數組的三向分區

```#include<iostream>
using namespace std;

void getPartition(int arr[], int n, int lowValue, int highValue)
{
int startingValue = 0, endingValue = n-1;

for (int i=0; i<= endingValue;)
{
if (arr[i] < lowValue)
swap(arr[i++], arr[startingValue++]);

else if (arr[i] > highValue)
swap(arr[i], arr[endingValue--]);

else
i++;
}
}

int main()
{
int arr[] = {2,5,87,56,12,4,9,23,76,1,45};
int n = sizeof(arr)/sizeof(arr[0]);

getPartition(arr, n, 15, 30);

for (int i=0; i<n; i++)
cout << arr[i] << " ";
}
```
`2 5 1 12 4 9 23 76 56 45 87`

### Java代碼來解決給定範圍內的數組的三種方式分區

```class ThreeWayPartition
{
public static void getPartition(int[] arr, int lowValue, int highValue)
{
int n = arr.length;

int startingValue = 0, endingValue = n-1;

for(int i = 0; i <= endingValue;)
{
if(arr[i] < lowValue)
{

int temp = arr[startingValue];
arr[startingValue] = arr[i];
arr[i] = temp;
startingValue++;
i++;
}
else if(arr[i] > highValue)
{

int temp = arr[endingValue];
arr[endingValue] = arr[i];
arr[i] = temp;
endingValue --;
}
else
i++;
}
}
public static void main (String[] args)
{
int arr[] = {2,5,87,56,12,4,9,23,76,1,45};

getPartition(arr, 15, 30 );

for (int i=0; i < arr.length; i++)
{
System.out.print(arr[i] + " ");

}
}
}
```
`2 5 1 12 4 9 23 76 56 45 87`

## 複雜度分析

### 時間複雜度

O（N） 哪裡 “ n” 是數組中元素的數量。 由於我們遍歷了數組元素，因此時間複雜度是線性的。

### 空間複雜度

O（1） 因為不需要額外的空間。 該算法本身是就地算法，並且正在更新初始給定數組。 因此，算法的空間複雜度是恆定的，而程序是線性的。