插入排序 java实现
?
//实现1
public class InsertSort(){
?
? ?public static <T extends Comparable <? super T>> void insert(T[] elements) {
for (int i = 1; i < elements.length; i++) {
int j = -1;
while (j <= i && elements[i].compareTo(elements[++j])> 0)
;
if (j < i) {
T temp = elements[i];
for (int k = i - 1; k >= j; k--) {
elements[k + 1] = elements[k];
}
elements[j] = temp;
}
}
}
?
? ? ? public static void main(){
? ? ? ? ? ? Integer [] a={9,8,7,6,5,4};
? ? ? ? ? ? InsertSort.insert(a);
? ? ? ? ? ? for(int i:a){
? ? ? ? ? ? ? ? ? ?System.out.print(i+" ");
? ? ? ? ? ? }
? ? ? }
}
?
?
?
//实现2
?
public class InsertSort {
?
? ? ?public static void main(String[] args) {
? ? ? ? Integer a[] = {1,2,32,4,5,6,7,8,9};
InsertSort.insertSort(a, 0, a.length);
for(int i :a){
System.out.print(i+" ");
}
}
?
public static <T extends Comparable <? super T>>void insertSort(T[]a,int first,int last) {
? ? ? ?for(int i = first + 1;i<last;i++ ){
? ? ? T firstUnsorted = a[i];
? ? ? insertInOrder(firstUnsorted, a, first, i-1);
? ? ? ?}
}
?
//将elements插入到从a[begin]到a[end]的有序数组元素之间
public 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];//腾出空间
? ?index--;
? ?}
? ? ? ? ?a[index+1] = element; ?//插入
}
}
?
?
?
