排序算法--快速排序

算法思想：
树立一个基准数(以此数作为比较的标杆),分别从数组两边进行探测查找，右边的探测结束条件为找到一个比基准数小的数，左边的探测结束条件为找到一个基准数大的数，当左右两边的探测都结束后，交换这两个数；重复以上过程，直到两边探测的索引相遇(一致)。最后将基准数与索引相遇的位置上的数交换。废话不多说，上图：
假设我们对{6,1,2,7,9,3,4,5,10,8}这10个数进行排序。

20180802182433217.png

注：i,j分别为左右两端的探测，姑且称它们为哨兵，首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，否则会出现递归无法退出的情况。哨兵j一步一步地向左挪动(即j--)，直到找到一个小于6的数停下来，接下来哨兵i再一步一步向右挪动(即i++)，直到找到一个大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

20180802183238258.png

交换哨兵i和哨兵j所指向元素的值，交换后序列如下：
6 1 2 5 9 3 4 7 10 8
到此，第一次交换结束。接下来哨兵继续向左挪动。它发现了4之后停了下来。哨兵i也继续向右挪动，它发现9之后停了下来。此时再次进行交换，再次进行交换，交换之后的序列如下：
6 1 2 5 4 3 9 7 10 8

20180802183238258.png

第二次交换结束，探测继续。哨兵j继续向左挪动，它发现了3之后又停了下来。此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时探测结束。我们将基准数6和3进行交换。交换之后的序列如下。
3 1 2 5 4 6 9 7 10 8

20180802190301222.png

到此第一轮探测真正结束，此时以6为分界点，6左边的数都小于等于6，6右边的数都大于等于。
此时我们已经将原来的序列以6为分界点拆分成了两个序列，左边序列{3,1,2,5,4},右边序列{9,7,10,8}，接下来只需要再以上述同样的方法对这两个序列分别进行排序即可。

快排的java实现：

public class QuickSortTest {
    public void quickSort(int[] arr,int left,int right){
        if(left > right)
            return;
        int i = left;
        int j = right;
        int temp = arr[left];

        while(i!=j){
            while(i<j && arr[j]>=temp)
                j--;
            while(i<j && arr[i]<=temp)
                i++;

            if(i<j){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }

        }

        arr[left] = arr[i];
        arr[i] = temp;

        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);
    }
}