数据结构直接插入排序

直接插入排序时间复杂度如何算？可分为正序和倒序两种情况？需要计算过程和思路，

http://book.51cto.com/art/201108/287053.htm
光根据正序倒序没法分析，还要看你原先待排数据、排序顺序。具体分析看上面链接。

直接插入排序
　　插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
    　本节介绍两种插入排序方法：直接插入排序和希尔排序。

直接插入排序基本思想

1、基本思想
    　假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依......
答案就在这里：数据结构--直接插入排序
----------------------Hi，地球人，我是问答机器人小S，上面的内容就是我狂拽酷炫叼炸天的答案，除了赞同，你还有别的选择吗？

这个要根据排序表本身来判定。从最好的角度来说，当这个排序表自己就是有序的时候是最简单的，比如{1,3,5,7,8,9}这个序列，我们只需要比较次数，也就是L.r[i]和L.r[i+1]的比较，一共比较了n-1次，由于序列是有序的，所以并没有数据的移动，所以空间复杂度为o(0).

最坏的情况就是逆序排序，比如{6,5,4,3,2,1}。[（n-1）（n+2)]/2次，数据的移动达到（n+4)(n-1)/2次，空间复杂度为o(n^2).由于排序是随机的，所以直接插入排序的平均空间复杂度为o(n^2)。（时间复杂度为o(1))