算法总结之数组的partition调整三个值的升序

给定一个数组arr, 其中只可能有 0，1，2三个值，请实现arr排序

另一种问法：有一个数组，只有红蓝黄球，请事先红球全放在数组的左边，蓝球放中间，黄球放右边

另一种问法：有一个数组，再给定一个值K, 请实现比k小的数都放在数组的左边，等于k的放中间，大于k的放右边

思路：

生成变量left arr[0....left] 上面都是0 left是这个区域的最右位置初始时 left =-1

生成变量index 利用这个变量从左到右的遍历， arr[left+1...index]上面都是1 初始index=0

生成变量right， arr[right....N-1]上面都是2，right是这个区域的当前最左位置，初始时时 right为N

然后进行遍历，看看当前元素是 0 1 2 并且放到相应的位置去

这个划分区域的思想很棒，很给力！非常值得学习与借鉴！

package TT;

public class Test82 {

	public void sort (int[] arr){

		if(arr==null ||| arr.length<2){

			return;

		}

		int left = -1;

		int index=0;

		int right =arr.length-1;

		while(index<right){

			if(arr[index]==0){

				swap(arr,++left,index++);

			}else if(arr[index]==2){

				swap(arr,index,--right)

			}else {

				index++;

			}

		}

	}

}

巴特西

算法总结之数组的partition调整三个值的升序

最新文章

热门文章

巴特西

算法总结之 数组的partition调整 三个值的升序

最新文章

热门文章

算法总结之数组的partition调整三个值的升序