排序

    把計算機全部的功能進行最終細化，歸類，可以分成三種基本功能：存儲、計算和通信。存儲數(shù)據(jù)是為了更好的查找數(shù)據(jù)，顯然，在一大堆數(shù)據(jù)里面找到我們想要的是一件很費時間的事，但若是數(shù)據(jù)是有序排列的，那將會大大節(jié)省我們的時間。

    排序就是將一組對象按照某種邏輯順序重新排序的過程。

    排序在商業(yè)數(shù)據(jù)處理和現(xiàn)代科學計算中有著重要的地位，可以應用于事物處理、組合優(yōu)化、天體物理學、分子動力學、語言學、基因組學、天氣預報和很多其他領域。

選擇排序

    選擇排序，也叫冒泡排序，每一次排序遍歷一次全部數(shù)據(jù)，然后把其中最小（或者最大）的元素標記出來，遍歷完一次之后，把該元素放到數(shù)組前面。

    該排序算法時間復雜度為O(n²)

    public static void sort(Comparable[] a) {        int n = a.length;        for (int i = 0; i < n; i++) {            int min = i;            for (int j = i+1; j < n; j++) {                if (less(a[j], a[min])) min = j;//比較            }            exch(a, i, min);//交換        }    }
插入排序
    遍歷數(shù)組，把當前數(shù)據(jù)與前面元素相比較，插入恰當?shù)奈恢茫纬删植坑行虻臓顟B(tài)。
    算法的復雜度與數(shù)據(jù)有序程度有關，最壞的情況是O(n2)
    public static void sort(Comparable[] a) {        int n = a.length;        for (int i = 0; i < n; i++) {            for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {                exch(a, j, j-1);            }        }    }
希爾排序
    希爾排序是一種基于插入排序的快速排序，希爾排序的思想是使數(shù)組中的任意間隔為h的元素都有序。
    public static void sort(Comparable[] a) {        int n = a.length;        int h = 1;        while (h < n/3) h = 3*h + 1;         while (h >= 1) {            for (int i = h; i < n; i++) {                for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {                    exch(a, j, j-h);                }            }            h /= 3;        }    }
歸并排序
    自頂向下歸并排序將一組數(shù)據(jù)不斷二分，一分二，二分四，四分八，然后從最小的元素開始比較，逐漸歸并。
    自頂向下歸并排序的時間復雜度為O(NlgN)，空間復雜度為O(N)。
    public static void sort(Comparable[] a) {        Comparable[] aux = new Comparable[a.length];        sort(a, aux, 0, a.length-1);    }
    PRivate static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {        if (hi <= lo) return;        int mid = lo + (hi - lo) / 2;        sort(a, aux, lo, mid);        sort(a, aux, mid + 1, hi);        merge(a, aux, lo, mid, hi);    }
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {        for (int k = lo; k <= hi; k++) {            aux[k] = a[k];         }        int i = lo, j = mid+1;        for (int k = lo; k <= hi; k++) {            if      (i > mid)              a[k] = aux[j++];            else if (j > hi)               a[k] = aux[i++];            else if (less(aux[j], aux[i])) a[k] = aux[j++];            else                           a[k] = aux[i++];        }    }    自底向上歸并排序是以分治思想實現(xiàn)排序，將數(shù)組中的元素兩兩歸并排序，然后翻倍，直到長度超過數(shù)組。
    自底向上歸并排序時間復雜度為O(NlgN)，空間復雜度為O(N)。
    public static void sort(Comparable[] a) {        int n = a.length;        Comparable[] aux = new Comparable[n];        for (int len = 1; len < n; len *= 2) {            for (int lo = 0; lo < n-len; lo += len+len) {                int mid  = lo+len-1;                int hi = Math.min(lo+len+len-1, n-1);                merge(a, aux, lo, mid, hi);            }        }    }
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {        for (int k = lo; k <= hi; k++) {            aux[k] = a[k];         }        int i = lo, j = mid+1;        for (int k = lo; k <= hi; k++) {            if      (i > mid)              a[k] = aux[j++];            else if (j > hi)               a[k] = aux[i++];            else if (less(aux[j], aux[i])) a[k] = aux[j++];            else                           a[k] = aux[i++];        }    }
快速排序
     快速排序是一種分治排序，它將一個數(shù)組分成兩個子數(shù)組，兩部分獨立排序，當這兩部分自然有序時，排序就完成了。用一個切分元素，切分兩個數(shù)組，將小于切分元素的放前面，大于切分元素的放后面。
    時間復雜度為O(NlgN)。
    public static void sort(Comparable[] a) {        StdRandom.shuffle(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) {        int i = lo;        int 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);        }        exch(a, lo, j);        return j;    }