登录 主页

插入排序(InsertionSort)

2023-03-22 06:01PM

概念:

插入排序也被称为直接插入排序,适用于少量的元素排序

插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增 1 的有序表 { 将一个记录插入到已排好序的序列中,从而得到一个新的有序序列(将序列的第一个数据看成是一个有序的子序列,然后从第二个记录逐个向该有序的子序列进行有序的插入,直至整个序列有序)}

在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素内层循环当前元素前面有序表进行待插入位置查找,并进行移动

算法分析: 1.当初始序列为正序时,只需要外循环n-1次,每次进行一次比较,无需移动元素。此时比较次(Cmin)和移动次数(Mmin)达到最小值。

Cmin=n-1

Mmin=0

此时时间复杂度为O(n)

2.当初始序列为反序时,需要外循环n-1次,每次排序中待插入的元素都要和[0,i-1]中的i个元素进行比较且要将这i个元素后移i次,加上tmp=arr[i]与arr[j]=temp的两次移动,每趟移动次数为i+2,此时比较次数和移动次数达到最大值

Cmax = 1+2+...+(n-1) = n(n-1)/2 = O(n^2)

Mmax=(1+2)+(2+2)+...+(n-1+2) = (n+1)(n+4)/2 = O(n^2)

此时时间复杂度为O(n)

3.在直接插入排序中只使用了i,j,tmp这三个辅助元素,与问题规模无关,空间复杂度为 O(1)

4.相同元素的相对位置不变,如果两个元素相同,插入元素放在相同元素后面。是一种稳定排序

图示:

go实例代码:

方法一:

结果:

方法二:

结果:

参考:https://www.jianshu.com/p/7cf0656e76dd

返回>>

登录

请登录后再发表评论。

评论列表:

目前还没有人发表评论