共计 1110 个字符,预计需要花费 3 分钟才能阅读完成。
简介
插入排序就是将要排序的元素插入到曾经排序的数组中,从而造成一个新的排好序的数组。
这个算法就叫做插入排序。
插入排序的例子
同样的,如果咱们有一个数组:29,10,14,37,20,25,44,15,怎么对它进行插入排序呢?
先看一个插入排序的动画,对它有个直观的理解:
咱们来剖析一下排序的流程。
八个数字,咱们分为 7 轮。
第一轮,假如 29 是曾经排好序的数组,从第二个元素开始,向排好序的数组插入新的元素。也就是说向数组 [29] 插入 10。失去[10,29]。
第二轮,[10,29]曾经排好序了,抉择数组中的第三个元素 14,插入排好序的数组[10,29]。
先将 29 和 14 比拟,发现 29>14, 则将 29 右移一位[10, ,29], 而后比拟 10 和 14,发现 10 小于 14,那么将 14 插入 10 前面[10,14,29],以此类推。
插入排序的 java 程序
咱们看下 java 程序怎么写:
public class InsertionSort {public void doInsertSort(int[] array){log.info("排序前的数组为:{}",array);
int n = array.length;
// 从第二个元素开始插入
for (int i = 1; i < n; ++i) {int key = array[i];
int j = i - 1;
// j 示意的是要插入元素之前的曾经排好序的数组
// 曾经排好序的数组,从后向前和要插入的数据比拟,如果比要插入的数据大,须要右移一位
while (j >= 0 && array[j] > key) {array[j + 1] = array[j];
j = j - 1;
}
// 最初的 j + 1 的地位就是须要插入新元素的地位
array[j + 1] = key;
log.info("第 {} 轮排序后的数组为:{}", i+1, array);
}
}
public static void main(String[] args) {int[] array= {29,10,14,37,20,25,44,15};
InsertionSort insertionSort=new InsertionSort();
insertionSort.doInsertSort(array);
}
}
运行后果:
插入排序的工夫复杂度
从代码中咱们能够看到,插入排序有一个 for 循环,在 for 循环中还有一个 while 循环。
所以插入排序的工夫复杂度也是 O(n²)。
本文的代码地址:
learn-algorithm
本文已收录于 http://www.flydean.com/algorithm-insertion-sort/
最艰深的解读,最粗浅的干货,最简洁的教程,泛滥你不晓得的小技巧等你来发现!
欢送关注我的公众号:「程序那些事」, 懂技术,更懂你!
正文完