【算法-Java实现】将数组按某值划分成左边小，中间相等，右边大的形式

一.问题描述：

1.输入：一个无序整型数组arr，其中arr中元素不唯一。

如：int[] arr = { 3, 4, 6, 9, 5, 5, 8, 8, 2, 1, 7, 7, 0 };

2.输出：将数组arr按某值划分成左边小，中间相等，右边大的形式，并输出。

二.问题解答：

此问题的另外一种问法：荷兰国旗问题

有一个数组，只有红球，蓝球，黄球，请将红球放在数组左边，蓝球放在数组中间，黄球放在数组右边。

思路：

1.首先用一个基准num作为中间值，cur指针从下标0依次遍历数组至下标arr.length-1。

2.less指针一开始指向-1，more指针指向arr.length。

3.cur指针依次移动，判断当前cur下标元素和num值之间的大小关系，进行元素交换。

具体实现见代码，结果如下：

三.算法分析：

1.时间复杂度为O(N)，相当于遍历数组。

2.额外空间复杂度为O(1),无需使用额外空间。

代码如下

import java.util.Arrays;
/*
 * 问题：将数组按某值划分成左边小，中间相等，右边大的形式
 * 
 */
public class ArraySort {
	//测试
	public static void main(String[] args) {
		int[] arr = { 3, 4, 6, 9, 5, 5, 8, 8, 2, 1, 7, 7, 0 };
		int[] newArr = partition(arr, 0, arr.length - 1, 5);
		System.out.println(Arrays.toString(newArr));
	}
    //算法实现
	public static int[] partition(int[] arr, int L, int R, int num) {
		int less = -1;
		int more = R + 1;
		int cur = L;
		while (cur < more) {
			if (arr[cur] > num) {
				swap(arr, --more, cur);
			} else if (arr[cur] < num) {
				swap(arr, ++less, cur++);
			} else {
				cur++;
			}
		}
		return arr;
	}
	//元素交换
	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}