插入排序---算法

1、算法概念

插入排序：它的工作原理是通过构建有序排序，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置插入。

2、算法步骤

• 将第一待排序序列第一个元素看作一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
• 从头到尾一次扫描为排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素到相等元素的后面）

public class _03插入排序 {
    public static void main(String[] args) {
        int[] arr = {5,4,3,2,1};
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i;
            while(j > 0 && tmp < arr[j-1]){
                arr[j] = arr[j-1];
                j--;
            }
            if(j != i){
                arr[j] =tmp;
            }
        }
        for (int x:arr){
            System.out.print(x + " ");
        }
    }
}

时间复杂度：O ()

例题

https://www.lanqiao.cn/problems/3225/learning/

代码同上