快速排序

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

快速排序

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

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