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. }