package sort;
/**
* 三å‘切分快速排åº
* 对于有大é‡é‡å¤å…ƒç´ 的数组，å¯ä»¥å°†æ•°ç»„切分为三部分，分别对应å°äºŽã€ç‰äºŽå’Œå¤§äºŽåˆ‡åˆ†å…ƒç´ 。
*
* 三å‘切分快速排åºå¯¹äºŽåªæœ‰è‹¥å¹²ä¸åŒä¸»é”®çš„éšæœºæ•°ç»„å¯ä»¥åœ¨çº¿æ€§æ—¶é—´å†…完æˆæŽ’åºã€‚
*
* @author 刘壮飞
* https://github.com/zfman.
* https://blog.csdn.net/lzhuangfei.
*/
public class ThreeWayQuickSort> extends QuickSort {
@Override
public void sort(T[] nums, int l, int h) {
if(l>=h) return;
int lt=l,i=l+1,gt=h;
T v=nums[l];
System.out.println(v);
while (i<=gt){
int compare=nums[i].compareTo(v);
if(compare<0){
swap(nums,lt++,i++);
}else if(compare>0){
swap(nums,i,gt--);
}else {
i++;
}
}
sort(nums,l,lt-1);
sort(nums,gt+1,h);
}
public static void main(String[] args){
Integer[] arr={
5,1,8,1,3,3,3,3,5,5,8,8,8
};
ArrayUtils.printArray(arr);
Sort sort=new ThreeWayQuickSort<>();
sort.sort(arr);
ArrayUtils.printArray(arr);
}
}