快速排序

快速排序是效率比较高的排序方式，采用分治法思想，将规模较大的问题分解成规模较小的子问题，它的时间复杂度O(nlog2n)。

描述：

1、选定第一个值为基准值，在数组两端设置一个低指针和一个高指针，从两端往中间遍历。
2、高指针从右往左走，遇到比基准值小的就赋值给低指针，切换方向从低指针往右走；低指针遇到比基准值大的就赋值给高指针，切换方向；
3、最终高指针和低指针重合，本次遍历结束，此时基准值左侧元素都比它小，右侧都比他大。
4、数组从基准值处一分为二，各自重复以上过程直到分成N个长度为1的数组，数组完成排序（类似二叉树前序遍历）。

动画：

快速排序.gif

代码：

       private void quickSort(int[] array, int start, int end) {
        if (array.length <= 1 || start >= end) {
            //数组最后会分解成长度为1的小数组，而且start值等于end，到此递归结束
            return;
        }
        //取第一个值为基准值
        int temp = array[start];
        int low = start;
        int high = end;
        //false 从高指针往低指针走
        //true  从低指针往高指针走
        boolean direction = false;
        while (low < high) {
            if (!direction) {
                if (temp <= array[high]) {
                    //高指针对应的值比基准值大
                    //高指针左移
                    high--;
                } else {
                    //高指针对应的值比基准值小
                    //把这个值放在低指针位置
                    //低指针右移
                    //切换移动方向
                    array[low++] = array[high];
                    direction = !direction;
                }
            } else {
                if (temp >= array[low]) {
                    low++;
                } else {
                    array[high--] = array[low];
                    direction = !direction;
                }
            }
        }
        //指针移动结束把基准值放在高低指针重合处
        array[low] = temp;
        //这时候基准值左侧元素都是比它小的，右侧都是比他大的
        //数组从基准值处一分为二，各自重复以上过程
        quickSort(array, start, low - 1);
        quickSort(array, low + 1, end);
    }