漫画:什么是插入排序?漫画:什么是插入排序?
漫画:什么是插入排序?

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

漫画:什么是插入排序?漫画:什么是插入排序?漫画:什么是插入排序?

漫画:什么是插入排序?漫画:什么是插入排序?漫画:什么是插入排序?漫画:什么是插入排序?

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

漫画:什么是插入排序?漫画:什么是插入排序?漫画:什么是插入排序?

漫画:什么是插入排序?
漫画:什么是插入排序?

漫画:什么是插入排序?

人们如何进行扑克牌的排序呢?举个例子,比如我手中有红桃 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 赋值到数组的首位:
漫画:什么是插入排序?

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

漫画:什么是插入排序?漫画:什么是插入排序?
[code] 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.


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

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

  16.     sort(array);

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

  18. }

[/code]

漫画:什么是插入排序?

漫画:什么是插入排序?

漫画:什么是插入排序?

漫画:什么是插入排序?

—————END—————
关注文章的同时请关注一下小灰的作品《漫画算法》哦

漫画:什么是插入排序?扫码查看详情漫画:什么是插入排序?小灰把两年多以来积累的漫画作品进行了筛选和优化,并加上了一些更为基础和系统的入门章节,最终完成了本书的六大篇章:

第一章 算法概述介绍了算法和数据结构的相关概念,告诉大家算法是什么,数据结构又是什么,它们有哪些用途,如何分析时间复杂度,如何分析空间复杂度。第二章 数据结构基础**介绍了最基本的数据结构,包括数组、链表、栈、队列、哈希表的概念和读写操作。第三章 树介绍了树和二叉树的概念、二叉树的各种遍历方式、二叉堆和优先队列的应用。第四章 排序算法*介绍了几种典型的排序算法,包括冒泡排序、快速排序、堆排序、计数排序、桶排序。
第五章 面试中的算法介绍了 10 余道职场上流行的算法面试题及详细的解题思路。例如怎样判断链表有环、怎样计算大整数相加等。第六章 算法的实际应用*介绍了算法在职场上的一些应用,例如使用 LRU 算法来淘汰冷数据,使用 Bitmap 算法来统计用户特征等。 本书是全彩印制,书中的每一章、每一节、每一句话、每一幅图、每一行代码,都经过了小灰和编辑们的精心打磨,力求用最为直白的方式把知识讲明白、讲透彻。
漫画:什么是插入排序?

漫画:什么是插入排序?早期的漫画中存在一些叙述错误和表达不清晰的地方,小灰在本书中做了修正和补充;同时书中增加了许多全新的篇章,使得本书的内容更加系统和全面。对于渴望学习算法的小伙伴,无论你是正在学习计算机专业的学生,还是已经进入职场的新人,亦或是拥有多年工作经验却不擅长算法的老手,这本《漫画算法》都能帮助你告别对算法的恐惧,认识算法、掌握算法。扫码购买漫画:什么是插入排序?

漫画:什么是插入排序?欢迎大家加入我们的码书群,在这里你可以和技术人一起聊人生,一起聊技术,一起畅谈职场生活,因为群已满 100 人,只能添加微信号加入了哦漫画:什么是插入排序?

漫画:什么是插入排序?

来源链接:mp.weixin.qq.com