时间： o（n） 空间 o(1): 没有recursion, 只有当前一层的call stack
sorting 如果是general sorting algo(1:不能对数组的性质加以限制） comparison based(2: sorting 只能通过两个数的比较来进行) ， 最好的时间复杂度o(nlogn)
/* * ［，i) value 1 * [i, j) value 2 * (k,) value 3 * the unknown places: [j, k] * */ public class RainbowSort { public static void main(String[] args){ int[] arr ={1,3,2,3,1,2} ; rainbowSort(arr); print(arr); } public static void rainbowSort(int[] arr){ if (arr == null || arr.length ==0 ) return; /* i * j * k * 1 1 2 2 2 2 3 3 * * */ int n = arr.length; int i = 0,j = 0, k = n-1; while (j<=k){ if(arr[j]==1){ swap(arr, i, j ); i++; j++; } else if(arr[j]==2){ j++; } else { swap(arr, j, k); k--; } } } public static void swap(int[] arr, int i, int j){ int temp = arr[i] ; arr[i] = arr[j]; arr[j] = temp; } public static void print(int[] arr){ for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } }