import java.lang.reflect.Method;
import java.util.Arrays;
import java.util.Date;

/**
 * Java常用排序算法及性能測試集合
 *
 * 本程序集合涵蓋常用排序算法的編寫，并在注釋中配合極其簡單的特例講解了各種算法的工作原理，以方便理解和吸收；
 * 程序編寫過程中吸收了很多維基百科和別人blog上面的例子，并結(jié)合自己的思考，選擇并改進(jìn)一個最容易讓人理解的寫法
 *（尤其是快速排序，我覺得我寫的算法最好理解）。
 * 同時包含一個集中式的性能測試和正確性測試方法，方便觀測。
 * @author /link.php?url=http://blog.csdn.net/sunxing007
 * 轉(zhuǎn)載請注明來自/link.php?url=http://blog.csdn.net/sunxing007
 */
public class SortUtil {
 // 被測試的方法集合
 static String[] methodNames = new String[]{
  "bubbleSort",
  "bubbleSortAdvanced",
  "bubbleSortAdvanced2",
  "selectSort",
  "insertSort",
  "insertSortAdvanced",
  "insertSortAdvanced2",
  "binaryTreeSort",
  "shellSort",
  "shellSortAdvanced",
  "shellSortAdvanced2",
  "mergeSort",
  "quickSort",
  "heapSort"
 };
    public static void main(String[] args) throws Exception{
     //correctnessTest();
     performanceTest(20000);
    }

    /**
     * 正確性測試<br>
     * 簡單地測試一下各個算法的正確性<br>
     * 只是為了方便觀測新添加的算法是否基本正確；<br>
     * @throws Exception 主要是反射相關(guān)的Exception；<br>
     */
    public static void correctnessTest() throws Exception{
     int len = 10;
     int[] a = new int[len];
     for(int i=0; i<methodNames.length; i++){
      for(int j=0; j<a.length; j++){
          a[j] = (int)Math.floor(Math.random()*len*2);
         }
      Method sortMethod = null;
      sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
      Object o = sortMethod.invoke(null, a);
      System.out.print(methodNames[i] + " : ");
      if(o==null){
       System.out.println(Arrays.toString(a));
      }
      else{
       //兼顧mergeSort，它的排序結(jié)果以返回值的形式出現(xiàn)；
       System.out.println(Arrays.toString((int[])o));
      }
     }
    }

    /**
     * 性能測試<br>
     * 數(shù)組長度用參數(shù)len傳入，每個方法跑20遍取耗時平均值；<br>
     * @param len 數(shù)組長度 建議取10000以上，否則有些算法會顯示耗時為0；<br>
     * @throws Exception 主要是反射相關(guān)的Exception；<br>
     */
    public static void performanceTest(int len) throws Exception{
     int[] a = new int[len];
     int times = 20;

     System.out.println("Array length: " + a.length);
     for(int i=0; i<methodNames.length; i++){
      Method sortMethod = null;
      sortMethod = SortUtil.class.getDeclaredMethod(methodNames[i], a.getClass());
      int totalTime = 0;
      for(int j=0; j<times; j++){
       for(int k=0; k<len; k++){
           a[k] = (int)Math.floor(Math.random()*20000);
          }
       long start = new Date().getTime();
       sortMethod.invoke(null, a);
       long end = new Date().getTime();
       totalTime +=(end-start);
      }
      System.out.println(methodNames[i] + " : " + (totalTime/times) + " ms");
      //System.out.println(Arrays.toString(a));
     }
    }

