基本思想:從a[i]右邊找到最小的數,與a[i]交換
void sort(Comparable[] a){ int n = a.length; for(int i=0; i<a.length; i++){ int min = i; for(int j=i+1; j<a.length; j++){ if(less(a[j],a[min])) min = j; } exch(a,i,j); }}基本思想:在要排序的一組數中，對當前還未排好序的范圍內的全部數，自上而下對相鄰的兩個數依次進行比較和調整，讓較大的數往下沉，較小的往上冒。即：每當兩相鄰的數比較后發現它們的排序與排序要求相反時，就將它們互換。
void sort(Comparable[] a){ int n = a.length; for(int i=n-1; i>0; i--){ for(int j=n-1; j>0; j--){ if(less(a[j],a[j-1])) exch(a,j,j-1); } } }基本思想:將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數增1的有序表
void sort(Comparable[] a){ int n = a.length; for(int i=0; i<a.length; i++){ for(int j=i+1; j>0&&less(a[j],[j-1]); j--){ exch(a,j,j-1); } }}基本思想:先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。又叫縮小增量排序。
void sort(Comparable[] a){ int n = a.length; int h = 1;//增量 while(h<n/3) h = 3*h+1;//1,4,13,... while(h>=1){ for(int i=h; i<a.length; i++){ for(int j=i+h; j>h&&less(a[j],[j-h]); j-=h){ exch(a,j,j-h); } } h = h/3; } }基本思想:一種分治的排序算法,將一個數組分成兩個子數組,將兩部分獨立排序
1）選擇一個基準元素,通常選擇第一個元素或者最后一個元素, 2）通過一趟排序講待排序的記錄分割成獨立的兩部分，其中一部分記錄 的元素值均比基準元素值小。另一部分記錄的 元素值比基準值大。 3）此時基準元素在其排好序后的正確位置 4）然后分別對這兩部分記錄用同樣的方法繼續進行排序，直到整個序列有序。
//快速排序public static void sort(Comparable[] a){ int n = a.length; sort(a, 0, n-1); }PRivate static void sort(Comparable[] a, int lo, int hi){ if(lo>=hi) 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, 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; }//重復元素較多時,三向切分的快速排序public static void sort(Comparable[] a){ int n = a.length; sort(a, 0, n-1); }private static void sort(Comparable[] a, int lo, int hi){ if(lo>=hi) return; int lt = lo, i = lo+1; gt = hi; Comparable v = a[lo]; while(i<=gt){ int cmp = a[i].comparaTo(v); if(cmp<0) exch(a, lt++; i++); else(cmp>0) exch(a, i, gt--); else i++; } sort(a, lo, lt-1); sort(a, gt+1, hi); }基本思想:歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表
//自頂向下的歸并排序public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a, 0, a.length-1); }private static void sort(Comparable[] a, int lo, int hi){ if(hi<=lo) return; int mid = (lo+hi)/2; sort(a, lo, mid); sort(a, mid+1, hi); merge(a,lo,mid,hi); }public static void merge(Comparable[] a, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) aux[k] = a[k]; //復制 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++]; } }//自底向上的歸并排序public static void sort(Comparable[] a) { int n = a.length; aux = new Comparable[n]; for( int sz=1; sz<n; sz=sz+sz){ for(int lo=0; lo<n-sz; lo+=sz+sz){ merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, n-1)); } } }public static void merge(Comparable[] a, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) aux[k] = a[k]; //復制 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++]; } }基本思想堆的定義如下：具有n個元素的序列（k1,k2,…,kn),當且僅當滿足 
時稱之為堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最小項（小頂堆）。 若以一維數組存儲一個堆，則堆對應一棵完全二叉樹，且所有非葉結點的值均不大于(或不小于)其子女的值，根結點（堆頂元素）的值是最小(或最大)的。
public static void sort(Comparable[] a){ int n = a.length; for(int k=n/2; k>=1; k--) sink(a,k,n); while(n>1){ exch(a,1,--n); sink(a,1,n); } } private static void sink(Comparable[] a, int k, int n){ while(2*k<=n-2){ int j = 2*k; if(j<n && less(a[j], a[j+1])) j++; if(!less(a[k],a[j])) break; exch(a,k,j); k = j; } }新聞熱點
疑難解答
