绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
看动画学算法之:排序-插入排序
2020-07-13 14:01:17

简介


插入排序就是将要排序的元素插入到已经排序的数组中,从而形成一个新的排好序的数组。


这个算法就叫做插入排序。

插入排序的例子


同样的,假如我们有一个数组: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 >= && 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²)。


本文的代码地址:

https://github.com/ddean2009/learn-algorithm/tree/master/sorting

分享好友

分享这个小栈给你的朋友们,一起进步吧。

程序那些事
创建时间:2020-06-17 07:11:38
通俗的解读,深刻的干货,简洁的教程,众多你不知道的小技巧,尽在公众号:程序那些事!
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • flydean程序那些事
    栈主

小栈成员

查看更多
  • ?
  • 小天
  • 林昆
  • 背后
戳我,来吐槽~