插入排序--自学笔记

插入排序

学习目标：

1.插入排序的思想

2.移动法

3.交换法

4.复杂度分析

1.插入排序的思想

就像打扑克牌一样，在已排序的序列中，从后向前扫描，找到相应位置并插入

是一种“后来的数字”找自己位置的过程

从第二个数字 2 开始，取出待插入的数字 2 ，往前插入

数字 2 与 6 比较 2<6 所以 6 向右移动，将 2 插入

以此类推

直到最后一个数字插入后，排序完成

2.移动法

publicstaticvoidinsertSort(int[]arr){for(inti=1;i<arr.length;i++){intcurrentNumber=arr[i];intj=i-1;while(j>=0&&arr[j]>currentNumber){arr[j+1]=arr[j];j--;}//跳出循环的条件//1.遇到了一个比currentNumber小的数 则把currentNumber放到该数后面//2.j<0 说明整个数组currentNumber最小 把它放到开头arr[j+1]=currentNumber;}}

3.交换法

publicstaticvoidinsertSort(int[]arr){for(inti=1;i<arr.length;i++){intj=i;//j-1 值小于 j 则交换while(j>=1&&arr[j]<arr[j-1]){swap(arr,j,j-1);j--;}}}

4.复杂度分析

时间复杂度：O(n²)

​ *与冒泡、选择排序类似，都需要两层循环

空间复杂度：O(1)

​ *只引入了常数级别的变量

析

时间复杂度：O(n²)

​ *与冒泡、选择排序类似，都需要两层循环

空间复杂度：O(1)

​ *只引入了常数级别的变量

147. 对链表进行插入排序 - 力扣（LeetCode）