插入排序(Insertion Sort)

在上篇文章介绍的并归排序(Merge Sort)后,再来了解下插入排序。简介插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。分类排序算法数据结构数组最差时间复杂度最优时间复杂度平均时间复杂度最差空间复杂度总共 ,需要辅助空间记载最早拥有排序概念的机器出现在1901至1904年间由Hollerith发明出使用基数排序法的分类机,此机器系统包括打孔,制表等功能,1908年分类机第一次应用于人口普查,并且在两年内完成了所有的普查数据和归档。 Hollerith在1896年创立的分类机公司的前身,为电脑制表记录公... Read More