Java中的各種排序算法

各種排序算法：

冒泡排序，選擇排序，插入排序，稀爾排序，快速排序，歸並排序，堆排序，桶式排序，基數排序

一、冒泡排序(Bubble Sort)
1. 基本思想：
　　兩兩比較待排序數據元素的大小，發現兩個數據元素的次序相反時即進行交換，直到沒有反序的數據元素為止。
2. 排序過程：
　　設想被排序的數組R［1..N］垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最後任何兩個氣泡都是輕者在上，重者在下為止。

【示例】：

49 13 13 13 13 13 13 13
38 49 27 27 27 27 27 27
65 38 49 38 38 38 38 38
97 65 38 49 49 49 49 49
76 97 65 49 49 49 49 49
13 76 97 65 65 65 65 65
27 27 76 97 76 76 76 76
49 49 49 76 97 97 97 97

java代碼實現：

1. /**
2. * 冒泡排序：
3. * 執行完一次內for循環後，最小的一個數放到了數組的最前面，相鄰位置之間交換
4. * @author TSW
5. *
6. */ 
7. public class BubbleSort { 
8.  
9.     public staticvoid main(String[] args) { 
10.         Integer[] intgArr = { 7, 2, 4, 3, 12,1, 9,6, 8,5, 11,10 }; 
11.         BubbleSort bubblesort = new BubbleSort(); 
12.         bubblesort.bubble(intgArr, 0, intgArr.length -1); 
13.         for (Integer intObj : intgArr) { 
14.             System.out.print(intObj + " "); 
15.         } 
16.     } 
17.      
18.     /**
19.      * 排序算法的實現，對數組中指定的元素進行排序  
20.      * @param array 待排序的數組    
21.      * @param from 從哪裡開始排序  
22.      * @param end 排到哪裡
23.      */ 
24.     public void bubble(Integer[] array,int from, int end) { 
25.  
26.         // 需 array.length - 1 輪比較 
27.  
28.         for (int k =1; k < end - from + 1; k++) { 
29.  
30.             // 每輪循環中從最後一個元素開始向前起泡，直到i=k止，即i等於輪次止 
31.  
32.             for (int i = end - from; i >= k; i--) { 
33.  
34.                 // 按照一種規則（後面元素不能小於前面元素）排序 
35.  
36.                 if ((array[i].compareTo(array[i -1])) < 0) { 
37.  
38.                     // 如果後面元素小於了（當然是大於還是小於要看比較器實現了）前面的元素，則前後交換 
39.  
40.                     swap(array, i, i - 1); 
41.  
42.                 } 
43.  
44.             } 
45.  
46.         } 
47.  
48.     } 
49.      
50.     /**
51.      * 交換數組中的兩個元素的位置  
52.      * @param array 待交換的數組  
53.      * @param i 第一個元素  
54.      * @param j 第二個元素  
55.      */ 
56.     public void swap(Integer[] array,int i, int j) { 
57.  
58.         if (i != j) {// 只有不是同一位置時才需交換 
59.  
60.             Integer tmp = array[i]; 
61.  
62.             array[i] = array[j]; 
63.  
64.             array[j] = tmp; 
65.  
66.         } 
67.  
68.     } 
69.  
70. } 

