中科大软件工程算法实验1.cpp

这是算法导论第一次实验代码,题目:当输入数据已经“几乎有序时”,插入排序很快,在实际应用中,我们可以利用这一特点来提高快速排序的速度。当对一个长度小于k的子数组调用快速排序时,让它不做任何排序就返回。当上一层的快速排序调用返回后,对整个数组运行插入排序完成排序过程。证明:这一排序算法的期望时间复杂度为O(nk+nlg(n/k)).