精选优质文档-倾情为你奉上实验二：用分治法查找k1-k2问题实验内容从包含n个整数的无序列表中输出第k1小到第k2小之间的所有整数，其中k1=k2。分析时间复杂度。必须用分治法求解，但是不能简单地重复使用求第k小元素的分治法。禁止使用排序算法求解给出复杂度分析过程 算法思想在解决实验的过程中参考了快速排序中双向扫描的思想。快速排序是一种基于分治技术的重要排序算法。首先选择一个元素，接下来根据该元素的值来划分数组。中轴之前的是小于中轴的数，之后的为大于中轴的数。在这个问题中我们只需要在找到中轴位K1和K2时跳出快排，输出第K1到K2的元素，便得问题的解。在寻找中轴的过程中如果遇到k2则不需要二次快排，否则再次查找中轴为k2。数据结构：顺序表算法1Quicksort(Sqlist &L,int low,int high,int k1,int k2,int &temp) /用Quicksort对子数组排序/快排到中轴为k1返回/输出：k1将数组分为k1前和k1后两部分if(lowhigh)/长度大于1
