Question

插入排序有相同的时候怎么接着顺序排

Answer 1

问：插入排序有相同的时候怎么接着顺序排

答：每次将一个新数据插入到有序队列中的合适位置里 。时间复杂度 当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。 当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N2)。 所以，数据越接近正序，直接插入排序的算法性能越好。 空间复杂度 由直接插入排序算法可知，我们在排序过程中，需要一个临时变量存储要插入的值，所以空间复杂度为 1 。算法稳定性 直接插入排序的过程中，不需要改变相等数值元素的位置，所以它是稳定的算法。2.折半插入排序 时间复杂度：折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O(N2)），在减少了比较次数方面它确实相当优秀，所以该算法仍然比直接插入排序好。 空间复杂度： 折半插入排序和插入排序一样只需要一个多余的缓存数据单元来放第 i 个元素，所以空间复杂度是O（1），因为排序前2个相等的数在序列的前后位置顺序和排序后它们两个的前后位置顺序相同，所以它是一个稳定排序。 3.希尔排序 希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。 希尔排序的基本思想是：把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。 O(Nlog2N)=O(N1.3) 算法稳定性 由上文的希尔排序算法演示图即可知，希尔排序中相等数据可能会交换位置，所以希尔排序是不稳定的算法。

答：很高兴为您服务