插入排序就是把当前待排序的元素插入到一个已经排好序的列表里面。一个非常形象的例子就是右手抓取一张扑克牌,并把它插入左手拿着的排好序的扑克里面。
,,,,,,,,插入排序的最坏运行时间是O (n2),所以并不是最优的排序算法。
,,,,,,,,如果输入数组已经是排好序的话,插入排序出现最佳情况,其运行时间是输入规模的一个线性函数。
,,,,,,,,如果输入数组是逆序排列的,将出现最坏情况。平均情况与最坏情况一样,其时间代价是Θ(n2)。
简单例子:
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
