实验，测试线性有序表的插入效率

本次实验测试了线性表的各种数据结构实现和操作算法的实际效率
一共进行了两次测试，结果如下:

数据容量=10000
现在使用动态链表
The running time was: 390 MS

现在使用静态链表
The running time was: 140 MS

现在使用二分插入(mem函数移动数组)
The running time was: 46 MS

现在使用二分插入(循环移动数组)
The running time was: 125 MS

现在使用直接读入+快速排序
The running time was: 0 MS

对照组:直接读入
The running time was: 0 MS

数据容量=20000
现在使用动态链表
The running time was: 6796 MS

现在使用静态链表
The running time was: 1546 MS

现在使用二分插入(mem函数移动数组)
The running time was: 156 MS

现在使用二分插入(循环移动数组)
The running time was: 500 MS

现在使用直接读入+快速排序
The running time was: 16 MS

对照组:直接读入
The running time was: 15 MS

当然在在不同的测试情况下时间可能有稍许改变.
从复杂度的角度来分析:
对照组直接读入的复杂度最低，为O(N);
快排的复杂度为O(NlogN)
二分插入,查找复杂度为logN,插入复杂度可以算作N,要插入N次,所以应该是O(N^2)
链表插入,查找复杂度为N,插入复杂度为1,故为O(N^2)

咋看按照复杂度分析的角度来看二分插入和连表插入所需要的时间应该差不多，但是实际情况却不是这样，
那么这是为什么呢？其实复杂度分析应该没有错，只是3N^2和N^2都算N^2，虽然复杂度相同，但是因为
具体的实现而相差整数倍是很正常的

再比较两组数据,对于链表，虽然复杂度是O(N^2)，但是运行时间却不是4倍关系,数据量=20000的效率明显慢了许多，这是为什么呢？
再看二分，差不多是4倍关系.我猜想是链表的复杂度不能算为O(N^2)?好象不可能啊。这个问题待解决.

本次实验的启示:
考虑时间效率:
利用线性的有序结构,二分插入排序法比连表法更快,而二分中使用高效库函数也显得重要了,静态链表比动态的效率要高.
如果需要最后得到一个有序序列而不是中间一直维护一个有序序列,先读入再排序的效率更高.

经过网友提醒，发现随机数据应该多次测取平均，于是又测试了一下，数据如下：

Test[0]=动态链表
Test[1]=静态链表
Test[2]=二分插入(mem函数移动数组)
Test[3]=二分插入(循环移动数组
Test[4]=直接读入+快速排序
Test[5]=对照组:直接读入
The number of data is 10000
test[0]: running time = 388
test[1]: running time = 165
test[2]: running time = 46
test[3]: running time = 124
test[4]: running time = 7
test[5]: running time = 9

The number of data is 15000
test[0]: running time = 2705
test[1]: running time = 435
test[2]: running time = 84
test[3]: running time = 288
test[4]: running time = 10
test[5]: running time = 9

The number of data is 20000
test[0]: running time = 8410
test[1]: running time = 1763
test[2]: running time = 165
test[3]: running time = 560
test[4]: running time = 32
test[5]: running time = 16

依然存在链表复杂度和实际情况不对应的问题..

相关代码程序: