快速排序

https://www.bilibili.com/video/BV1at411T75o

《算法：第4版》

软考：程序员中的快速排序

https://www.bilibili.com/video/BV1YY411g7gw

https://www.bilibili.com/video/BV15f4y1i7Vt

快速排序的优点：

速度最快，原地排序

算法的时间复杂度是 NlgN

实现

数组版

public class Quick {

    public static void sort(Comparable[] a) {
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }

        int j = partition(a, lo, hi); //切分
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private static int partition(Comparable[] a, int lo, int hi) {
        //将数组切分为a[lo……i-1]，a[i]，a[i+1……hi]
        int i = lo, j = hi + 1; //左右扫描指针
        Comparable v = a[lo]; //切分元素

        while (true) {//扫描左右，检查扫描是否结束并交换元素

            while (less(a[++i], v)) {
                if (i == hi) {
                    break;
                }
            }

            while (less(v, a[--j])) {
                if (j == lo) {
                    break;
                }
            }

            if (i >= j) {
                break;
            }

            exch(a, i, j);

        }//end while

        exch(a, lo, j);

        return j;

    }//end partition


    /**
     * 自定义比较规则
     *
     * @param a
     * @param b
     * @return
     */
    private static boolean less(Comparable a, Comparable b) {
        boolean ret = false;
        if (a instanceof Integer && b instanceof Integer) {
            ret = (Integer) a < (Integer) b;
        }
        return ret;
    }

    private static void exch(Comparable[] a, int lo, int j) {
        Comparable tmp = a[lo];
        a[lo] = a[j];
        a[j] = tmp;
    }

    public static void main(String[] args) {
        Integer[] arr = {5,4,6,3,7,2,8,1,9,0};
        Quick.sort(arr);

        System.out.print(arr[0]);

        for (int i = 1; i < arr.length; i++) {
            System.out.printf(", %d", arr[i]);
        }

        System.out.println();
    }

}

数组泛型版

public class Quick1<T> {

    public static <T> void sort(Comparable<T>[] a) {
        sort(a, 0, a.length - 1);
    }

    private static <T> void sort(Comparable<T>[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }

        int j = partition(a, lo, hi); //切分
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    private static <T> int partition(Comparable<T>[] a, int lo, int hi) {
        //将数组切分为a[lo……i-1]，a[i]，a[i+1……hi]
        int i = lo, j = hi + 1; //左右扫描指针
        Comparable v = a[lo]; //切分元素

        while (true) {//扫描左右，检查扫描是否结束并交换元素

            while (less(a[++i], v)) {
                if (i == hi) {
                    break;
                }
            }

            while (less(v, a[--j])) {
                if (j == lo) {
                    break;
                }
            }

            if (i >= j) {
                break;
            }

            exch(a, i, j);

        }//end while

        exch(a, lo, j);

        return j;

    }//end partition


    /**
     * 自定义比较规则
     *
     * @param a
     * @param b
     * @return
     */
    private static boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) == -1;
    }

    private static void exch(Comparable[] a, int lo, int j) {
        Comparable tmp = a[lo];
        a[lo] = a[j];
        a[j] = tmp;
    }

    public static void main(String[] args) {
//        Integer a = 1;
//        Integer b = 2;
//        boolean ret = less(a, b);
//        System.out.println(ret);

        Integer[] arr = {5,4,6,3,7,2,8,1,9,0};
        Quick.sort(arr);

        System.out.print(arr[0]);

        for (int i = 1; i < arr.length; i++) {
            System.out.printf(", %d", arr[i]);
        }

        System.out.println();

    }
}

列表泛型版

package quicksort;

import java.util.Arrays;
import java.util.List;

public class QuickSort<T extends Comparable> {

    private static <T extends Comparable> boolean less(T a, T b) {
        return a.compareTo(b) == -1;
    }

    private static <T> void exch(List<T> a, int lo, int j) {
        T tmp = a.get(lo);
        a.set(lo, a.get(j));
        a.set(j, tmp);
    }

    private static <T extends Comparable> int partition(List<T> a, int lo, int hi) {
        //将数组切分为a[lo……i-1]，a[i]，a[i+1……hi]
        int i = lo, j = hi + 1; //左右扫描指针
        T v = a.get(lo); //切分元素

        while (true) {//扫描左右，检查扫描是否结束并交换元素

            while (true) {
                ++i;

                if (!less(a.get(i), v)) {
                    break;
                }

                if (i == hi) {
                    break;
                }
            }


            while (true) {
                --j;

                if (!less(v, a.get(j))) {
                    break;
                }

                if (j == lo) {
                    break;
                }

            }

            if (i >= j) {
                break;
            }

            exch(a, i, j);

        }//end while

        exch(a, lo, j);

        return j;

    }//end partition

    public static <T extends Comparable> void sort(List<T> list) {
        sort(list, 0, list.size() - 1);
    }

    private static <T extends Comparable> void sort(List<T> a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }

        int j = partition(a, lo, hi); //切分
        sort(a, lo, j - 1);
        sort(a, j + 1, hi);
    }

    public static void main(String[] args) {

        List<Integer> list = Arrays.asList(5,4,6,3,7,2,8,1,9,0);

        QuickSort.sort(list);

        System.out.print(list.get(0));

        for (int i = 1; i < list.size(); i++) {
            System.out.printf(", %d", list.get(i));
        }

        System.out.println();

    }

}

快速排序旗舰版

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.List;

/**
 * 可应用快速排序算法对数组和列表进行排序
 * @param <T>
 */
public class PremiumQuickSort<T extends Comparable> {

    private static <T extends Comparable> boolean less(T a, T b) {
        return a.compareTo(b) == -1;
    }

