首页  >  文章  >  插入排序有哪些

插入排序有哪些

藏色散人
藏色散人原创
2020-06-30 09:28:572964浏览

插入排序有简单插入排序和希尔排序这两种,简单插入排序的时间复杂度是【O(N2) 稳定排序】,希尔排序的时间复杂度是【和增量序列的选取有关,非稳定排序】。

插入排序有哪些

插入排序

简单插入排序

将待排序的一组序列分为已排好序和未排序的两个部分,初始状态时,已排序序列仅包含第一个元素,未排序序列中的元素为除了第一个以外N-1个元素;此后将未排序序列中的元素逐一插入到已排序的序列中。如此往复,经过N-1次插入后,未排序序列中元素个数为0,则排序完成

时间复杂度:O(N2) 稳定排序

希尔排序

将待排序的一组元素按一定间隔分为若干个序列,分别进行插入排序。开始时设置的"间隔"较大,在每轮排序中将间隔逐步减小,直到"间隔"为1,也就是最后一步是进行简单插入排序

时间复杂度:和增量序列的选取有关 非稳定排序

以上是插入排序有哪些的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn