【Java】数据结构-插入排序法

插入排序法

• 从[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));
    }
}