还有一个月就要算法导论考试了，东西很多，想了想就姑且把博客当作笔记。一边打字，一边看书，一边复习。
插入排序虽然在第一章有所提到，然而具体讲解的地方是在第二章。
插入排序（INSERTION-SORT)**时间复杂度：平均： O( n2） 最坏： O(n) 最好：O( n2）
空间复杂度：O(1)（因为不需要辅助数组存储数据）
插入排序思路（结果从小到大）（个人理解）：
从第二个元素起，当前元素与前一个元素进行比较。如果比前一个元素小，就两个元素值相互交换，然后继续向前比较，直到该元素比前一个元素大为止。（有一点冒泡排序的感觉。。。）之后，第三个元素起，执行上述过程，随后，直到最后一个元素比较完成，排序结束。
伪代码：
INSERTION-SORT(A)
for j=2 to A.length
key=A[i]
i=j-1
while i>0
and
A[i]>key
A[i+1]=A[i]
i=i-1
A[i+1]=key
代码（主体代码）
for(int j=0;j<x;j++)
{
int key=a[j];
int k=j-1;
while(k>0&&a[k]>key)
{
a[k+1]=a[k];
k=k-1;
a[k+1]=key;
}
}
算法分析：
要计算插入排序的时间复杂度，就是通过得到每条语句的执行时间算总时间
平均情况：
最佳情况（输入数组已排好序，所以该算法是受输入序列影响的）分析
其中，最坏情况可以用 an2+bn+c 表示，也就是n平方级
最好情况是线性的，也就是n级
平均情况，由于其中有求和，而且涉及到n，所以也是n平方级
因此各种情况的时间复杂度就出来了
网友评论