快速排序
private static void quickSortThreeWay(int[] arr, int l, int r) {
if (l >= r) {
return;
}
swap(arr, l, (int) (Math.random() * (r - l + 1) + l)); //[l,r]随机参数一个基数放在第一个
int v = arr[l];
int lt = l;
int i = lt + 1;
int rt = r+1;
//循环完成值的交换
while (i < rt){
if(arr[i] < v){
swap(arr,i,lt+1);
lt++;
i++;
}else if(arr[i] > v){
swap(arr,i,rt-1);
rt--;
}else{
i++;
}
}
swap(arr,l,lt); //把基数的值放在左边的位置
quickSortThreeWay(arr,l,lt-1);//左边进行递归
quickSortThreeWay(arr,rt,r); //右边进行递归
}
//用于交换数组中的值
private static void swap(int[] arr, int i, int j) {
int temp;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}