Java--快速排序优化：聚集元素法

找基准、第一次快速排序； //找基准 public static int partion(int[] array,int low,int high){//一次快排 int tmp=array[low]; while(low < high){ //从后找 while(low < high && array[high] >= tmp){ --high; } if(low >= high){ break; }else{ array[low] = array[high]; } //从前找 while(low < high && array[low] <= tmp){ ++low; } if(low >= high){ break; }else{ array[high] =array[low]; } } array[low] = tmp; return low; } 将相同元素聚集在一起； public static void Quick(int[] array,int start,int end){ int par = partion(array,start,end); int[] brray = focusNum(array,start,end,par);//相同元素 int left = brray[0]; int right = brray[1]; if(par > start+1){ Quick(array,start,left); } if(par < end-1){ Quick(array,right,end); } } public static int[] focusNum(int[] array,int start,int end,int par){ int tmp = 0; //查找范围 int left=par-1; int right=par+1; //交换的指引变量 int parLeft=par-1; int parRight=par+1; //左边找 for(int i = left;i >= start;i--){ if(array[i] == array[par]){//遍历过程中，有与par相同的元素时 if(i != parLeft){//若i 和parLeft相同，将两下标所对应的元素交换 tmp = array[i]; array[i] = array[parLeft]; array[parLeft] = tmp; parLeft--; }else{ parLeft--; } } } //右边找 for(int j = right;j <= end;j++){//遍历过程中，有与par相同的元素时 if(array[j] == array[par]){//若i 和parRight相同，将两下标所对应的元素交换 if(j != parRight){ tmp = array[j]; array[j] = array[parRight]; array[parRight] = tmp; parRight++; }else{ parRight++; } } } int[] focus={parLeft,parRight}; return focus; } 基准左右进行递归排序； public static void Quick(int[] array,int start,int end){ int par = partion(array,start,end); int[] brray = focusNum(array,start,end,par);//相同元素聚集在一起后，新的left和right int left = brray[0]; int right = brray[1]; if(par > start+1){ Quick(array,start,left); } if(par < end-1){ Quick(array,right,end); } } 调用方法； public static void QuickSort(int[] array) { Quick(array,0,array.length-1); } 测试。 public static void main(String[] args) { // TODO Auto-generated method stub int[] array = {20,20,20,56,25,32,87,45,12,69,54,20,98,51,25,56,25,56}; QuickSort(array); System.out.println(Arrays.toString(array)); }

输出结果：