常用算法Java实现之快速排序

　　快速排序和冒泡排序相似，都是通过多次比较和交换来实现排序。

　　具体流程如下：

　　1、首先设定一个分界值，通过分界值将数组分成左右两部分，将大于等于分界值的数据交换集中到右侧数组，将小于分界值的数据交换集中到左侧数组；

　　2、然后，左侧数组和右侧数组可以独立排序。对于左侧数组可以取一个分界值，将左侧数组分成左右两个部分，同样将左边放置小于分界值的数据，右侧放置大于等于分界值的数据。对右侧数组做类似处理。

　　3、重复上述过程，其实就是递归。通过递归将左侧数组排好序后，再递归处理右侧数据。当左、右两部分数据都排好序后，整个数组的排序也就完成了。

    

　　假如有初始数据：25  11  45  26  12  78。

　　1、首先设定一个分界值，这里选择第一个元素---25。在变量left中保存数组的最小序号0，在变量right中保存数组的最大序号6，在变量base中保存分界值25。

　　2、从数组右侧开始，逐个与分界值25比较，直到找到小于base的数据为止。这里，12 就比分界值25小。

　　3、将右侧比分界值小的数据，保存到 A[left]（A[0]）元素中。

　　4、从数组左侧开始，逐个与分界值25比较，直到找到大于等于base的数据为止。这里，数组最左侧的数据为12，比分界值小，将left自增1，再取A[left]（A[1]）的值为45，因45大于25，结束查找。

　　5、将左侧比分界值大的数保存到A[right]元素中。

　　6、将分界值保存到A[left]中。经过一轮比较和交换，base数据左侧的数都是比base值小的数，右侧都是比base值大的数。

　　7、接下来，通过递归调用，将left左侧的数据进行同样的排序，再将left右侧的数据进行同样的排序。

 

　　快速排序对冒泡排序进行了改进，因此具有更好的执行效率。平均时间复杂度是O(nlogn)。

 

　　Java 代码实现如下：（https://github.com/xbk417/algorithm）

    public void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
    
    private static void quickSort(int[] arr, int left, int right){
        int t;
        int ltemp = left;
        int rtemp = right;
        // 分界值
        int fIndex = arr[(left + right)/ 2];
        while(ltemp < rtemp) {
            // 从左侧开始查找比分界值大的数
            while(arr[ltemp] < fIndex) {
                // 元素小于分界值，继续查找
                ++ltemp;
            }
            // 从右侧开始查找比分界值小的数
            while(arr[rtemp] > fIndex) {
                // 元素大于分界值，继续查找
                --rtemp;    
            }
            // 如果查到的比分界值大的数的下标小于等于比分界值小的数的下标，则进行交换
            if(ltemp <= rtemp) {
                t = arr[ltemp];
                arr[ltemp] = arr[rtemp];
                arr[rtemp] = t;
                --rtemp;
                ++ltemp;
            }
            if(ltemp == rtemp) {
                ltemp++;
            }
            System.out.println( Arrays.toString(arr));
            if(left < rtemp) {
                quickSort(arr, left, ltemp - 1);
            }
            if(ltemp < right) {
                quickSort(arr, rtemp + 1, right);
            }
        }
    }