    private static <T extends Comparable> void exch(T[] arr, int lo, int j) {
        T t = arr[lo];
        arr[lo] = arr[j];
        arr[j] = t;
    }

    private static <T extends Comparable> int partition(T[] a, int lo, int hi) {

        //将数组切分为a[lo……i-1]，a[i]，a[i+1……hi]
        int i = lo, j = hi + 1; //左右扫描指针
        T v = a[lo]; //切分元素

        while (true) {//扫描左右，检查扫描是否结束并交换元素

            while (less(a[++i], v)) {
                if (i == hi) {
                    break;
                }
            }

            while (less(v, a[--j])) {
                if (j == lo) {
                    break;
                }
            }

            if (i >= j) {
                break;
            }

            exch(a, i, j);

        }//end while

        exch(a, lo, j);

        return j;

    }//end partition

    private static <T extends Comparable> void sort(T[] arr, int lo, int hi) {
        if (hi <= lo) {
            return;
        }

        int j = partition(arr, lo, hi); //切分
        sort(arr, lo, j - 1);
        sort(arr, j + 1, hi);
    }

    public static <T extends Comparable> void sort(T[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    public static <T extends Comparable> List<T> sort(Class<T> clazz, List<T> list) {
        T[] arr = (T[]) Array.newInstance(clazz, list.size());
        list.toArray(arr);
        sort(arr);
        list = Arrays.asList(arr);
        return list;
    }

    public static void main(String[] args) {
        Integer[] arr = {5,4,6,3,7,2,8,1,9,0};

        //测试数组
        PremiumQuickSort.sort(arr);
        System.out.print(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            System.out.printf(", %d", arr[i]);
        }
        System.out.println();

        //测试列表
        List list = Arrays.asList(5,4,6,3,7,2,8,1,9,0);
        list = PremiumQuickSort.sort(Integer.class, list);
        System.out.print(list.get(0));
        for (int i = 1; i < arr.length; i++) {
            System.out.printf(", %d", list.get(i));
        }
        System.out.println();
    }
}

快速排序+插入排序混合

对于小数组，快速排序比插入排序慢；

因为递归，快速排序的sort()方法在小数组中也会调用自己。

因此，在排序小数组时应该切换到插入排序。一般来说它们能将性能提升20%~30%。

import Insertion.Insertion;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.List;

/**
 * 可应用快速排序算法和插入排序算法对数组和列表进行排序
 * 对于元素个数小于m的数组将应用插入排序算法
 * 需要通过实验来确定选择m的最佳参数值
 * @param <T>
 */
public class MixQuickSort<T extends Comparable> {

    private static <T extends Comparable> boolean less(T a, T b) {
        return a.compareTo(b) == -1;
    }

    private static <T extends Comparable> void exch(T[] arr, int lo, int j) {
        T t = arr[lo];
        arr[lo] = arr[j];
        arr[j] = t;
    }

    private static <T extends Comparable> int partition(T[] a, int lo, int hi) {

        //将数组切分为a[lo……i-1]，a[i]，a[i+1……hi]
        int i = lo, j = hi + 1; //左右扫描指针
        T v = a[lo]; //切分元素

        while (true) {//扫描左右，检查扫描是否结束并交换元素

            while (less(a[++i], v)) {
                if (i == hi) {
                    break;
                }
            }

            while (less(v, a[--j])) {
                if (j == lo) {
                    break;
                }
            }

            if (i >= j) {
                break;
            }

            exch(a, i, j);

        }//end while

        exch(a, lo, j);

        return j;

    }//end partition

    private static <T extends Comparable> void sort(T[] arr, int lo, int hi, int m) {
        if (hi <= lo + m) {
            Insertion.sort(arr, lo, hi);
            return;
        }

        int j = partition(arr, lo, hi); //切分
        sort(arr, lo, j - 1, m);
        sort(arr, j + 1, hi, m);
    }

    public static <T extends Comparable> void sort(T[] arr) {
        sort(arr, 0, arr.length - 1, 15);
    }

    public static <T extends Comparable> List<T> sort(Class<T> clazz, List<T> list) {
        T[] arr = (T[]) Array.newInstance(clazz, list.size());
        list.toArray(arr);
        sort(arr);
        list = Arrays.asList(arr);
        return list;
    }

    public static void main(String[] args) {
        Integer[] arr = {5,4,6,3,7,2,8,1,9,0};

        //测试数组
        MixQuickSort.sort(arr);
        System.out.print(arr[0]);
        for (int i = 1; i < arr.length; i++) {
            System.out.printf(", %d", arr[i]);
        }
        System.out.println();

        //测试列表
        List list = Arrays.asList(5,4,6,3,7,2,8,1,9,0);
        list = MixQuickSort.sort(Integer.class, list);
        System.out.print(list.get(0));
        for (int i = 1; i < arr.length; i++) {
            System.out.printf(", %d", list.get(i));
        }
        System.out.println();
    }

}

转换参数M的最佳值是和系统相关的，但是5~15之间的任意值在大多数情况下都能令人满意。

注意事项

一般来说，快速排序是空间复杂度和时间复杂度两全其美的方案，但在最坏情况下，比如：[5,4,3,2,1]这样完全逆序的数组，比较切分用的 pivot 元素每次都取 arr[lo] 的话，

将切分成 [][5][4,3,2,1]，然后[4,3,2,1]又切分成[][4][3,2,1]，……，这样并不能有效地将序列切分，时间复杂度将由 O(nlogn) 下降到 O(n²)，可以通过取随机位置的元素作为 pivot 进行优化：

Random r = new Random();
T v = a[r.nextInt(j)];