在学习快速排序之前我们来看一下什么冒泡排序

import java.util.Arrays;

public class 冒泡排序 {
    public static void main(String[] args) {

        int[] test = new int[]{9, 1, 5, 8, 7, 4, 6, 2};
        //用于交换的临时值
        int temp = 0;
        for (int i = 0; i < test.length; i++) {
            for (int j = test.length - 1; j > i; j--) {
            //如果前一位数比后一位大则交换两个数
                if (test[j - 1] > test[j]) {
                    temp = test[j - 1];
                    test[j - 1] = test[j];
                    test[j] = temp;
                }
            }
        }
        //记得Java的话直接test.toString()可是没法输出数组的...
        System.out.println(Arrays.toString(test));

    }
}

冒牌排序的核心思路是两两交换, 它是一种时间换空间的排序算法, (因为它不耗费什么额外空间), 最坏情况是把逆序的数列变成顺序, 所以最差的时间复杂度是O(N^2), 最好的情况下是O(N)一遍过, 平均就是O(N^2)

快速排序是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

就是你选择一个点, 然后左端有端两个指针, 把比那个点小的放在左边, 大的放右边, 递归处理.

最差情况显而易见, 划分之后一边是一个, 另一边是n-1个, 这种极端情况的时间复杂度就是O(N^2), 最好的情况就是每次都能均匀的划分序列(中轴两边的数相等), 时间复杂度就是O(N*log2N)

正因为如此, 所以它不稳定, 而冒泡排序是稳定的O(N^2)

现在让我们来尝试实现一下快速排序

package baguwen;

import java.util.Arrays;

public class quickSort {


    public static void main(String[] args) {
        int a[] = {3, 5, 9, 4, 11, 6, 7, 25, 33, 54, 99};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }

    public static void quickSort(int[] a, int left, int right) {
        int pivot = a[(left + right) / 2];
        //pivot作为中轴 比它小的放在左边 比它大的放在右边
        int l = left;
        int r = right;
        while (l < r) {
            //开始比较! 只要左指针的位置不超过右指针的位置就不能停下来
            while (a[l] < pivot) {
                //在左侧找到一个比中轴值大的为止
                l = l + 1;
            }
            while (pivot < a[r]) {
                //在右侧找到一个比中轴值小的为止
                r = r - 1;
            }
            if (l <= r) {
                //交换他们俩!
                int temp = a[l];
                a[l] = a[r];
                a[r] = temp;
                l++;
                r--;
                //至于为什么要l++和r--,你想想如果不加的话是不是就陷入死循环了
            }
            //这样就进行完一个轮回啦, 马上就要开始下一个轮回了冲冲冲
        }
        if (left < r) {
            quickSort(a, left, r);
        }
        if (l < right) {
            quickSort(a, l, right);
        }
    }

}