排序
把計算機全部的功能進行最終細化，歸類，可以分成三種基本功能：存儲、計算和通信。存儲數據是為了更好的查找數據，顯然，在一大堆數據里面找到我們想要的是一件很費時間的事，但若是數據是有序排列的，那將會大大節省我們的時間。
排序就是將一組對象按照某種邏輯順序重新排序的過程。
排序在商業數據處理和現代科學計算中有著重要的地位，可以應用于事物處理、組合優化、天體物理學、分子動力學、語言學、基因組學、天氣預報和很多其他領域。
選擇排序，也叫冒泡排序，每一次排序遍歷一次全部數據，然后把其中最?。ɑ蛘咦畲螅┑脑貥擞洺鰜?，遍歷完一次之后，把該元素放到數組前面。
該排序算法時間復雜度為O(n2)
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);//交換 } }插入排序
遍歷數組，把當前數據與前面元素相比較，插入恰當的位置，形成局部有序的狀態。
算法的復雜度與數據有序程度有關，最壞的情況是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); } } }希爾排序
希爾排序是一種基于插入排序的快速排序，希爾排序的思想是使數組中的任意間隔為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; } }歸并排序
自頂向下歸并排序將一組數據不斷二分，一分二，二分四，四分八，然后從最小的元素開始比較，逐漸歸并。
自頂向下歸并排序的時間復雜度為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++]; } } 自底向上歸并排序是以分治思想實現排序，將數組中的元素兩兩歸并排序，然后翻倍，直到長度超過數組。 自底向上歸并排序時間復雜度為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++]; } }快速排序
快速排序是一種分治排序，它將一個數組分成兩個子數組，兩部分獨立排序，當這兩部分自然有序時，排序就完成了。用一個切分元素，切分兩個數組，將小于切分元素的放前面，大于切分元素的放后面。
時間復雜度為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; }
新聞熱點
疑難解答
