本题虽然考察的知识点很简单，但是想要程序在规定时间内跑完并且正确的话，就必须舍弃冒泡排序、选择排序和插入排序这三种较为低级的排序算法。
八大排序中还剩下很多可以用的算法，例如：希尔排序、快速排序、堆排序、基数排序、归并排序。
由于基数排序可能会导致内存超标（没测试过），而且写起来比较麻烦，所以我们选择听的比较多的，也是经常会遇到的面试题：快速排序。

快速排序

总得来说，快速排序的介绍非常简单。

  1. 首先，我们选择一个枢轴，一般为数组的第一个值或最后一个值

  2. 让所有左边的值都小于这个枢轴

  3. 让所有右边的值都大于这个枢轴

  4. 递归排左右两边

  5. 递归终止的条件为：left == right
    具体上代码：

    import java.util.*;

 public static void quickSort(int[] arr,int left,int right) {
     if ( left < right) {
         //只有当left < right的时候，排序才有意义
         int i = left;//辅助左指针
         int j = right;//辅助右
         int pivot = arr[i]; // 枢轴，将所有小于pivot的数放在它左边，所有大于pivot的数放在它右边
         while (i < j) {
             //当 i == j 时，循环才结束
             while (i < j && arr[j] >= pivot) {
                 //从后往前找，找到比pivot小的数，或者 i == j
                 j--;
             }
             if (i < j) {//如果退出上个循环后，i仍小于j，说明，找到了符合条件的数
                 arr[i] = arr[j];
                 //令i位置上的数等于j位置上的数
                 //由于交换数据太耗费时间，所以用这种方法代替
                 //最开始的i位置上的数已经通过pivot保存起来，此时为无效数据，可以用来保存j上的数据
                 //而赋值完成后，j上的数据为无效数据，在下一个循环中会被修改
             }
             while(i < j && arr[i] <= pivot) {
                 //此时再从前往后找，找到比pivot大的数，或者 i == j
                 i++;
             }
             if (i < j) {
                 //此时代表找到了这么个数，可以进行赋值
                 arr[j] = arr[i];
             }
         }
         //当循环退出后，i == j,此时i,j在同一位置，且为无效数据
         //修改该位置的数据为pivot，并利用递归完成其余两部分数据的排序
         arr[i] = pivot;
         quickSort(arr,left, i - 1);//从中间位置往左
         quickSort(arr,i + 1,right);//从中间位置往右
     }
 }

需要注意的是：函数开始的时候，Left = 0, right = arr.length - 1