算法导论第1次复习和实践：插入排序和归并排序

是否具备深厚的数据结构与算法的知识储备？这正是区分一名资深程序员与初学者的关键特征之一。即便借助现代计算技术，在无需深入掌握复杂的算法理论的情况下仍可完成基本任务。然而若掌握了扎实的数据结构与算法原理后，在实际应用中能够解决更多问题，并显著提升逻辑思维能力。在大学期间系统学习了《数据结构与算法》课程后由于缺乏系统的编程训练，在实际编码过程中需要参考课本中的伪代码进行辅助开发。工作后几年时间里遗忘了大部分内容如今渴望重新捡起以便通过记录实践过程来加深理解和巩固记忆

文章目录

• • 插入排序
  • 归并排序

通过比较排序算法的时间复杂度及其在实际处理相同规模问题时所需的时间可以看出，在面对大量数据时, 一台高性能计算机A采用插入排序可能需要几个小时才能完成任务, 相比之下, 一台普通性能计算机B采用归并排序仅需数秒即可完成计算任务, 显著差距一目了然. 当处理的数据量逐渐增大时, 归并排序相较于插入排序展现出显著的优势. 因此由此可见, 算法的设计对于处理大规模问题至关重要.

插入排序

通过在玩扑克时摸牌的过程可以直观地理解插入排序。每次从牌堆中抽出一张牌，并一边从右向左比较每张牌的大小。随后将其插入到第一张比它小的那张牌之后的位置。这一系列操作确保手里的所有卡片最终都会被正确排列。

如图所示，在书中对插入排序的实现过程进行了形象化的阐述：插入