插入排序算法的Java實現

1，對元素進行排列時，元素之間需要進行比較，因此需要實現Comparable<T>接口。即，<T extends Comparable<T>>. 更進一步，如果允許待比較的類型可以和它的父類型進行比較，則需要寫成：<T extends Comparable<? super T>， 其中<? super T> 表示 T 的任意超類。

2，InsertionSortArray.java 類實現了從小到大順序以插入排序的方式對數據進行排序。

3，insertionSort方法負責對每一個元素進行排序，insertInOrder方法將待排序的元素插入到合適的位置，相當於執行具體的操作。

具體代碼如下：

public class InsertionSortArray {
    public static <T extends Comparable<? super T>> void insertSort(T[] a, int n){
        insertionSort(a, 0, n - 1);//對序列a進行排序，其起始索引為0，最後元素的索引為n-1
    }
   
    //從索引first到last執行插入排序
    private static <T extends Comparable<? super T>> void insertionSort(T[] a, int first, int last){
        for(int unsorted = first + 1; unsorted <= last; unsorted++){//插入排序中第一個元素視為有序，故從第二個元素開始
            T firstUnsorted = a[unsorted];//獲得待排序的元素
            insertInOrder(firstUnsorted, a, first, unsorted - 1);//將之插入到合適的位置
        }
    }
   
    //將element插入到已經排好序的，起始位置為begin，終止位置為end的 序列中
    private static <T extends Comparable<? super T>> void insertInOrder(T element, T[] a, int begin, int end){
        int index = end;
        //待插入的元素依次從後往前與已排序好的元素進行比較，直至找到比它小的元素為止
        while((index >= begin) && (element.compareTo(a[index]) < 0)){
            a[index + 1] = a[index];//將元素後移一位，a[index+1]其實就是element
            index--;
        }
        a[index + 1] = element;//將element插入到合適的位置
    }
}

4，在實現排序時，我們使用了泛型。使用泛型的好處是：對於任何類型的對象，只要它實現了Comparable接口，就可以通過調用compareTo方法對之進行比較。

因此，它還可以對自定義類型的對象進行排序，只要你定義的類實現Comparable接口就可以了。

以下測試類中定義了String類型數組和Integer類型的數組，並都可以調用插入排序的方法進行排序，代碼如下：

public class TestSort {
    public static void main(String[] args) {
        String[] arr = {"hello","world","Hadoop","hbase","hive"};
        InsertionSortArray.insertSort(arr, arr.length);
        System.out.println("字符串排序結果");
        for(String str : arr)
            System.out.println(str);
        Integer[] integer = {1,5,3,8,10,4};
        InsertionSortArray.insertSort(integer, integer.length);
        System.out.println("整數排序結果");
        for(int i : integer)
            System.out.println(i);
    }
}