1     public static void main(String[] args) 2     {     3         Scanner input = new Scanner(System.in); 4         int n = input.nextInt(); 5         int[] a = new int[n]; 6          7         for(int i = 0; i < a.length; i++) 8             a[i] = (int)(Math.random() * 100); 9         10         System.out.println("Before sort:");11         //System.out.println(Arrays.toString(a));12         long start = System.currentTimeMillis();13         divide(a, 0, a.length - 1);14         long end = System.currentTimeMillis();15         //10000000个测试数据用时约为550ms  相对于归并排序有较大提升16         System.out.println("After sort: ");17         //System.out.println(Arrays.toString(a));18         System.out.println(end - start);19     }20     21     public static void divide(int[] a, int left, int right)22     {23         if(left >= right)   //大于号防止数组为空24             return;25         26         int value = QuickSort(a, left, right);27         //先处理右半边28         divide(a, value + 1, right);   29         //再处理左半边30         divide(a, left, value - 1);   //分割时不能将value作为边界 否则排序数字相同的数组会导致无限递归31     }32     33     public static int QuickSort(int[] a, int left, int right)34     {35         int i = left, j = right + 1;36         int key = a[left];37         38         while(true)39         {    40             while(a[--j] > key)41                 if(j == left)   //该判断其实是冗余的 可以去掉42                     break;43             while(a[++i] < key)44                 if(i == right) 45                     break;46             if(i >= j)   //不判断相等的情况会导致数组下标越界(传入两个相同的元素) 47                 break;48             int temp = a[j];49             a[j] = a[i];50             a[i] = temp;51         }52         53         int t = a[left];54         a[left] = a[j];55         a[j] = t;56         return j;57     }