算法排序-数组的partition调整

算法：数组的partition调整

1、给定一个有序数组arr, 调整arr使得这个数组左边部分没有重复元素且升序， 而右边部分不需保证是否有序和是否重复

例如，arr= [1,2,2,2,2,3,3,3,3,4,5,6,7,7,7,7,8,9]  ,调整后arr=[1,2,3,4,5,6,7,8,9,2,2,2,3,7,7,7,3,3]

public class ArrPatition { public static void main(String[] args){ //测试数组 int[] arr = {1,2,2,2,2,3,3,3,3,4,5,6,7,7,7,7,8,9}; int[] output = sortArray(arr); for(int i=0; i< output.length; i++){ System.out.print(arr[i] + ","); } } public static int[] sortArray(int[] arr){ if(arr == null || arr.length<2){ return arr; } int i=0; int j=1; //从左到右遍历数组，若arr[i] 与arr[j]不等，则数组互换位置i+1,j的值 while(j != arr.length){ if(arr[i] != arr[j]){ swap(arr, i+1, j); i++; } j++; } return arr; } //调换数组i,j位置 public static void swap(int[] arr, int i, int j){ int help = arr[i]; arr[i] = arr[j]; arr[j] = help; } }

2、给定无序且只含有1,2,3三个值的数组，实现数组排序

例如 arr=[3,3,1,2,3,3,2,1,2,3,2,1,2,2,2,3,2,1,1,1,1]      输出：arr=[1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3]

public class ArrPation1 { public static void main(String[] args){ int[] arr = {3,3,1,2,3,3,2,1,2,3,2,1,2,2,2,3,2,1,1,1,1}; int[] output = sortArray(arr); for(int i=0; i< output.length; i++){ System.out.print(arr[i] + ","); } } public static int[] sortArray(int[] arr) { if (arr == null || arr.length < 2) { return arr; } int left = 0; int index = 0; int right = arr.length-1; while (index < right) { if (arr[index] == 1) { //关键：left到index 区间的数一定不为1 swap(arr, left, index); left++; index++; } else if (arr[index] == 3) { swap(arr, index, right); right--; } else { index++; } } return arr; } //调换数组i,j位置 public static void swap(int[] arr, int i, int j){ int help = arr[i]; arr[i] = arr[j]; arr[j] = help; } }