    /**
     * 最原始的冒泡交換排序;<br>
     * 兩層遍歷，外層控制掃描的次數(shù)，內(nèi)層控制比較的次數(shù)；<br>
     * 外層每掃描一次，就有一個最大的元素沉底；所以內(nèi)層的比較次數(shù)將逐漸減?。?lt;br>
     */
    public static void bubbleSort(int[] a){
        for(int i=0; i<a.length; i++){
            for(int j=0; j<a.length-i-1; j++){
                if(a[j]>a[j+1]){
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
    }

    /**
     * 改進(jìn)的冒泡法<br>
     * 改進(jìn)之處在于：設(shè)一個標(biāo)志位，如果某趟跑下來，沒有發(fā)生交換，說明已經(jīng)排好了；<br>
     */
    public static void bubbleSortAdvanced(int[] a){
        int k = a.length-1;
        boolean flag = true;
        while(flag){
            flag = false;
            for(int i=0;i<k;i++){
                if(a[i]>a[i+1]){
                    int tmp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = tmp;
                    //有交換則繼續(xù)保持標(biāo)志位；
                    flag = true;
                }
            }
            k--;
        }
    }

    /**
     * 改進(jìn)的冒泡法2<br>
     * 改進(jìn)之處在于吸收上面的思想(沒有交換意味著已經(jīng)有序)，如果局部的已經(jīng)是有序的，則后續(xù)的比較就不需要再比較他們了。<br>
     * 比如：3142 5678，假如剛剛做完了2和4交換之后，發(fā)現(xiàn)這趟比較后續(xù)再也沒有發(fā)生交換，則后續(xù)的比較只需要比到4即可；<br>
     * 該算法就是用一個標(biāo)志位記錄某趟最后發(fā)生比較的地點；<br>
     */
    public static void bubbleSortAdvanced2(int[] a){
        int flag = a.length - 1;
        int k;
        while(flag>0){
            k = flag;
            flag = 0;
            for(int i=0; i<k; i++){
                if(a[i] > a[i+1]){
                    int tmp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = tmp;
                    //有交換則記錄該趟最后發(fā)生比較的地點；
                    flag = i+1;
                }
            }
        }
    }

    /**
     * 插入排序
     *
     * 關(guān)于插入排序，這里有幾個約定，從而可以快速理解算法：<br>
     * i: 無序表遍歷下標(biāo)；i<n-1；<br>
     * j: 有序表遍歷下表；0<=j<i;<br>
     * a[i]:表示當(dāng)前被拿出來做插入排序的無序表頭元素；<br>
     * a[j]:有序表中的任意元素；<br>
     * <br>
     * 算法關(guān)鍵點：把數(shù)組分割為a[0~i-1]有序表，a[i~n-1]無序表；每次從無序表頭部取一個，<br>
     * 把它插入到有序表適當(dāng)?shù)奈恢茫钡綗o序表為空；<br>
     * 初始時，a[0]為有序表，a[1~n-1]為無序表；<br>
     */
    public static void insertSort(int[] a){
        //從無序表頭開始遍歷；
        for(int i=1; i<a.length; i++){
            int j;
            //拿a[i]和有序表元素依次比較，找到一個恰當(dāng)?shù)奈恢茫?BR>            for(j=i-1;j>=0; j--){
                if(a[j] < a[i]){
                    break;
                }
            }
            //如果找到恰當(dāng)?shù)奈恢?，則從該位置開始，把元素朝后移動一格，為插入的元素騰出空間；
            if(j!=(i-1)){
                int tmp = a[i];
                int k;
                for(k = i-1; k>j;k--){
                    a[k+1] = a[k];
                }
                a[k+1] = tmp;
            }
        }
    }

    /**
     * 改進(jìn)的插入排序1
     * 改進(jìn)的關(guān)鍵在于：首先拿無序表頭元素a[i]和有序表尾a[i-1]比較，
     * 如果a[i]<a[i-1],說明需要調(diào)整；調(diào)整的過程為：
     * 從有序表尾開始，把有序表里面比a[i]大的元素都朝后移動，直到找到恰當(dāng)?shù)奈恢茫?BR>     */
    public static void insertSortAdvanced(int[] a){
        //遍歷無序表；
        for(int i=1; i<a.length; i++){
            //如果無序表頭元素小于有序表尾，說明需要調(diào)整；
            if(a[i]<a[i-1]){
                int tmp = a[i];
                int j;
                //從有序表尾朝前搜索并比較，并把大于a[i]的元素朝后移動以騰出空間；
                for(j=i-1; j>=0&&a[j]>tmp;j--){
                    a[j+1] = a[j];
                }
                a[j+1] = tmp;
            }
        }
    }

    /**
     * 改進(jìn)的插入排序2
     * 總體思想和上面相似，拿無序表頭元素從有序表尾元素開始朝前比較，
     * 如果a[i]比a[i-1]小，則把a[i]從有序表尾用冒泡交換的方式朝前移動，直到到達(dá)恰當(dāng)?shù)奈恢茫?BR>     */
    public static void insertSortAdvanced2(int[] a){
        //遍歷無序表
        for(int i=1; i<a.length; i++){
            //拿a[i]從有序表尾開始冒泡；
            for(int j=i-1; j>=0 && a[j] > a[j+1]; j--){//a[j+1]就是a[i]
                int tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
            }
        }
    }

    /**
     * 快速排序<br>
     * 算法的思想在于分而治之:先找一個元素(一般來說都是數(shù)組頭元素),把比它大的都放到右邊,把比它小的都放到左邊;<br>
     * 然后再按照這樣的思想去處理兩個子數(shù)組; 下面說的子數(shù)組頭元素通指用來劃分?jǐn)?shù)組的元素;<br>
     * <br>
     * 下面程序關(guān)鍵點就在于!forward, low0++, high0--這些運算; 這三個運算使得a[low0],a[high0]里面總有一個指向子數(shù)組頭元素; <br>  
     * 可以用極端的情況來方便理解這三個值的運作: <br>
     * 假如我的數(shù)列為0123456789, 初始時forward=false,0作為子數(shù)組劃分依據(jù),很顯然第一輪的時候不會發(fā)生任何交換,low0一直指向0,<br>
     * high0逐漸下降直到它指向0為止; 同理可思考9876543210這個例子;<br>
     * <br>
     * @param a 待排序數(shù)組<br>
     * @param low 子數(shù)組開始的下標(biāo);<br>
     * @param high 子數(shù)組結(jié)束的下標(biāo);<br>
     */
    public static void quickSort(int[] a, int low, int high){
        if(low>=high){
            return;
        }
        int low0 = low;
        int high0 = high;
        boolean forward = false;
        while(low0!=high0){
            if(a[low0]>a[high0]){
                int tmp = a[low0];
                a[low0] = a[high0];
                a[high0] = tmp;
                forward = !forward;
            }
            if(forward){
                low0++;
            }
            else{
                high0--;
            }
        }
        low0--;
        high0++;
        quickSort(a, low, low0);
        quickSort(a, high0, high);
    }

    /**
     * 快速排序的簡單調(diào)用形式<br>
     * 方便測試和調(diào)用<br>
     * @param a
     */
    public static void quickSort(int[] a){
     quickSort(a, 0, a.length-1);
    }

    /**
     * 歸并排序<br>
     * 所謂歸并，就是合并兩個有序數(shù)組；歸并排序也用了分而治之的思想，把一個數(shù)組分為若干個子數(shù)組；<br>
     * 當(dāng)子數(shù)組的長度為1的時候，則子數(shù)組是有序的，于是就可以兩兩歸并了；<br>
     * <br>
     * 由于歸并排序需要分配空間來轉(zhuǎn)儲歸并的結(jié)果，為了算法上的方便，歸并算法的結(jié)果以返回值的形式出現(xiàn)；<br>
     */

    /**
     * 合并兩個有序數(shù)組
     * @param a 有序數(shù)組1
     * @param b 有序數(shù)組2
     * @return 合并之后的有序數(shù)組；
     */
    public static int[] merge(int[] a, int[] b){
     int result[] = new int[a.length+b.length];
     int i=0,j=0,k=0;
     while(i<a.length&&j<b.length){
      if(a[i]<b[j]){
       result[k++] = a[i];
       i++;
      }
      else{
       result[k++] = b[j];
       j++;
      }
     }
     while(i<a.length){
      result[k++] = a[i++];
     }
     while(j<b.length){
      result[k++] = b[j++];
     }
     return result;
    }

    /**
     * 歸并排序<br>
     * 把數(shù)組從中間一分為二，并對左右兩部分遞歸調(diào)用，直到數(shù)組長度為1的時候，開始兩兩歸并；<br>
     * @param 待排序數(shù)組；
     * @return 有序數(shù)組；
     */
    public static int[] mergeSort(int[] a){
     if(a.length==1){
      return a;
     }
     int mid = a.length/2;
     int[] leftPart = new int[mid];
     int[] rightPart = new int[a.length-mid];
     System.arraycopy(a, 0, leftPart, 0, leftPart.length);
     System.arraycopy(a, mid, rightPart, 0, rightPart.length);
     leftPart = mergeSort(leftPart);
     rightPart = mergeSort(rightPart);
     return merge(leftPart, rightPart);
    }

    /**
     * 選擇排序<br>
     * 和插入排序類似，它也把數(shù)組分割為有序區(qū)和無序區(qū)，所不同的是：<br>
     * 插入排序是拿無序區(qū)的首元素插入到有序區(qū)適當(dāng)?shù)奈恢茫?lt;br>
     * 選擇排序是從無序區(qū)中挑選最小的放到有序區(qū)最后；<br>
     * <br>
     * 兩層循環(huán)，外層控制有序區(qū)的隊尾，內(nèi)層用來查找無序區(qū)最小元素；<br>
     * @param a
     */
    public static void selectSort(int[] a){
     for(int i=0; i<a.length; i++){
      int minIndex = i;
      for(int j=i+1; j<a.length; j++){
       if(a[j]<a[minIndex]){
        minIndex = j;
       }
      }
      int tmp = a[i];
      a[i] = a[minIndex];
      a[minIndex]= tmp;
     }
    }

    /**
     * 希爾排序<br>
     * 其思想是把數(shù)組按等步長(/間距)劃分為多個子序列，對各個子序列做普通的插入排序，<br>逐次降低步長，直到為1的時候最后再做一次普通的插入排序；
     * 用一個極端的例子作比方，我有數(shù)列如下：<br>
     * [1,2,3,4,5,6,7,8,9,10];<br>
     * 初始的時候，步長gap=5；則劃分的子數(shù)組為[1,6], [2,7], [3,8], [4,9], [5,10];<br>對他們分別排序(當(dāng)然由于本數(shù)組特殊，所以結(jié)果是不變的)；<br>
     * 然后gap=2=5/2; 子數(shù)組為[1,3,5,7,9], [2,4,6,8,10]; <br>
     * 最后gap=1=2/2; 做一次全局排序；<br>
     * <br>
     * 希爾排序克服了插入/冒泡排序的弱點(一次只能把元素移動一個相鄰的位置), <br>依靠大步長，可以把元素盡快移動到目標(biāo)位置(或附近);<br>
     * 希爾排序?qū)嶋H上是插入排序的變種。它適用于：當(dāng)數(shù)組總體有序，個別需要調(diào)整的情況；這時候利用插入排序的優(yōu)勢，可以達(dá)到O(n)的效率；<br>
     * 影響希爾算法的一個重要的因素是步長選擇，一個好步長的優(yōu)點是：后面的短步長排序不會破壞前面的長步長排序；<br>
     * 怎么理解這種破壞呢？前面的長步長把一個較小的數(shù)移到了左面，但是在縮小步長之后有可能又被交換到了右面 (因為它被分到了一個有很多比它更小的組)；<br>
     * 關(guān)于步長，可以查看http://zh.wikipedia.org上面關(guān)于希爾排序的頁面；<br>
     * 下面的程序是希爾排序最基礎(chǔ)的寫法，適合用來理解希爾排序思想；<br>
     */
    public static void shellSort(int[] a){
     // 控制間距；間距逐漸減小，直到為1；
     for(int gap = a.length/2; gap>0; gap/=2){
      // 掃描每個子數(shù)組
      for(int i=0; i<gap; i++){
       // 對每個字?jǐn)?shù)組，掃描無序區(qū)；注意增量；
       // a[i]是初始有序區(qū)；
       for(int j=i+gap; j<a.length; j+=gap){
        // 無序區(qū)首元素小于有序區(qū)尾元素，說明需要調(diào)整
        if(a[j]<a[j-gap]){
         int tmp = a[j];
         int k = j-gap;
         //從有序區(qū)尾向前搜索查找適當(dāng)?shù)奈恢茫?BR>         while(k>=0&&a[k]>tmp){
          a[k+gap] = a[k];
          k-=gap;
         }
         a[k+gap] = tmp;
        }
       }
      }
     }
    }

    /**
     * 改進(jìn)的希爾排序<br>
     * 改進(jìn)之處在于：上面的寫法用一個for循環(huán)來區(qū)別對待每個字?jǐn)?shù)組；而實際上是不必要的；<br>
     * a[0,1,...gap-1]作為所有子數(shù)組的有序區(qū)，a[gap,...n-1]作為所有字?jǐn)?shù)組的無序區(qū)；<br>
     * <br>
     * 該改進(jìn)在時間效率上沒有改進(jìn)；只是讓程序看起來更簡潔；<br>
     * @param a
     */
    public static void shellSortAdvanced(int[] a){
     // 控制步長
     for(int gap = a.length/2; gap>0; gap/=2){
      // 從無序區(qū)開始處理，把多個子數(shù)組放在一起處理；
      for(int j=gap; j<a.length; j++){
       // 下面的邏輯和上面是一樣的；
       if(a[j]<a[j-gap]){
        int tmp = a[j];
        int k = j-gap;
        while(k>=0&&a[k]>tmp){
         a[k+gap] = a[k];
         k-=gap;
        }
        a[k+gap] = tmp;
       }
      }
     }
    }

    /**
     * 改進(jìn)的希爾排序2<br>
     * 在吸收shellSortAdvanced思想的基礎(chǔ)上，采用insertAdvanced2的做法；<br>即無序區(qū)首元素通過朝前冒泡的形式移動的適當(dāng)?shù)奈恢茫?lt;br>
     * @param a
     */
    public static void shellSortAdvanced2(int[] a){
     for(int gap = a.length/2; gap>0; gap/=2){
      for(int i=gap; i<a.length; i++){
       if(a[i]<a[i-gap]){
        for(int j=i-gap; j>=0&&a[j+gap]>a[j]; j-=gap){
         int tmp = a[j];
         a[j] = a[j+gap];
         a[j+gap] = tmp;
        }
       }
      }
     }
    }

    /**
     * 堆排序<br>
     * 堆的定義：堆是一個完全，或近似完全的二叉樹，堆頂元素的值大于左右孩子的值，左右孩子也需要滿足這個條件；<br>
     * 按照堆的定義，堆可以是大頂堆(maxHeap)，或小頂堆(minHeap)；<br>
     * 一般用數(shù)組即可模擬二叉樹，對于任意元素i，左孩子為2*i+1,右孩子為2*i+2;父節(jié)點為(i-1)/2;
     * @param a
     */
    public static void heapSort(int[] a){

     // 先從最后一個非葉子節(jié)點往上調(diào)整，使?jié)M足堆結(jié)構(gòu)；
     for(int i=(a.length-2)/2; i>=0; i--){
      maxHeapAdjust(a, i, a.length);
     }
     // 每次拿最后一個節(jié)點和第一個交換，然后調(diào)整堆；直到堆頂；
     for(int i=a.length-1; i>0; i--){
      int tmp = a[i]; a[i] = a[0]; a[0] = tmp;
      maxHeapAdjust(a, 0, i);
     }
    }

    /**
     * 調(diào)整堆<br>
     * 把以i為跟節(jié)點的二叉樹調(diào)整為堆；<br>
     * 可以這么來思考這個過程：這個完全二叉樹就像一個金字塔，塔頂?shù)男≡匮刂鴺浣Y(jié)構(gòu)，往下沉降；<br>
     * 調(diào)整的結(jié)果是最大的元素在金字塔頂，然后把它從堆中刪除(把它交換到堆尾，然后堆收縮一格)；<br>
     * 堆排序快的原因就是根據(jù)二叉樹的特點，一個節(jié)點要沉降到合適的位置，只需要logn步；同時前期調(diào)整的結(jié)果(大小順序)會被記錄下來，從而加快后續(xù)的調(diào)整；<br>
     * @param a 待排數(shù)組
     * @param i 堆頂
     * @param len 堆長度
     */
    public static void maxHeapAdjust(int[] a, int i, int len){
     int tmp = a[i];
     // j是左孩子節(jié)點
     int j = i*2+1;
     //
     while(j<len){
      // 從左右孩子中挑選大的
      // j+1是右孩子節(jié)點
      if((j+1)<len && a[j+1]>a[j]){
       j++;
      }
      // 找到恰當(dāng)?shù)奈恢镁筒辉僬?BR>      if(a[j]<tmp){
       break;
      }
      // 否則把較大者沿著樹往上移動；
      a[i] = a[j];
      // i指向剛才的較大的孩子；
      i = j;
      // j指向新的左孩子節(jié)點；
      j = 2*i + 1;
     }
     // 把要調(diào)整的節(jié)點值下沉到適當(dāng)?shù)奈恢茫?BR>     a[i] = tmp;
    }

    /**
     * 二叉樹排序<br>
     * 二叉樹的定義是嵌套的：<br>節(jié)點的值大于左葉子節(jié)點的值，小于右葉子節(jié)點的值；葉子節(jié)點同樣滿足這個要求；<br>
     * 二叉樹的構(gòu)造過程就是排序的過程：<br>
     * 先構(gòu)造跟節(jié)點，然后調(diào)用add方法添加后續(xù)節(jié)點為跟節(jié)點的子孫節(jié)點；這個過程也是嵌套的;<br>
     * <br>
     * 中序遍歷二叉樹即得到有序結(jié)果；<br>
     * 二叉樹排序用法特殊，使用情形要視情況而定；<br>
     * @param a
     */
    public static void binaryTreeSort(int[] a){
     // 構(gòu)造一個二叉樹節(jié)點內(nèi)部類來實現(xiàn)二叉樹排序算法；
     class BinaryNode{
      int value;
      BinaryNode left;
      BinaryNode right;

      public BinaryNode(int value){
       this.value = value;
       this.left = null;
       this.right = null;
      }

      public void add(int value){
       if(value>this.value){
        if(this.right!=null){
         this.right.add(value);
        }
        else{
         this.right = new BinaryNode(value);
        }
       }
       else{
        if(this.left!=null){
         this.left.add(value);
        }
        else{
         this.left = new BinaryNode(value);
        }
       }
      }
      /**
       * 按中序遍歷二叉樹，就是有序的。
       */
      public void iterate(){
       if(this.left!=null){
        this.left.iterate();
       }
       // 在測試的時候要把輸出關(guān)掉，以免影響性能；
       // System.out.print(value + ", ");
       if(this.right!=null){
        this.right.iterate();
       }
      }
     }

     BinaryNode root = new BinaryNode(a[0]);
     for(int i=1; i<a.length; i++){
      root.add(a[i]);
     }
     root.iterate();
    }
}