基本思想

每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的一边，将大于等于基准点的数全部放到基准点的另一边.

时间复杂度

因此快速排序的最差时间复杂度和冒泡排序是一样的，都是 O(N^2 )，它的平均时间复杂度为 O(NlogN)。

Java实现（从大到小）

    public static void main(String[] args) {
        int length = 20;
        int maxValue = 20;
        int[] array = new int[length];
        Random r = new Random();
        for (int i = 0; i < array.length; i++) {
            array[i] = r.nextInt(maxValue);
        }
        System.out.println(Arrays.toString(array));
        quickSort(array, 0, length-1);
        System.out.println(Arrays.toString(array));
    }


    // 假设以左边的为基数，那就要从右边开始移动。左为大于基数，右为小于基数
    public static void quickSort(int[] array, int leftPoint, int rightPoint) {
        if (leftPoint > rightPoint) {
            return;
        }
        int swapTmp = 0;
        int baseNumber = array[leftPoint];// 以左边为基准
        int i = leftPoint;
        int j = rightPoint;
        while (leftPoint != rightPoint) {
            // 从右边开始向左移动，到找第一个大于基数时停止
            while (array[rightPoint] <= baseNumber && leftPoint < rightPoint) {
                rightPoint--;
            }

            // 从左边开始向右移动，到找第一个小于基数时停止
            while (array[leftPoint] >= baseNumber && leftPoint < rightPoint) {
                leftPoint++;
            }

            // 没有相遇时，就交换
            if (leftPoint < rightPoint) {
                swapTmp = array[leftPoint];
                array[leftPoint] = array[rightPoint];
                array[rightPoint] = swapTmp;
            }
        }
        //恢复新一轮的基准，将旧的基准归位，然后又重新定一个新的左边基准位。即将基准数与中间数互换
        array[i] = array[leftPoint];
        array[leftPoint] = baseNumber;

        //递归左，右两边
        quickSort(array, i, leftPoint-1);
        quickSort(array, leftPoint+1, j);
    }