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 {
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. }
18. /**
19. * 排序算法的實現，對數組中指定的元素進行排序
20. * @param array 待排序的數組
21. * @param from 從哪裡開始排序
22. * @param end 排到哪裡
23. */
24. public void bubble(Integer[] array,int from, int end) {
26. // 需 array.length - 1 輪比較
28. for (int k =1; k < end - from + 1; k++) {
30. // 每輪循環中從最後一個元素開始向前起泡，直到i=k止，即i等於輪次止
32. for (int i = end - from; i >= k; i--) {
34. // 按照一種規則（後面元素不能小於前面元素）排序
36. if ((array[i].compareTo(array[i -1])) < 0) {
38. // 如果後面元素小於了（當然是大於還是小於要看比較器實現了）前面的元素，則前後交換
40. swap(array, i, i - 1);
42. }
44. }
46. }
48. }
50. /**
51. * 交換數組中的兩個元素的位置
52. * @param array 待交換的數組
53. * @param i 第一個元素
54. * @param j 第二個元素
55. */
56. public void swap(Integer[] array,int i, int j) {
58. if (i != j) {// 只有不是同一位置時才需交換
60. Integer tmp = array[i];
62. array[i] = array[j];
64. array[j] = tmp;
66. }
68. }
70. }

1. /**
2. * 冒泡排序：
3. * 執行完一次內for循環後，最小的一個數放到了數組的最前面，相鄰位置之間交換
4. * @author TSW
5. *
6. */
7. public class BubbleSort {
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. }
18. /**
19. * 排序算法的實現，對數組中指定的元素進行排序
20. * @param array 待排序的數組
21. * @param from 從哪裡開始排序
22. * @param end 排到哪裡
23. */
24. public void bubble(Integer[] array, int from, int end) {
26. // 需 array.length - 1 輪比較
28. for (int k = 1; k < end - from + 1; k++) {
30. // 每輪循環中從最後一個元素開始向前起泡，直到i=k止，即i等於輪次止
32. for (int i = end - from; i >= k; i--) {
34. // 按照一種規則（後面元素不能小於前面元素）排序
36. if ((array[i].compareTo(array[i - 1])) < 0) {
38. // 如果後面元素小於了（當然是大於還是小於要看比較器實現了）前面的元素，則前後交換
40. swap(array, i, i - 1);
42. }
44. }
46. }
48. }
50. /**
51. * 交換數組中的兩個元素的位置
52. * @param array 待交換的數組
53. * @param i 第一個元素
54. * @param j 第二個元素
55. */
56. public void swap(Integer[] array, int i, int j) {
58. if (i != j) {// 只有不是同一位置時才需交換
60. Integer tmp = array[i];
62. array[i] = array[j];
64. array[j] = tmp;
66. }
68. }
70. }

另外一種實現方式：

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

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