1,采用選擇排序對元素進行排列時,元素之間需要進行比較,因此需要實現Comparable<T>接口。即,<T extends Comparable<T>>. 更進一步,如果允許待比較的類型可以和它的父類型進行比較,則需要寫成:<T extends Comparable<? super T>, 其中<? super T> 表示 T 的任意超類。
2,SelectionSortArray.java 實現了選擇排序的迭代形式和遞歸形式。具體代碼如下:
public class SelectionSortArray {
/*
* Task:將數組中前n個對象按升序排列
* @param a Comparable 對象的數組
* @param n 大於0的整數,表示數組的長度
*/
public static <T extends Comparable<? super T>> void selectionSort(T[] a, int n){
for(int index = 0; index < n-1; index++){
int indexOfNextSmallest = getIndexOfSmallest(a, index, n-1);
swap(a, index, indexOfNextSmallest);
}
}
//返回索引first 至 索引last 之間的最小值的索引
private static <T extends Comparable<? super T>> int getIndexOfSmallest(T[] a, int first, int last){
T min = a[first];
int indexOfMin = first;
for(int index = first + 1; index <= last; index++){
if(a[index].compareTo(min) < 0){
min = a[index];
indexOfMin = index;
}//end if
}
return indexOfMin;
}
//交換數組元素不涉及compareTo方法,因而使用Object作為元素類型
private static void swap(Object[] a, int i, int j){
Object temp = a[i];//交換的並不是引用,而是具體的元素的值
a[i] = a[j];
a[j] = temp;
}
//選擇排序的遞歸方法
public static <T extends Comparable<? super T>> void selectionSort_Recursive(T[] a, int n){
selectionSort(a, 0, n - 1);
}
private static <T extends Comparable<? super T>> void selectionSort(T[] a, int first, int last){
if(first < last)
{
int indexOfNextSmallest = getIndexOfSmallest(a, first, last);
swap(a, first, indexOfNextSmallest);
selectionSort(a, first + 1, last);
}
}
}