本文主要是介绍插入排序算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

插入排序与选择排序的区别：

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

代码实现

package InsertionSort;

public class InsertionSort {

    private InsertionSort(){}

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

        for (int i=0; i<arr.length; i++){

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

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

}

package InsertionSort;

import SelectionSort1.SelectionSort;

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

        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<n; i++){
            arr[i] = i;
        }
        return arr;
    }

    //生成一个长度为 n 的随机数组，每个数组的范围是 [0，bound)
    public static Integer[] generateRandomArray(int n, int bound){

        Integer[] arr = new Integer[n];
        Random rnd = new Random();
        for (int i=0; i<n; i++){
            arr[i] = rnd.nextInt(bound);
        }
        return arr;
    }

}

这篇关于插入排序算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！