/*************幾種常見的排序算法總結(jié)***************************/            package paixu;            public class PaiXu {         final int MAX=20;         int num[]=new int[MAX];         {             System.out.PRint("生成的隨機(jī)數(shù)組是：");             for(int i=0;i<20;i++){                 num[i]=(int)(Math.random()*100);                 System.out.print(num[i]+" ");             }             System.out.println();         }                  int num2[]=new int[MAX]; //只用于合并排序法中         {             System.out.print("合并排序法需要使用的數(shù)組2是：");             for(int i=0;i<20;i++){                 num2[i]=(int)(Math.random()*100);                 System.out.print(num2[i]+" ");             }             System.out.println();         }                  int num3[]=new int[MAX+MAX]; //用于存放合并排序法中被合并排序好的數(shù)組                           public PaiXu(){             selsort(num.clone());                        //選擇排序法             insort(num.clone());                         //插入排序法             bubsort(num.clone());                        //冒泡排序法             shellsort(num.clone());                      //希爾排序法             shakersort(num.clone());                     //shake排序法             heapsort(num.clone());                       //堆排序             quicksort_one(num.clone());                  //快速排序法（一）               quicksort_two(num.clone());                  //快速排序法（二）             quicksort_three(num.clone());                //快速排序法（三）             mergesort(num.clone(),num2.clone(),num3);    //合并排序法             basesort(num.clone());                       //基數(shù)排序法         }                 /*----------------------------選擇排序法-------------------------------------------               將要排序的對象分作兩部份，一個(gè)是已排序的，一個(gè)是未排序的，從后端未排序部份選擇一個(gè)最小值，并放入前端已排序部份的最后一個(gè)。        -------------------------------------------------------------------------------*/         public void selsort(int number[]) {              int i, j, k, m, temp;              long start,end;                            start=System.nanoTime();              for(i = 0; i < MAX-1; i++) {                  m = i;                  for(j = i+1; j < MAX; j++){                      if(number[j] < number[m]){                       m = j;                      }                  }                  if( i != m){                      temp=number[i];                      number[i]=number[m];                      number[m]=temp;                  }              }              end=System.nanoTime();                            System.out.println("-----------------選擇排序法------------------");              System.out.print("排序后是:");              for(i=0;i<=MAX-1;i++){                  System.out.print(number[i]+" ");              }              System.out.println();              System.out.println("排序使用時(shí)間："+(end-start)+" ns");          }                                    /*-------------------------插入排序法--------------------------------                 像是玩樸克一樣，我們將牌分作兩堆，每次從后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的適當(dāng)位置        -----------------------------------------------------------------*/         public void insort(int number[]){              int i, j, k, temp;              long start,end;                            start=System.nanoTime();              for(j = 1; j < MAX; j++) {                  temp = number[j];                  i = j - 1;                  while(temp < number[i]) {                      number[i+1] = number[i];                      i--;                      if(i == -1){                          break;                      }                  }              number[i+1] = temp;              }              end=System.nanoTime();                            System.out.println("-----------------插入排序法------------------");              System.out.print("排序后是:");              for(i=0;i<=MAX-1;i++){                  System.out.print(number[i]+" ");              }              System.out.println();              System.out.println("排序使用時(shí)間："+(end-start)+" ns");         }                           /*-----------------------------------------冒泡排序法----------------------------------------                        顧名思義，就是排序時(shí)，最大的元素會如同氣泡一樣移至右端，其利用比較相鄰元素的方法，將大的元素交換至右端，               所以大的元素會不斷的往右移動，直到適當(dāng)?shù)奈恢脼橹埂?                      基本的氣泡排序法可以利用旗標(biāo)的方式稍微減少一些比較的時(shí)間，當(dāng)尋訪完陣列后都沒有發(fā)生任何的交換動作，              表示排序已經(jīng)完成，而無需再進(jìn)行之后的回圈比較與交換動作。        ----------------------------------------------------------------------------------------*/         public void bubsort(int number[]){              int i, j, k, temp, flag = 1;              long start,end;                            start=System.nanoTime();              for(i = 0; i < MAX-1 && flag == 1; i++) {                  flag = 0;                  for(j = 0; j < MAX-i-1; j++) {                      if(number[j+1] < number[j]) {                          temp=number[j+1];                          number[j+1]=number[j];                          number[j]=temp;                          flag = 1;                      }                  }              }              end=System.nanoTime();                            System.out.println("-----------------冒泡排序法------------------");              System.out.print("排序后是:");              for(i=0;i<=MAX-1;i++){                  System.out.print(number[i]+" ");              }              System.out.println();              System.out.println("排序使用時(shí)間："+(end-start)+" ns");         }                                    /*--------------------------shell（希爾）排序法----------------------------         Shell首先將間隔設(shè)定為n/2，然后跳躍進(jìn)行插入排序，再來將間隔n/4，跳躍進(jìn)行排序動作，再來         間隔設(shè)定為n/8、n/16，直到間隔為1之后的最后一次排序終止，由于上一次的排序動作都會將         固定間隔內(nèi)的元素排序好，所以當(dāng)間隔越來越小時(shí)，某些元素位于正確位置的機(jī)率越高，因此         最后幾次的排序動作將可以大幅減低。         ---------------------------------------------------------------------*/         public void shellsort(int number[]) {              int i, j, k, gap, temp;              long start,end;                            start=System.nanoTime();              gap = MAX / 2;              while(gap > 0) {                  for(k = 0; k < gap; k++) {                      for(i = k+gap; i < MAX; i+=gap) {                          for(j = i - gap; j >= k; j-=gap) {                              if(number[j] > number[j+gap]) {                                  temp=number[j];                                  number[j]=number[j+gap];                                  number[j+gap]=temp;                              }else{                                  break;                              }                          }                      }                  }                  gap /= 2;              }              end=System.nanoTime();                            System.out.println("-----------------shell(希爾)排序法（改進(jìn)的插入排序法）------------------");              System.out.print("排序后是:");              for(i=0;i<=MAX-1;i++){                  System.out.print(number[i]+" ");              }              System.out.println();              System.out.println("排序使用時(shí)間："+(end-start)+" ns");         }                                    /*---------------------Shake排序法（改良的冒泡排序法）--------------------------                   方法就在于氣泡排序的雙向進(jìn)行，先讓氣泡排序由左向右進(jìn)行，再來讓氣泡排序由右往左進(jìn)行，                   如此完成一次排序的動作，而您必須使用left與right兩個(gè)旗標(biāo)來記錄左右兩端已排序的元素位置。          --------------------------------------------------------------------*/         public void shakersort(int number[]) {               int i, temp, left = 0, right = MAX - 1, shift = 0;               long start,end;                            start=System.nanoTime();              while(left < right) {                   // 向右進(jìn)行氣泡排序                   for(i = left; i < right; i++) {                       if(number[i] > number[i+1]) {                           temp=number[i];                          number[i]=number[i+1];                          number[i+1]=temp;                          shift = i;                       }                   }                   right = shift;                              // 向左進(jìn)行氣泡排序                   for(i = right; i > left; i--) {                       if(number[i] < number[i-1]) {                           temp=number[i];                          number[i]=number[i-1];                          number[i-1]=temp;                           shift = i;                       }                   }                   left = shift;               }              end=System.nanoTime();                            System.out.println("-----------------shake排序法（改進(jìn)的冒泡排序法）------------------");              System.out.print("排序后是:");              for(i=0;i<=MAX-1;i++){                  System.out.print(number[i]+" ");              }              System.out.println();              System.out.println("排序使用時(shí)間："+(end-start)+" ns");          }                                              /*-----------------------heap排序（堆排序法--改進(jìn)的選擇排序）----------------------------                利用堆積樹的原理，先構(gòu)造一個(gè)堆積樹（看堆積樹的定義，筆記本上有），然后將根節(jié)點(diǎn)與最后的葉子節(jié)點(diǎn)交換，并屏蔽掉最后一個(gè)葉子節(jié)點(diǎn)，                然后再將未被屏蔽的部分重新構(gòu)造堆積樹，然后再重復(fù)上面的步驟，直到所有的數(shù)被按順序排好。         --------------------------------------------------------------------------------*/         public void heapsort(int number[]) {             int i, m, p, s, temp;             long start,end;                          start=System.nanoTime();             int number_temp[]=new int[MAX+1];             for(int temp_i=1;temp_i<MAX+1;temp_i++){                 number_temp[temp_i]=number[temp_i-1];             }             createheap(number_temp);             m = MAX;             while(m > 1) {                 temp=number_temp[1];                 number_temp[1]=number_temp[m];                 number_temp[m]=temp;                 m--;                 p = 1;                 s = 2 * p;                 while(s <= m) {                     if(s < m && number_temp[s+1] > number_temp[s])                         s++;                     if(number_temp[p] >= number_temp[s])                         break;                     temp=number_temp[p];                     number_temp[p]=number_temp[s];                     number_temp[s]=temp;                     p = s;                     s = 2 * p;                 }             }             for(int temp_j=1;temp_j<MAX+1;temp_j++){                 number[temp_j-1]=number_temp[temp_j];             }             end=System.nanoTime();                                        System.out.println("-----------------heap排序（堆排序法--改進(jìn)的選擇排序）------------------");              System.out.print("排序后是:");              for(i=0;i<=MAX-1;i++){                  System.out.print(number[i]+" ");              }              System.out.println();              System.out.println("排序使用時(shí)間："+(end-start)+" ns");         }                  //將原數(shù)組構(gòu)造為從下標(biāo)1開始的一個(gè)新數(shù)組，便于處理，同時(shí)將這個(gè)新數(shù)組構(gòu)造為最初始的堆積樹結(jié)構(gòu)         public void createheap(int number[]) {             int i, s, p, temp;             int heap[] = new int[MAX+1];             for(i = 1; i <= MAX; i++) {                 heap[i] = number[i];                 s = i;                 p = i / 2;                 while(s >= 2 && heap[p] < heap[s]) {                     temp=heap[p];                     heap[p]=heap[s];                     heap[s]=temp;                     s = p;                     p = s / 2;                 }             }             for(i = 1; i <= MAX; i++){                number[i] = heap[i];              }         }                                                               /*-----------------------快速排序法（一）---------------------------------------------         這邊所介紹的快速演算如下：將最左邊的數(shù)設(shè)定為軸，并記錄其值為s         廻圈處理：         令索引i 從數(shù)列左方往右方找，直到找到大于s 的數(shù)         令索引j 從數(shù)列左右方往左方找，直到找到小于s 的數(shù)         如果i >= j，則離開回圈         如果i < j，則交換索引i與j兩處的值         將左側(cè)的軸與j 進(jìn)行交換         對軸左邊進(jìn)行遞回         對軸右邊進(jìn)行遞回           --------------------------------------------------------------------------------*/         public void quicksort_one(int number[]){             long start,end;                          start=System.nanoTime();             quicksort_1(number,0,MAX-1);             end=System.nanoTime();                           System.out.println("-----------------快速排序法（ 一 ）------------------");              System.out.print("排序后是:");              for(int i=0;i<=MAX-1;i++){                  System.out.print(number[i]+" ");              }              System.out.println();              System.out.println("排序使用時(shí)間："+(end-start)+" ns");                                   }                           public void quicksort_1(int number[],int left,int right) {             int i, j, s, temp;             if(left < right) {                 s = number[left];                 i = left;                 j = right + 1;                 while(true) {                     // 向右找                     while(i + 1 < number.length && number[++i] < s) ;                     // 向左找                     while(j -1 > -1 && number[--j] > s) ;                     if(i >= j)                         break;                     temp=number[i];                     number[i]=number[j];                     number[j]=temp;                 }             number[left] = number[j];             number[j] = s;             quicksort_1(number, left, j-1); // 對左邊進(jìn)行遞回             quicksort_1(number, j+1, right); // 對右邊進(jìn)行遞回             }         }                                    /*-----------------------快速排序法（二）---------------------------------------------         在這個(gè)例子中，取中間的元素s作比較，同樣的先得右找比s大的索引i，然后找比s小的         索引j，只要兩邊的索引還沒有交會，就交換i 與j 的元素值，這次不用再進(jìn)行軸的交換了，         因?yàn)樵趯ふ医粨Q的過程中，軸位置的元素也會參與交換的動作，例如：         41 24 76 11 45 64 21 69 19 36         首先left為0，right為9，(left+right)/2 = 4（取整數(shù)的商），所以軸為索引4的位置，比較的元素是         45，您往右找比45大的，往左找比45小的進(jìn)行交換：         41 24 76* 11 [45] 64 21 69 19 *36         41 24 36 11 45* 64 21 69 19* 76         41 24 36 11 19 64* 21* 69 45 76        [41 24 36 11 19 21] [64 69 45 76]         完成以上之后，再初別對左邊括號與右邊括號的部份進(jìn)行遞回，如此就可以完成排序的目的。        --------------------------------------------------------------------------------*/         public void quicksort_two(int number[]){             long start,end;                          start=System.nanoTime();             quicksort_2(number,0,MAX-1);             end=System.nanoTime();                           System.out.println("-----------------快速排序法（ 二 ）------------------");              System.out.print("排序后是:");              for(int i=0;i<=MAX-1;i++){                  System.out.print(number[i]+" ");              }              System.out.println();              System.out.println("排序使用時(shí)間："+(end-start)+" ns");         }                           public void quicksort_2(int number[], int left, int right) {             int i, j, s, temp;             if(left < right) {                 s = number[(left+right)/2];                 i = left - 1;                 j = right + 1;                 while(true) {                     while(number[++i] < s) ; // 向右找                     while(number[--j] > s) ; // 向左找                     if(i >= j)                         break;                     temp=number[i];                     number[i]=number[j];                     number[j]=temp;                 }             quicksort_2(number, left, i-1); // 對左邊進(jìn)行遞回             quicksort_2(number, j+1, right); // 對右邊進(jìn)行遞回             }         }                                             /*-----------------------快速排序法（三）---------------------------------------------                 先說明這個(gè)快速排序法的概念，它以最右邊的值s作比較的標(biāo)準(zhǔn)，將整個(gè)數(shù)列分為三個(gè)部份，         一個(gè)是小于s的部份，一個(gè)是大于s的部份，一個(gè)是未處理的部份，如下所示：                 i           j         --------|-----------|----------|s             小于s     大于s         未處理         在排序的過程中，i 與j 都會不斷的往右進(jìn)行比較與交換，最后數(shù)列會變?yōu)橐韵碌臓顟B(tài)：         -------------|-----------------|s             小于s             大于s         然后將s的值置于中間，接下來就以相同的步驟會左右兩邊的數(shù)列進(jìn)行排序的動作，如下所示：         -------------|s|---------------             小于s             大于s         然后采用遞歸的方法重復(fù)上面的步驟，就可以實(shí)現(xiàn)排序了。        --------------------------------------------------------------------------------*/         public void quicksort_three(int number[]){             long start,end;                          start=System.nanoTime();             quicksort_3(number,0,MAX-1);             end=System.nanoTime();                           System.out.println("-----------------快速排序法（ 三 ）------------------");              System.out.print("排序后是:");              for(int i=0;i<=MAX-1;i++){                  System.out.print(number[i]+" ");              }              System.out.println();              System.out.println("排序使用時(shí)間："+(end-start)+" ns");                      }                           public int partition(int number[], int left, int right) {             int i, j, s, temp;             s = number[right];             i = left - 1;             for(j = left; j < right; j++) {                 if(number[j] <= s) {                     i++;                     temp=number[i];                     number[i]=number[j];                     number[j]=temp;                 }             }             temp=number[i+1];             number[i+1]=number[right];             number[right]=temp;             return i+1;         }                  public void quicksort_3(int number[], int left, int right) {             int q;             if(left < right) {                 q = partition(number, left, right);                 quicksort_3(number, left, q-1);                 quicksort_3(number, q+1, right);             }         }                                                      /*-----------------------合并排序法---------------------------------------------                  合并排序法基本是將兩筆已排序的資料合并并進(jìn)行排序，如果所讀入的資料尚未排序，                  可以先利用其它的排序方式來處理這兩筆資料，然后再將排序好的這兩筆資料合并。                  合并排序法中用到了  快速排序法（三）        --------------------------------------------------------------------------------*/                  public void mergesort(int number1[],int number2[],int number3[]){             long start,end;                          start=System.nanoTime();             quicksort_3(number1,0,MAX-1);             quicksort_3(number2,0,MAX-1);             mergesort_merge(number1,MAX,number2,MAX,number3);             end=System.nanoTime();                          System.out.println("-----------------合并排序法------------------");             System.out.print("排序后是:");             for(int i=0;i<=MAX+MAX-1;i++){                  System.out.print(number3[i]+" ");             }             System.out.println();             System.out.println("排序使用時(shí)間："+(end-start)+" ns");            }                           public void mergesort_merge(int number1[], int M, int number2[], int N, int number3[]) {             int i = 0, j = 0, k = 0;             while(i < M && j < N) {                 if(number1[i] <= number2[j]){                     number3[k++] = number1[i++];                 }else{                     number3[k++] = number2[j++];                 }                }             while(i < M){                 number3[k++] = number1[i++];             }               while(j < N){                 number3[k++] = number2[j++];             }         }                                             /*-----------------------基數(shù)排序法---------------------------------------------                 基數(shù)排序的方式可以采用LSD（Least sgnificant digital）或MSD（Most sgnificant digital），         LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。         以LSD為例，假設(shè)原來有一串?dāng)?shù)值如下所示：         73, 22, 93, 43, 55, 14, 28, 65, 39, 81         首先根據(jù)個(gè)位數(shù)的數(shù)值，在走訪數(shù)值時(shí)將它們分配至編號0到9的桶子中：         0   1   2   3   4   5   6   7   8   9             81              65              39                     43  14  55          28                     93                 22  73         接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：         81, 22, 73, 93, 43, 14, 55, 65, 28, 39         接著再進(jìn)行一次分配，這次是根據(jù)十位數(shù)來分配：         接下來將這些桶子中的數(shù)值重新串接起來，成為以下的數(shù)列：         0   1   2   3   4   5   6   7   8   9                 28  39             14  22      43  55  65  73  81  93         14, 22, 28, 39, 43, 55, 65, 73, 81, 93         這時(shí)候整個(gè)數(shù)列已經(jīng)排序完畢；如果排序的對象有三位數(shù)以上，則持續(xù)進(jìn)行以上的動作直至最         高位數(shù)為止。         LSD的基數(shù)排序適用于位數(shù)小的數(shù)列，如果位數(shù)多的話，使用MSD的效率會比較好，MSD的方         式恰與LSD相反，是由高位數(shù)為基底開始進(jìn)行分配，其他的演算方式則都相同。              --------------------------------------------------------------------------------*/         public void basesort(int number[]){             int temp[][] = new int[MAX][MAX];             int order[] = new int[MAX];             int i, j, k, n, lsd;             long start,end;             k = 0;             n = 1;                                       start=System.nanoTime();             while(n <= 10) {                 for(i = 0; i < MAX; i++) {                     lsd = ((number[i] / n) % 10);                     temp[lsd][order[lsd]] = number[i];                     order[lsd]++;                 }                 //重新排列                 for(i = 0; i < MAX; i++) {                     if(order[i] != 0)                         for(j = 0; j < order[i]; j++) {                             number[k] = temp[i][j];                             k++;                         }                     order[i] = 0;                 }                 n *= 10;                 k = 0;              }             end=System.nanoTime();                          System.out.println("-----------------基數(shù)排序法------------------");             System.out.print("排序后是:");             for(int ii=0;ii<=MAX-1;ii++){                  System.out.print(number[ii]+" ");             }             System.out.println();             System.out.println("排序使用時(shí)間："+(end-start)+" ns");         }                        public static void main(String[] args){             System.out.println("以下的測試時(shí)間僅供參考...");             new PaiXu();         }               }  
以上代碼的運(yùn)行結(jié)果如下所示
    以下的測試時(shí)間僅供參考...      生成的隨機(jī)數(shù)組是：53 82 61 70 75 31 30 68 22 56 48 23 12 74 13 85 69 62 21 55       合并排序法需要使用的數(shù)組2是：2 12 48 18 93 13 98 87 55 77 89 56 6 31 56 38 59 76 90 30       -----------------選擇排序法------------------      排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85       排序使用時(shí)間：7815 ns      -----------------插入排序法------------------      排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85       排序使用時(shí)間：7475 ns      -----------------冒泡排序法------------------      排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85       排序使用時(shí)間：18008 ns      -----------------shell(希爾)排序法（改進(jìn)的插入排序法）------------------      排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85       排序使用時(shí)間：11212 ns      -----------------shake排序法（改進(jìn)的冒泡排序法）------------------      排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85       排序使用時(shí)間：14610 ns      -----------------heap排序（堆排序法--改進(jìn)的選擇排序）------------------      排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85       排序使用時(shí)間：15969 ns      -----------------快速排序法（ 一 ）------------------      排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85       排序使用時(shí)間：8834 ns      -----------------快速排序法（ 二 ）------------------      排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85       排序使用時(shí)間：9853 ns      -----------------快速排序法（ 三 ）------------------      排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85       排序使用時(shí)間：10533 ns      -----------------合并排序法------------------      排序后是:2 6 12 12 13 13 18 21 22 23 30 30 31 31 38 48 48 53 55 55 56 56 56 59 61 62 68 69 70 74 75 76 77 82 85 87 89 90 93 98       排序使用時(shí)間：20387 ns      -----------------基數(shù)排序法------------------      排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85       排序使用時(shí)間：8495 ns  再次申明，以上的測試時(shí)間僅供參考，在項(xiàng)目中需要使用什么排序算法要根據(jù)實(shí)際情況來確定。