在桥牌游戏中,为每个人派发13张牌,牌的正面朝下。一种排列手中牌的方法是,一次挑出一张牌来,然后插入到适当的位置。需要保持的一个特征是手中的牌必须按照花色和大小排好序。首先拿出一张牌抓在手中,这时候手中的牌是(平凡)有序的。然后对于每一张拿到的牌,找到合适的位置并且插入,这样就保证了手上的牌是有序的状态。当所有的牌都拿到之后,这个特征仍然不变,这就是算法如何工作的。当牌在你手上时,在合适的位置插入一张牌是一件非常容易的事情,因为其他的牌只需要移出一个位置即可。当数据集合存储在内存中时,排序算法就必须做更多的工作来移动数据,以使得能够留出一个位置来给插入的元素。
图4-6的伪代码描述了插入排序反复地调用insert helper函数来确保A[0,i]是严格有序的,最后,i到达了最右的元素,会对整个A排序。图4-7描绘了插入排序是如何在运行在一个无序的小数据集A上的,A的大小为16。接下来的15行阐述了每一次插入之后A的状态。pos从1增长到n-1的过程中,算法不断将A[pos]插入到不断增长的有序区域A[0,pos](这个区域被用粗体竖线隔开)的正确位置,最后A成为一个有序序列。灰色的元素被移到右边确保为即将插入的元素腾出位置,总体来说,插入排序执行了60次移位(一次将一个元素移动一个位置)。
图 4-6 插入排序详解 图 4-7 插入排序在小数据集上的执行过程使用环境
如果你有小规模数据需要排序,并且初始数据几乎是有序的,这个时候可以使用插入排序。什么样的数据集是小规模的,这个根据编程语言和机器的不同而存在不同的答案。事实上,元素的类型也是很重要的。