概述

快速排序算法是基于交换的高效排序算法, 采用了分治的思想.

其基本思想如下:

1. 从数列中取出一个数作为基准数
2. 将数组进行划分, 将比基准数大的元素移至右侧, 比基准数小的元素移至左侧
3. 对左右的子区间重复进行排序, 直至每个子区间只有一个元素

其时间空间复杂度如下:

快速排序就是将小的放左边, 大的放右边, 在对左右进行重复执行.

其代码实现如下:

/**
 * 快速排序实现数组排序, 从小到大顺序
 * 
 * @param arr
 */
public static void quickSort(int[] arr) {
    qSort(arr, 0, arr.length - 1);
}

/**
 * 快速排序实现数组排序, 从小到大顺序
 * 
 * @param arr
 *            数组
 * @param head
 *            头下标
 * @param tail
 *            尾下标
 */
private static void qSort(int[] arr, int head, int tail) {
    /*
     * 1. 从数列中选出一个数作为基准数
     * 2. 将比基准数大的移动到右面,小的移动到左面
     * 3. 对基准数的左右两个子数列进行排序
     */
    int i = head, j = tail;
    // 当区间只有一个元素或没有元素时, 返回
    if (i >= j || i < 0 || j >= arr.length) {
        return;
    }
    // 将第一个元素作为基准值
    int key = arr[i];
    // i从前向后, j从后向前, 进行遍历
    while (i < j) {
        // 从后向前找到第一个小于基准值的元素, 不能到i前面
        for (; i < j && arr[j] >= key; j--);
        // 将找到的小于基准值的元素拿到前面来
        arr[i] = arr[j];
        // 从前向后找到第一个大于基准值的元素, 不能到j后面
        for (; i < j && arr[i] <= key; i++);
        // 将找到的大于基准值的元素拿到后面
        arr[j] = arr[i];
    }
    // 将中间的空位补为基准值
    arr[i] = key;
    /*
     * 程序运行到此 
     * i之后的元素都是大于基准值的 
     * j之前的元素都是小于基准值的 
     * 此时, 基准值已经找到了它的位置, 不用再管
     */
    // 对基准值之前的序列进行排序
    qSort(arr, head, i - 1);
    // 对基准值之后的序列进行排序
    qSort(arr, i + 1, tail);
}

同时, 快速排序也可以进行三切分, 分为大于、等于、小于三组, 对于重复元素比较多的情况, 如此切分是比较好的, 可以有效避免相等元素的比较, 将相等元素聚集起来, 就可以不必再切分这些元素了.