1 算法原理
将数组划分为三部分，大于v，小于v和等于v，设置三个指针，优点就是无需对重复元素进行重复操作，性能有所优化
2 时间复杂度
O(logn*n)
3 实现
/**
* 三路快排
*
* @author xld
*
*/
public class QuickSortThreeWay {
public static void sort(
int[] arr) {
int n = arr.length;
sort(arr,
0, n -
1);
}
public static void sort(
int[] arr,
int l,
int r) {
if(r<l)
return;
int v = arr[l];
int lt = l;
int gt = r+
1;
int i = l +
1;
while (i < gt) {
if (arr[i] < v) {
swap(arr, i, lt +
1);
lt++;
i++;
}
else if (arr[i] > v) {
swap(arr, i, gt -
1);
gt--;
}
else {
i++;
}
}
swap(arr, l, lt);
sort(arr, l, (lt-
1));
sort(arr, gt, r);
}
private static void swap(
int[] arr,
int i,
int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
/**
* 测试
*
* @param args
*/
public static void main(String[] args) {
int[] arr = {
10,
9,
8,
7,
6,
5,
4,
3,
2,
1 };
QuickSortThreeWay.sort(arr);
for (
int i =
0; i < arr.length; i++) {
System.out.print(arr[i]);
System.out.print(
' ');
}
System.out.println();
}
}
