快速排序

思想

快速排序采用的思想是分治思想。
快速排序是找出一个元素（理论上可以随便找一个）作为基准（pivot），然后对数组进行分区操作，使基准左边元素的值都不大于基准值，基准右边的元素值都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，讲其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

例子

初始序列：6，1，2，7，9，3，4，5，10，8
两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换它们。这里可以用两个变量i和j，分别执行序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i执行序列的最左边（即i=0）,指向数字6。让哨兵j执行序列的最右边（即j=9）,指向数字8.

2.png

首先哨兵j开始出动。因为此处设置的基准数是最左边的树，所以需要让哨兵j先出动。这一点非常重要。哨兵j一步一步地向左挪动（即j--），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。

3.png

现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下：
6，1，2，5，9，3，4，7，10，8
到此，第一次交换结束。接下来哨兵j继续向左挪动。他发现了4（比基准数6小，满足要求）之后停了下来。哨兵i也继续像右挪动，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下
6，1，2，5，4，3，9，7，10，8

4.png

第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6小，满足要求）之后又停了下来。哨兵i继续向右挪动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3交换。交换之后的序列如下：
3，1，2，5，4，6，9，7，10，8

5.png

到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的树都大于等于6.
回顾一下刚才的过程，其实哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止。
ok,解释完毕，现在基准数6已经归位，它正好在序列的第5位。此时我们已经将原来的序列，以6位分界点拆分成了两个序列，左边的序列是“3，1，2，5，4”，右边的序列是“9，7，10，8”.接下来还需要分别处理这两个序列，按照刚刚的方法。

6.png
到此，排序完全结束。
快速排序的每一轮处理其实就是将这一轮的基准数归位，直到所有的数都归位为止，排序就结束了。

总结

快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放在基准点的左边，将大于等于基准点的数全部放在基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的，都是O(NN)，它的平均时间复杂度O(NlogN)。

代码

 private static int getPartition(int[] array,int begin,int end) {
        int pivotIndex = begin;
        int pivot = array[begin];
        while (begin != end) {
            while (array[end] > pivot&&end!=begin){
                end--;
            }
            while (array[begin]<=pivot&&end!=begin) {
                begin++;
            }
            if(begin!=end){
                int temp = array[begin];
                array[begin]= array[end];
                array[end]=temp;
            }
        }

        int temp = array[pivotIndex];
        array[pivotIndex] = array[begin];
        array[begin]=temp;
        return begin;
    }

    public static void fastSort(int[] array,int begin,int end){
        if(null== array|| array.length<=1){
            return;
        }

        if(begin>=end){
            return;
        }
        int partition = getPartition(array,begin,end);
        fastSort(array,begin,partition-1);
        fastSort(array,partition+1,end);
    }