三分钟彻底理解插入排序

1、原理：从整个待排序列中选出一个元素插入到已经有序的子序列中去，得到一个有序的、元素加一的子序列，直到整个序列的待插入元素为0，则整个序列全部有序。

2、思路：

　　(1)设置监视哨r[0]，将待插入的记录值赋值给r[0];

　　(2)设置开始查找的位置j;

　　(3)在数组中搜索，搜索中将第j个记录后移，直到r[0].key>=r[j].key为止

　　(4)将r[0]插入r[j+1]的位置上。

3、举例

　　(1)待排序数组：[5,3,4,0,6]

　　(2)第一趟排序：[5,3,4,0,6]

　　　　将r[0]=5设置为监视哨，将1位置上的数3和监视哨5进行比较，3小于5，将5和3交换。

　　　　排序结果为：[3,5,4,0,6] 此时0-1范围上的数值大小已经排好了。

　　(3)第二趟比较：[3,5,4,0,6]

　　　　将4和5进行比较，4比5小，交换位置，排序结果为：[3,4,5,0,6]

　　　　将4和3进行比较，4比3大，不交换位置。

　　　　排序结果为：[3,4,5,0,6]　　此时0-2位置上的数值大小已经排列好了

　　(4)第三趟比较：[3,4,5,0,6]

　　　　将0和5做比较，0比5小，交换位置，排序结果为：[3,4,0,5,6]

　　　　将0和4做比较，0比4小，交换位置，排序结果为：[3,0,4,5,6]

　　　　将0和3做比较，0比3小，交换位置，排序结果为：[0,3,4,5,6]

　　　　排序结果为：[0,3,4,5,6]，此时0-3位置上的书已经排好序

　　(5)第四趟比较：[0,3,4,5,6]

　　　　6比5大，已经全局有序，不用进行任何的交换

4.java实现的代码

import java.util.Scanner;

public class InsertSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入一个数组的大小：");
        int a = sc.nextInt();
        System.out.println("请输入一个数组：");
        int[] arr = new int[a];
        for (int i=0 ; i<a;i++){
            arr[i]= sc.nextInt();

        }
        //遍历数组
        for(int k = 0 ; k<arr.length;k++){
            System.out.print("  "+arr[k]);
        }
        System.out.println();
        insertSort(arr);

    }
    public static void insertSort(int[] arr){
        if(arr==null || arr.length<2){
            return;
        }
        for(int i=1; i <arr.length;i++){
            for(int j=i-1;j>=0&&arr[j]>arr[j+1];j--){
                int temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }

        }
        //将数组进行遍历
        for(int k = 0 ; k<arr.length;k++){
            System.out.print("  "+arr[k]);
        }


    }
}

　　算法的最大时间复杂度仍然是O(n^2)，如果数据有序，那么插入排序的时间复杂度是O(n),如果数据是无序的，比如说是逆序的，那么时间复杂度就是O(n^2)。当数据状况不同，一律按照最差的时间复杂度进行估计。

　　时间复杂度为一个算法流程中，常数操作数量的指标，常用O来表示