快速排序

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

《算法：第4版》

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

快速排序的优点：

速度最快，原地排序

算法的时间复杂度是 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();

    }

}