Quick Sort(三向切分的快速排序)(Java)

1 1 //三向切分的快速排序
2 2 //这种切分方法对于数组中有大量重复元素的情况有比较大的性能提升
3 3 
4 4 public static void main(String[] args)
5 5 {
6 6     Scanner input = new Scanner(System.in);
7 7     int n = input.nextInt();
8 8     int[] a = new int[n];
9 9         
1010     for(int i = 0; i < a.length; i++)
1111     a[i] = (int)(Math.random() * 100);
1212     //System.out.println(Arrays.toString(a));
1313     long start = System.currentTimeMillis();
1414     qsort3way(a, 0, a.length - 1);
1515     long end = System.currentTimeMillis();
1616     //System.out.println(Arrays.toString(a));
1717     System.out.println(end - start);
1818     //10000000个测试数据用时350ms 相比普通快速排序提升约35%的性能
1919 }    
2020 
2121 public static void qsort3way(int[] a, int front, int rear)
2222 {
2323     if(front >= rear)
2424     return;
2525     
2626     int key_index = front, i = front + 1, j = rear;
2727     while(i <= j)
2828     {
2929     if(a[i] < a[key_index])   //key_index永远指向第一个key值
3030         swap(a, i++, key_index++);  
3131     else if(a[i] > a[key_index])
3232         swap(a, i, j--);
3333     else   //a[i] = a[key_index] 
3434         i++;
3535     }
3636 
3737     qsort3way(a, front, key_index - 1);
3838     qsort3way(a, j + 1, rear);
3939 }