跟着课本走算法导论复习（1） 插入排序

 还有一个月就要算法导论考试了，东西很多，想了想就姑且把博客当作笔记。一边打字，一边看书，一边复习。

插入排序虽然在第一章有所提到，然而具体讲解的地方是在第二章。

插入排序（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平方级

因此各种情况的时间复杂度就出来了