插入排序---算法

1、算法概念

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

2、算法步骤

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

public class _03插入排序 {public static void main(String[] args) {int[] arr = {5,4,3,2,1};for (int i = 1; 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/

代码同上