排序算法(JAVA實現)：冒泡排序法和插入排序法

為了方便擴展，先引入一個抽象的基礎類：

[html]

1. package com.andyidea.algorithms;
3. /**
4. * 排序抽象基礎類
5. * @author Andy.Chen
6. *
7. * @param <T>
8. */
9. public abstract class Sorter<T extends Comparable<T>> {
11. public abstract void sort(T[] array,int from,int len);
13. public final void sort(T[] array){
14. sort(array,0,array.length);
15. }
17. protected final void swap(T[] array,int from,int to){
18. T tmp = array[from];
19. array[from] = array[to];
20. array[to] = tmp;
21. }
23. }

【一】冒泡排序：冒泡排序是一種簡單的排序算法，其平均時間復雜度為O(n²)，它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

冒泡排序算法的具體描述如下：

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。在這一點，最後的元素應該會是最大的數。
3. 針對所有的元素重復以上的步驟，除了最後一個。
4. 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

冒泡排序算法源碼如下：

[html]

1. package com.andyidea.algorithms;
3. /**
4. * 冒泡排序法
5. * @author Andy.Chen
6. *
7. * @param <T>
8. */
9. public class BubbleSort<T extends Comparable<T>> extends Sorter<T> {
11. //是否從右向左排序的標志位
12. public static boolean RIGHT = true;
14. @Override
15. public void sort(T[] array, int from, int len) {
16. if(RIGHT){
17. bubble_right(array, from, len);
18. }else{
19. bubble_left(array, from, len);
20. }
21. }
23. /**
24. * 從右向左排序
25. * @param array
26. * @param from
27. * @param len
28. */
29. public final void bubble_right(T[] array, int from, int len){
30. for(int i=from; i<from+len; i++){
31. for(int j=from+len-1;j>i;j--){
32. if(array[j].compareTo(array[j-1])<0){
33. swap(array, j-1, j);
34. }
35. }
36. }
37. }
39. /**
40. * 從左向右排序
41. * @param array
42. * @param from
43. * @param len
44. */
45. public final void bubble_left(T[] array, int from, int len){
46. for(int i=from+len-1; i>from;i--){
47. for(int j=from;j<i;j++){
48. if(array[j].compareTo(array[j+1])>0){
49. swap(array,j,j+1);
50. }
51. }
52. }
53. }
55. }

【二】插入排序：插入排序（Insertion Sort）的算法描述是一種簡單直觀的排序算法，其平均時間復雜度為O(n²)。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反復把已排序元素逐步向後挪位，為最新元素提供插入空間。

插入排序都采用in-place在數組上實現。具體算法描述如下：

1. 從第一個元素開始，該元素可以認為已經被排序
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描
3. 如果該元素（已排序）大於新元素，將該元素移到下一位置
4. 重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
5. 將新元素插入到該位置中
6. 重復步驟2

[html]

1. package com.andyidea.algorithms;
3. /**
4. * 插入排序法
5. * @author Andy.Chen
6. * @param <T>
7. *
8. */
9. public class InsertionSort<T extends Comparable<T>> extends Sorter<T> {
11. @Override
12. public void sort(T[] array, int from, int len) {
13. T tmp = null;
14. for(int i=from+1;i<from+len;i++){
15. tmp = array[i];
16. int j = i;
17. for( ; j>from; j--){
18. if(tmp.compareTo(array[j-1]) < 0){
19. array[j] = array[j-1];
20. }else{
21. break;
22. }
23. }
24. array[j] = tmp;
25. }
26. }
28. }