1. /** 
2.  * 冒泡排序： 
3.  * 執行完一次內for循環後，最小的一個數放到了數組的最前面，相鄰位置之間交換  
4.  * @author TSW 
5.  * 
6.  */  
7. public class BubbleSort {  
8.   
9.     public static void main(String[] args) {  
10.         Integer[] intgArr = { 7, 2, 4, 3, 12, 1, 9, 6, 8, 5, 11, 10 };  
11.         BubbleSort bubblesort = new BubbleSort();  
12.         bubblesort.bubble(intgArr, 0, intgArr.length - 1);  
13.         for (Integer intObj : intgArr) {  
14.             System.out.print(intObj + " ");  
15.         }  
16.     }  
17.       
18.     /** 
19.      * 排序算法的實現，對數組中指定的元素進行排序    
20.      * @param array 待排序的數組      
21.      * @param from 從哪裡開始排序    
22.      * @param end 排到哪裡 
23.      */  
24.     public void bubble(Integer[] array, int from, int end) {  
25.   
26.         // 需 array.length - 1 輪比較   
27.   
28.         for (int k = 1; k < end - from + 1; k++) {  
29.   
30.             // 每輪循環中從最後一個元素開始向前起泡，直到i=k止，即i等於輪次止   
31.   
32.             for (int i = end - from; i >= k; i--) {  
33.   
34.                 // 按照一種規則（後面元素不能小於前面元素）排序   
35.   
36.                 if ((array[i].compareTo(array[i - 1])) < 0) {  
37.   
38.                     // 如果後面元素小於了（當然是大於還是小於要看比較器實現了）前面的元素，則前後交換   
39.   
40.                     swap(array, i, i - 1);  
41.   
42.                 }  
43.   
44.             }  
45.   
46.         }  
47.   
48.     }  
49.       
50.     /** 
51.      * 交換數組中的兩個元素的位置    
52.      * @param array 待交換的數組    
53.      * @param i 第一個元素    
54.      * @param j 第二個元素    
55.      */  
56.     public void swap(Integer[] array, int i, int j) {  
57.   
58.         if (i != j) {// 只有不是同一位置時才需交換   
59.   
60.             Integer tmp = array[i];  
61.   
62.             array[i] = array[j];  
63.   
64.             array[j] = tmp;  
65.   
66.         }  
67.   
68.     }  
69.   
70. }  

另外一種實現方式：

1. /**
2. * 冒泡排序：執行完一次內for循環後，最大的一個數放到了數組的最後面。相鄰位置之間交換
3. */ 
4.  
5. public class BubbleSort2 { 
6.  
7.     public staticvoid main(String[] args) { 
8.  
9.         int[] a = { 3,5, 9,4, 7,8, 6,1, 2 }; 
10.  
11.         BubbleSort2 bubble = new BubbleSort2(); 
12.  
13.         bubble.bubble(a); 
14.  
15.         for (int num : a) { 
16.  
17.             System.out.print(num + " "); 
18.  
19.         } 
20.  
21.     } 
22.  
23.     public void bubble(int[] a) { 
24.  
25.         for (int i = a.length -1; i > 0; i--) { 
26.  
27.             for (int j =0; j < i; j++) { 
28.  
29.                 if (new Integer(a[j]).compareTo(new Integer(a[j +1])) > 0) { 
30.  
31.                     swap(a, j, j + 1); 
32.  
33.                 } 
34.  
35.             } 
36.  
37.         } 
38.  
39.     } 
40.  
41.     public void swap(int[] a,int x, int y) { 
42.  
43.         int temp; 
44.  
45.         temp = a[x]; 
46.  
47.         a[x] = a[y]; 
48.  
49.         a[y] = temp; 
50.  
51.     } 
52.  
53. } 

1. /** 
2.  * 冒泡排序：執行完一次內for循環後，最大的一個數放到了數組的最後面。相鄰位置之間交換 
3.  */  
4.   
5. public class BubbleSort2 {  
6.   
7.     public static void main(String[] args) {  
8.   
9.         int[] a = { 3, 5, 9, 4, 7, 8, 6, 1, 2 };  
10.   
11.         BubbleSort2 bubble = new BubbleSort2();  
12.   
13.         bubble.bubble(a);  
14.   
15.         for (int num : a) {  
16.   
17.             System.out.print(num + " ");  
18.   
19.         }  
20.   
21.     }  
22.   
23.     public void bubble(int[] a) {  
24.   
25.         for (int i = a.length - 1; i > 0; i--) {  
26.   
27.             for (int j = 0; j < i; j++) {  
28.   
29.                 if (new Integer(a[j]).compareTo(new Integer(a[j + 1])) > 0) {  
30.   
31.                     swap(a, j, j + 1);  
32.   
33.                 }  
34.   
35.             }  
36.   
37.         }  
38.   
39.     }  
40.   
41.     public void swap(int[] a, int x, int y) {  
42.   
43.         int temp;  
44.   
45.         temp = a[x];  
46.   
47.         a[x] = a[y];  
48.   
49.         a[y] = temp;  
50.   
51.     }  
52.   
53. }