快速排序

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。-----百度百科
按照上面的描述，关键词有两个：1、分割 2、递归
我们一个一个处理。
先上一个要处理的数组：

int[] a={49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };

Sep1、分割：
在数组中随便找一个基准值作为分割标准，将数组按照基准值分割为两部分。左边小右边大。
要达到这个要求首先需要一个基准值pivot，还需要两个游标high和low，分别在数组右侧和左侧。
下面开始分割

• 拿到基准值pivot，我们不妨把它设为a[0]
• 将low设为数组最右侧也就是a[0],将high设为数组最左侧也就是a[a.length-1]
• 将a[high]跟基准值pivot比较，如果比a[high]大就high--往下找，直到找到pivot比a[high]小的，然后把a[high]跟a[low]换位置，换完位置换到low游标
• 将a[low]跟基准值pivot比较，如果比a[low]小就low++往下找，直到找到pivot比a[low]大的，然后把a[low]跟a[high]换位置，换完位置换到high游标
• 循环往复，当low和high两个游标相遇我们就完成了一次分割
  下面是实现：

//将low设为数组最右侧也就是a[0],将high设为数组最左侧也就是a[a.length-1]
public static int apartByPivot(int[] a,int low,int high){
        int pivot=a[low];//基准值pivot，我们不妨把它设为a[0]
        int temp;
        while(low!=high){//游标相遇表示分边完成退出循环
            while(a[high]>=pivot && low<high){//比基准值大，并且游标没相遇
                high--;
            }
            //交换
            temp=a[high];
            a[high]=a[low];
            a[low]=temp;
            while(a[low]<=pivot && high>low){//同上
                low++;
            }
            //交换
            temp=a[high];
            a[high]=a[low];
            a[low]=temp;
        }
        a[high]=pivot;//基准值的正确位置，
        return high;
    }

Step2、递归
做完第一步之后我们得到了两个部分，一边比基准值大，另一边则小。
此时我们只要在将两边的数组一直重复这个步骤，最终就能将一开始的a[]排序完成。
开始实现：

public static void quickSort(int[] a,int low,int high){
        if(low>=high){return;}//如果游标相遇则表示分边完成
        int index=apartByPivot(a,low,high);//拿到数组之后分为大小两边
        quickSort(a,low,index-1);//将小的一边分边
        quickSort(a,index+1,high);//将大的一边分边
    }

这样就完成了，试试效果。

public static void main(String[] args) {
        int[] a={49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
        quickSort(a,0,a.length-1);
        for(int t:a){
            System.out.print(t+",");
        }
    }
//-1,0,1,2,5,8,22,22,23,38,49,65,76,97,