荷兰国旗问题

问题描述：给定一个k，把比k小的放数组的左边，=k的放中间，>k的放右边。

题解：

        就是快排中的partition步骤。

        用less指针表示比k小的最后一个元素的位置，more表示比k大的第一个元素的位置。

        用cur指针指向当前位置，如果当前元素小于k，直接把它和less+1位置交换，并且less++。由于less以及less以前的必然小于k，所以less+1必然大于等于k（如果<k,只能是cur就在less+1的位置），所以直接交换，cur也右移。

        如果>k，那么就和more-1位置元素交换，并且more--。由于more-1位置不知道数是多大，所以cur不能动，需要再次比较。

package sort;

import java.util.*;

public class NetherlandFlag {
	public static int[] partition(int[] arr,int L,int R,int num) {
		int cur = L;
		int less = L-1;
		int more = R+1;
		while(cur<more) { //这里不是小于等于
			if(arr[cur]<num) {
				swap(arr,cur++,++less);
			} else if(arr[cur]==num) {
				cur++;
			} else if(arr[cur]>num){
				swap(arr,cur,--more); //这里就是cur，不是cur++，因为交换回来的数不知道是多大
			}
		}
		return new int[] {less+1,more-1};
	}
	
	public static void swap(int[] arr,int i,int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int n,k;
		n = in.nextInt();
		k = in.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++)
			a[i] = in.nextInt();
		int[] b=partition(a,0,n-1,k);
		for(int i=0;i<2;i++)
			System.out.println(b[i]);
	}
}

转载自原文链接, 如需删除请联系管理员。

原文链接：荷兰国旗问题，转载请注明来源！