本文主要是介绍插入排序—直接插入排序(Straight Insertion Sort),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
基本思想:
将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。
要点:设立哨兵,作为临时存储和判断数组边界之用。
直接插入排序示例:
如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
算法的实现:
def insertSort(alist):for i in range(1, len(alist)):if alist[i] < alist[i-1]: #如果第i个元素大于第i-1个元素, 则不用改变位置, 否则在前i-1个元素中寻找插入的位置x = alist[i]j = i - 1while alist[j] > x and j >= 0:#当前元素大于x, 后移1位alist[j+1] = alist[j]j -= 1alist[j+1] = x #当前元素小于等于x, 或者j=-1时, 找到x的插入位置return alist
算法的复杂度:
当问题规模为n时
最好情况(原本就是有序的)
比较次数:Cmin=n-1
移动次数:Mmin=0
最差情况(逆序)
比较次数:Cmax=2+3+4+……+n=(n+2)n/2
移动次数:Mmax=1+2+3+……+n-1=n*n/2
若待排序对象序列中出现各种可能排列的概率相同,则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键字比较次数和对象移动次数约为 n^2/4。因此,直接插入排序的时间复杂度为 o(n^2)。
另外直接插入排序是一种稳定的排序方法。
这篇关于插入排序—直接插入排序(Straight Insertion Sort)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!