排序算法:快速排序

作为一个自己的复习记录，此处暂时只实现一个最简单的快排。
关于快排更深入的探讨。参考本文末尾的链接。

基本思想：
1，建立一个支点作为基准点，值记为temp
2，从数列左右两边依次向中间查找，一定要注意先右后左(此处思考为什么)。索引分别记为 i和 j。
3，左边找比temp大的元素，找到后停止。右边找比temp小的元素，找到后停止。当两边都找到以后，两个元素交换位置。
4，两边向中间查找的终止条件为 i==j，此时的i==j的索引值，记为index。终止后，再把temp元素和arr[index]互换。
5，互换之后，此时的数列就是index为中心，左边子数列所有元素比arr[index]小，右边子数列元素比arr[index]大
6，再对两个子数列递归调用当前函数，直到全部有序。

要注意的几点：
1，一定要在开始查找开始之前，判断当前函数终止条件。即 left>=right时(此时已经递归到最底层)，return。
2，查找时 i 和 j 的 条件也一定不能忘，始终保持i<j 直到相遇，不然两个可能错过去了。
3，左子数列left=left, right=index-1。右子数列left=index+1, right=right

以下是Java实现的源码：

public void quickSort(int[] arr, int left, int right){
        int temp = arr[left];
        int i = left;
        int j = right;
        int t;

        if(left >= right){
            return;
        }

        while (i != j){
            //由于是以左为基准，所以先从右边查找。
            while (arr[j] >= temp && i<j){
                j--;
            }
            while (arr[i] <= temp && i<j){
                i++;
            }
            //都找到以后，交换两个索引中元素的值
            if(i<j) {
                t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }

        //基准数和ij相遇的数互换，也就是基准数归位
        arr[left] = arr[i];
        arr[i] = temp;

        //处理左边
        quickSort(arr,left, i-1);
        //处理右边
        quickSort(arr, i+1, right);
        return;
    }

（如果有什么错误或者建议，欢迎留言指出）

---

参考资料:
来自简书：这个文章更全面的介绍了快速排序的各种算法及其原理
快读排序原理及其算法实现-单轴快速排序-三向切分快速排序-双轴快速排序