首页 > 代码库 > 直接插入排序
直接插入排序
目录：
1、为什么要用？（它的好处或优点）
2、原理是什么？（效果）
3、怎样去实现？（想马上看代码的同学点这里）
为什么要用？
1、时间复杂度： 平均情况 O(n2)、最坏情况O(n2)，最好情况O(n)
2、空间复杂度： O(1) —— 可理解为一个变量
3、稳定性： 稳定
4、复杂度：简单 容易实现
适用场景： 比较适用相对有序的情况下进行排序，或者在已经有序的情况下插入少量元素进入后的重新排序，实现容易，稳定，空间占用少
不适用场景 ： 排序逆序序列
原理是什么？
原理描述：
从第一个开始构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找比它大的最前面一个，插入其前面，如此往复，直到最后。
原理图如下：
动态图如下：
宏观效果：
怎样去实现？
java 实现代码：
class insertion_sort { public static void insertion(int[] arr) { int i,j,t; for (i = 1; i < arr.length; i++ ){ t = arr[i]; j = i - 1; while(j >= 0 && arr[j] > t){ arr[j + 1] = arr[j]; j--; } arr[j+1] = t; printArray(arr); } } public static void main (String[] args) throws java.lang.Exception { int[] arr = {6,5,3,1,8,7,2,4}; printArray(arr); insertion(arr); } public static void printArray(int[] arr){ for(int i : arr){ System.out.print(i+" "); } System.out.println(); } }
输出结果 ：
6 5 3 1 8 7 2 4 5 6 3 1 8 7 2 4 3 5 6 1 8 7 2 4 1 3 5 6 8 7 2 4 1 3 5 6 8 7 2 4 1 3 5 6 7 8 2 4 1 2 3 5 6 7 8 4 1 2 3 4 5 6 7 8
在线测试地址 ：https://www.shucunwang.com/RunCode/java/#id/366a8d22961113e4ea4ca1fbcaf0d736
开源代码地址 ：https://git.oschina.net/ITxiaoyan/SortAlgorithm
2017-03-23
直接插入排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。