https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

它的基本思想是

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

仍以归并排序示例中的数列进行举例

初始状态{6,202,100,301,38,8,1}

第一轮排序，比较6次

设定两个指针，i = 1 从前向后找，j = 6从后向前找

锚定6，从后向前查找比6小的数字，找到1，j--，交换6和1（比较1次）

{1},{202,100,301,38,8},{6}

从前向后找，大于6的数字，找到202，i++，交换6和202（比较1次）

{1},{6},{100,301,38,8,202}

从后向前查找比6小的数字，未找到（比较4次）

第二轮排序，比较4次

此时，i = 3 从前向后找，j = 5从后向前找

锚定100，从后向前查找比100小的数字，找到8，交换100和8（比较2次）

{1,6},{8,301,38},{100},{202}

从前向后查找，比100大的数字，找到301，交换100和301（比较1次）

{1,6},{8},{100,38},{301,202}

从后向前查找，比100小的数字，找到38，交换100和38（比较1次）

{1,6},{8,38},{100},{301,202}

第三轮排序，比较2次

比较8和38，8比38小，顺序无需变更（比较1次）

比较301和202，更换顺序（比较1次）

{1,6},{8,38},{100},{202,301}

完成排序

java代码：

    public static int[] qsort(int[] arr, int start, int end){
        if(start >= end){
            return arr;
        }
        int i = start;
        int j = end;
        int point = arr[start];
        while(i < j){
            while((i < j) && arr[j] > point){
                j --;
            }
            while((i < j) && arr[i] < point){
                i ++;
            }
            if(i < j && arr[i] == arr[j]){
                i ++;
            } else if(i < j){
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
            System.out.println(Arrays.toString(arr) + String.format(" - %d @ [%d, %d]", point, start, end));
        }
        System.out.println("--");
        arr = qsort(arr, start, i - 1);
        arr = qsort(arr, i + 1, end);
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = {6, 202, 100, 301, 38, 8, 1};
        System.out.println(Arrays.toString(arr) + " - start");
        arr = qsort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr) + " - end");
    }

输出：

[6, 202, 100, 301, 38, 8, 1] - start
[1, 202, 100, 301, 38, 8, 6] - 6 @ [0, 6]
[1, 6, 100, 301, 38, 8, 202] - 6 @ [0, 6]
[1, 6, 100, 301, 38, 8, 202] - 6 @ [0, 6]
--
[1, 6, 8, 301, 38, 100, 202] - 100 @ [2, 6]
[1, 6, 8, 100, 38, 301, 202] - 100 @ [2, 6]
[1, 6, 8, 38, 100, 301, 202] - 100 @ [2, 6]
[1, 6, 8, 38, 100, 301, 202] - 100 @ [2, 6]
--
[1, 6, 8, 38, 100, 301, 202] - 8 @ [2, 3]
--
[1, 6, 8, 38, 100, 202, 301] - 301 @ [5, 6]
[1, 6, 8, 38, 100, 202, 301] - 301 @ [5, 6]
--
[1, 6, 8, 38, 100, 202, 301] - end