插入排序算法

选择排序从开始到排序的这个数为止前面排好的数一定是这个数组中从最小依次排序好的，但是插入排序不是，对于插入排序有可能未排序的数组中有这个数组的最小的元素。

package InsertionSort;

public class InsertionSort {

    private InsertionSort(){}

    public static > void sort(E[] arr){

        for (int i=0; i=0; j--){
                if (arr[j].compareTo(arr[j-1])<0){
                    swap(arr,j,j-1);
                }
                else {
                    break;
                }
            }
        }
    }

    private static  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);
        }
    }

}

package InsertionSort;

import SelectionSort1.SelectionSort;

public class SortingHelper {

    private SortingHelper(){}

    public static > 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 > 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();

        double time = (endTime-startTime) / 1000000000.0;

        if (!SortingHelper.isSorted(arr)){
            throw new RuntimeException(sortName + "failed");
        }
        System.out.println(String.format("%s , n = %d : %f s",sortName,arr.length,time));
    }

}

package InsertionSort;

import java.util.Random;

public class ArrayGenerator {

    private ArrayGenerator(){}

    public static Integer[] generateOrderedArray(int n){

        Integer[] arr = new Integer[n];
        for (int i=0; i