漫画:什么是插入排序?

小灰 梦见 2019-08-12



—————  第二天  —————






————————————







人们如何进行扑克牌的排序呢?


举个例子,比如我手中有红桃6,7,9,10这四张牌,已经处于升序排列:



这时候,我又抓到了一张红桃8,如何让手中的五张牌重新变成升序呢?用冒泡排序,选择排序,亦或是快速排序?



恐怕正常人打牌的时候都不会那么做。最自然也最简单的方式,是在已经有序的四张牌中找到红桃8应该插入的位置,也就是7和9之间,把红桃8插入进去:





给定无序数组如下:



把数组的首元素5作为有序区,此时有序区只有这一个元素:



第一轮

让元素8和有序区的元素依次比较。

8>5,所以元素8和元素5无需交换。


此时有序区的元素增加到两个:



第二轮

素6和有序区的元素依次比较。

6<8,所以把元素6和元素8进行交换:



6>5,所以把元素6和元素5无需交换。


此时有序区的元素增加到三个:



第三轮

素3和有序区的元素依次比较。

3<8,所以把元素3和元素8进行交换:



3<6,所以把元素3和元素6进行交换:



3<5,所以把元3和元素5进行交换:



此时有序区的元素增加到四个:




以此类推,插入排序一共会进行(数组长度-1)轮,每一轮的结果如下:






什么意思呢?让我们以第三轮举例:



在第三轮操作中,我们需要让元素3逐个与有序区的元素进行比较和交换,与8交换、与6交换、与5交换,最终交换到有序区的第一个位置。


但是我们并不需要真的进行完整交换,只需把元素3暂存起来,再把有序区的元素从左向右逐一复制。


第一步,暂存元素3:



第二步,和前一个元素比较,由于3<8,复制元素8到它下一个位置:



第三步,和前一个元素比较,由于3<6,复制元素6到它下一个位置:



第四步,和前一个元素比较,由于3<5,复制元素5到它下一个位置:



第五步,也是最后一步,把暂存的元素3赋值到数组的首位:



显然,这样的优化方法减少了许多无谓的交换。




  1. public static void sort(int[] array){

  2. for(int i=1;i<array.length;i++){

  3. int insertValue =array[i];

  4. int j=i-1;

  5. //从右向左比较元素的同时,进行元素复制

  6. for(; j>=0&&insertValue<array[j]; j--){

  7. array[j+1]=array[j];

  8. }

  9. //insertValue的值插入适当位置

  10. array[j+1]=insertValue;

  11. }

  12. }


  13. public static void main(String[] args) {

  14. int array[]={12,1,3,46,5,0,-3,12,35,16};

  15. sort(array);

  16. System.out.println(Arrays.toString(array));

  17. }






—————END—————




喜欢本文的朋友,欢迎关注公众号 程序员小灰,收看更多精彩内容



欢迎长按二维码关注 小灰学英语,你所学到的不只是英语!



给个[在看],是对小灰最大的支持!
文章已于修改
    已同步到看一看

    发送中

    本站仅按申请收录文章,版权归原作者所有
    如若侵权,请联系本站删除
    觉得不错,分享给更多人看到
    梦见 热门文章:

    漫画:编程其实是文科    阅读/点赞 : 1108/17

    我是一个线程    阅读/点赞 : 693/22

    漫画:三分钟了解敏捷开发    阅读/点赞 : 644/17

    漫画:什么是中间人攻击    阅读/点赞 : 613/16

    我是一个Java class    阅读/点赞 : 552/10

    网贷遇雷潮,投资者如何避雷?    阅读/点赞 : 0/0