插入排序 insertionSort

插入排序法的原理，它的原理是每插入一个数都要将它和之前的已经完成排序的序列进行重新排序，也就是要找到新插入的数对应原序列中的位置。那么也就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序，时间复杂度同样为O（n²）。 这种算法是稳定的排序方法。

代码

public class 插入排序 {
    public static void main(String[] args){
        int[] a={4,1,2,8,6,7};
        insertionSort(a);
        for (int i = 0; i <a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
    public static  void  insertionSort(int[] arr){
        if (arr==null||arr.length<2){ //如果数组为空或者长度为小于等于1
            return;
        }
        for(int i=1;i<arr.length;i++){
            for (int j=i-1;j>=0&&arr[j]>arr[j+1];j--){
                swap(arr,j+1,j);
            }
        }
    }

    //交换数组array上,ab两个位置的值
    public static void swap(int [] array,int a,int b){ //a,b为数组下标
        int temp=array[a];
        array[a]=array[b];
        array[b]=temp;
    }
}

插入排序和冒泡排序以及选择排序的最大的区别:

冒泡排序以及选择排序与数据状况没关系,比较和遍历次数都是确定,不会停止
但是插入排序是跟数据状况一样的,最直观的前面数据从小到大都是排好序的,这里插入了一个大值放在最后,那么根本就不需要排序了.

这里当数据状况不同可能产生不同的时间复杂度,我们一般直接按照最差情况进行估计
所以这里插入排序的时间复杂度为O(N^2)