插入排序法
-
从[0,i)每一位跟自己i-1进行比较大小，如果小，就交换到前面，如果大就不变。
插入排序法执行截图
插入排序法代码（完整）
InsertionSort.java
public class InsertionSort {
private InsertionSort(){} //私有类
public static <E extends Comparable<E>> void sort(E[] arr){
for(int i = 0 ; i < arr.length ; i++){
// 将arr[i]插入到合适的位置
// for(int j = i ; j > 0; j--) //不断和前面的值比较，小就交换，大就结束
// if(arr[j].compareTo(arr[j-1])<0)
// swap(arr, j , j-1);
// else break;
for(int j = i; j > 0 && arr[j].compareTo(arr[j-1])<0; j-- )
swap(arr,j,j-1);
}
}
private static <E> void swap(E[] arr, int i , int j){
E t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int[] dataSize = {10000, 100000};
for (int n : dataSize) {
Integer[] arr = ArrayGenerator.generateRandomArray(n, n);
SortingHelper.sortTest("InsertionSort", arr);
}
}
}
SortingHelper.java（延续了前面的选择排序法）
public class SortingHelper {
private SortingHelper(){}
public static <E extends Comparable<E>> boolean isSorted(E[] arr){
for(int i = 1; i< arr.length; i++)
if (arr[i - 1].compareTo(arr[i]) > 0)
return false;
return true;
}
public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
long startTime = System.nanoTime();
if(sortname.equals("SelectionSort"))
SelectionSort.sort(arr);
else if(sortname.equals("InsertionSort"))
InsertionSort.sort(arr);
long endTime = System.nanoTime();
for(E e:arr){
System.out.println(e);
}
double time = (endTime - startTime) / 1000000000.0; //纳米要/9个零
if(!SortingHelper.isSorted(arr))
throw new RuntimeException(sortname + "failed");
System.out.println(String.format("%s , n = %d : %f s ", sortname, arr.length, time));
}
}
| 
[复制链接]
发表于 2021-6-24 22:03
