/*************幾種常見的排序算法總結***************************/ package paixu; public class PaiXu { final int MAX=20; int num[]=new int[MAX]; { System.out.PRint("生成的隨機數組是："); 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("合并排序法需要使用的數組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]; //用于存放合并排序法中被合并排序好的數組 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()); //基數排序法 } /*----------------------------選擇排序法------------------------------------------- 將要排序的對象分作兩部份，一個是已排序的，一個是未排序的，從后端未排序部份選擇一個最小值，并放入前端已排序部份的最后一個。 -------------------------------------------------------------------------------*/ 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("排序使用時間："+(end-start)+" ns"); } /*-------------------------插入排序法-------------------------------- 像是玩樸克一樣，我們將牌分作兩堆，每次從后面一堆的牌抽出最前端的牌，然后插入前面一堆牌的適當位置 -----------------------------------------------------------------*/ 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("排序使用時間："+(end-start)+" ns"); } /*-----------------------------------------冒泡排序法---------------------------------------- 顧名思義，就是排序時，最大的元素會如同氣泡一樣移至右端，其利用比較相鄰元素的方法，將大的元素交換至右端， 所以大的元素會不斷的往右移動，直到適當的位置為止。 基本的氣泡排序法可以利用旗標的方式稍微減少一些比較的時間，當尋訪完陣列后都沒有發生任何的交換動作， 表示排序已經完成，而無需再進行之后的回圈比較與交換動作。 ----------------------------------------------------------------------------------------*/ 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("排序使用時間："+(end-start)+" ns"); } /*--------------------------shell（希爾）排序法---------------------------- Shell首先將間隔設定為n/2，然后跳躍進行插入排序，再來將間隔n/4，跳躍進行排序動作，再來 間隔設定為n/8、n/16，直到間隔為1之后的最后一次排序終止，由于上一次的排序動作都會將 固定間隔內的元素排序好，所以當間隔越來越小時，某些元素位于正確位置的機率越高，因此 最后幾次的排序動作將可以大幅減低。 ---------------------------------------------------------------------*/ 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(希爾)排序法（改進的插入排序法）------------------"); System.out.print("排序后是:"); for(i=0;i<=MAX-1;i++){ System.out.print(number[i]+" "); } System.out.println(); System.out.println("排序使用時間："+(end-start)+" ns"); } /*---------------------Shake排序法（改良的冒泡排序法）-------------------------- 方法就在于氣泡排序的雙向進行，先讓氣泡排序由左向右進行，再來讓氣泡排序由右往左進行， 如此完成一次排序的動作，而您必須使用left與right兩個旗標來記錄左右兩端已排序的元素位置。 --------------------------------------------------------------------*/ public void shakersort(int number[]) { int i, temp, left = 0, right = MAX - 1, shift = 0; long start,end; start=System.nanoTime(); while(left < right) { // 向右進行氣泡排序 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; // 向左進行氣泡排序 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排序法（改進的冒泡排序法）------------------"); System.out.print("排序后是:"); for(i=0;i<=MAX-1;i++){ System.out.print(number[i]+" "); } System.out.println(); System.out.println("排序使用時間："+(end-start)+" ns"); } /*-----------------------heap排序（堆排序法--改進的選擇排序）---------------------------- 利用堆積樹的原理，先構造一個堆積樹（看堆積樹的定義，筆記本上有），然后將根節點與最后的葉子節點交換，并屏蔽掉最后一個葉子節點， 然后再將未被屏蔽的部分重新構造堆積樹，然后再重復上面的步驟，直到所有的數被按順序排好。 --------------------------------------------------------------------------------*/ 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排序（堆排序法--改進的選擇排序）------------------"); System.out.print("排序后是:"); for(i=0;i<=MAX-1;i++){ System.out.print(number[i]+" "); } System.out.println(); System.out.println("排序使用時間："+(end-start)+" ns"); } //將原數組構造為從下標1開始的一個新數組，便于處理，同時將這個新數組構造為最初始的堆積樹結構 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]; } } /*-----------------------快速排序法（一）--------------------------------------------- 這邊所介紹的快速演算如下：將最左邊的數設定為軸，并記錄其值為s 廻圈處理： 令索引i 從數列左方往右方找，直到找到大于s 的數 令索引j 從數列左右方往左方找，直到找到小于s 的數 如果i >= j，則離開回圈 如果i < j，則交換索引i與j兩處的值 將左側的軸與j 進行交換 對軸左邊進行遞回 對軸右邊進行遞回 --------------------------------------------------------------------------------*/ 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("排序使用時間："+(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); // 對左邊進行遞回 quicksort_1(number, j+1, right); // 對右邊進行遞回 } } /*-----------------------快速排序法（二）--------------------------------------------- 在這個例子中，取中間的元素s作比較，同樣的先得右找比s大的索引i，然后找比s小的 索引j，只要兩邊的索引還沒有交會，就交換i 與j 的元素值，這次不用再進行軸的交換了， 因為在尋找交換的過程中，軸位置的元素也會參與交換的動作，例如： 41 24 76 11 45 64 21 69 19 36 首先left為0，right為9，(left+right)/2 = 4（取整數的商），所以軸為索引4的位置，比較的元素是 45，您往右找比45大的，往左找比45小的進行交換： 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] 完成以上之后，再初別對左邊括號與右邊括號的部份進行遞回，如此就可以完成排序的目的。 --------------------------------------------------------------------------------*/ 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("排序使用時間："+(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); // 對左邊進行遞回 quicksort_2(number, j+1, right); // 對右邊進行遞回 } } /*-----------------------快速排序法（三）--------------------------------------------- 先說明這個快速排序法的概念，它以最右邊的值s作比較的標準，將整個數列分為三個部份， 一個是小于s的部份，一個是大于s的部份，一個是未處理的部份，如下所示： i j --------|-----------|----------|s 小于s 大于s 未處理 在排序的過程中，i 與j 都會不斷的往右進行比較與交換，最后數列會變為以下的狀態： -------------|-----------------|s 小于s 大于s 然后將s的值置于中間，接下來就以相同的步驟會左右兩邊的數列進行排序的動作，如下所示： -------------|s|--------------- 小于s 大于s 然后采用遞歸的方法重復上面的步驟，就可以實現排序了。 --------------------------------------------------------------------------------*/ 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("排序使用時間："+(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); } } /*-----------------------合并排序法--------------------------------------------- 合并排序法基本是將兩筆已排序的資料合并并進行排序，如果所讀入的資料尚未排序， 可以先利用其它的排序方式來處理這兩筆資料，然后再將排序好的這兩筆資料合并。 合并排序法中用到了 快速排序法（三） --------------------------------------------------------------------------------*/ 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("排序使用時間："+(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++]; } } /*-----------------------基數排序法--------------------------------------------- 基數排序的方式可以采用LSD（Least sgnificant digital）或MSD（Most sgnificant digital）， LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。 以LSD為例，假設原來有一串數值如下所示： 73, 22, 93, 43, 55, 14, 28, 65, 39, 81 首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中： 0 1 2 3 4 5 6 7 8 9 81 65 39 43 14 55 28 93 22 73 接下來將這些桶子中的數值重新串接起來，成為以下的數列： 81, 22, 73, 93, 43, 14, 55, 65, 28, 39 接著再進行一次分配，這次是根據十位數來分配： 接下來將這些桶子中的數值重新串接起來，成為以下的數列： 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 這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最 高位數為止。 LSD的基數排序適用于位數小的數列，如果位數多的話，使用MSD的效率會比較好，MSD的方 式恰與LSD相反，是由高位數為基底開始進行分配，其他的演算方式則都相同。 --------------------------------------------------------------------------------*/ 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("-----------------基數排序法------------------"); System.out.print("排序后是:"); for(int ii=0;ii<=MAX-1;ii++){ System.out.print(number[ii]+" "); } System.out.println(); System.out.println("排序使用時間："+(end-start)+" ns"); } public static void main(String[] args){ System.out.println("以下的測試時間僅供參考..."); new PaiXu(); } } 以上代碼的運行結果如下所示
以下的測試時間僅供參考... 生成的隨機數組是：53 82 61 70 75 31 30 68 22 56 48 23 12 74 13 85 69 62 21 55 合并排序法需要使用的數組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 排序使用時間：7815 ns -----------------插入排序法------------------ 排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85 排序使用時間：7475 ns -----------------冒泡排序法------------------ 排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85 排序使用時間：18008 ns -----------------shell(希爾)排序法（改進的插入排序法）------------------ 排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85 排序使用時間：11212 ns -----------------shake排序法（改進的冒泡排序法）------------------ 排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85 排序使用時間：14610 ns -----------------heap排序（堆排序法--改進的選擇排序）------------------ 排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85 排序使用時間：15969 ns -----------------快速排序法（ 一 ）------------------ 排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85 排序使用時間：8834 ns -----------------快速排序法（ 二 ）------------------ 排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85 排序使用時間：9853 ns -----------------快速排序法（ 三 ）------------------ 排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85 排序使用時間：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 排序使用時間：20387 ns -----------------基數排序法------------------ 排序后是:12 13 21 22 23 30 31 48 53 55 56 61 62 68 69 70 74 75 82 85 排序使用時間：8495 ns 再次申明，以上的測試時間僅供參考，在項目中需要使用什么排序算法要根據實際情況來確定。
新聞熱點
疑難解答
