【Java】数据结构-插入排序法
# 插入排序法> - ## 从[0,i)每一位跟自己i-1进行比较大小，如果小，就交换到前面，如果大就不变。
# 插入排序法执行截图
!(https://gitee.com/gylq/cloudimages/raw/master/img/image-20210624185045631.png)
# 插入排序法代码（完整）
## InsertionSort.java
```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插入到合适的位置
// for(int j = i ; j > 0; j--)//不断和前面的值比较，小就交换，大就结束
// if(arr.compareTo(arr)<0)
// swap(arr, j , j-1);
// else break;
for(int j = i; j > 0 && arr.compareTo(arr)<0; j-- )
swap(arr,j,j-1);
}
}
private static <E> void swap(E[] arr, int i , int j){
E t = arr;
arr = arr;
arr = 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（延续了前面的选择排序法）
```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.compareTo(arr) > 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));
}
}
``` 这个，我还真不会，mark一下 想学这个，但是感觉一片懵 插下眼，有机会看看 学习一下！！ 哈哈哈好久没看过排序了，感谢楼主分享～
页:
[1]