快速排序实验报告.doc

程序设计实践报告学号 江元 ；姓名 090241111 ；题目序号 2011年题目：排序7.1B类的第5题 ；难度等级 B 一、题目写出快速排序的非递归算法二、问题分析及求解基本思路问题分析：快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。而在程序设计中虽然应用递归技术, 能够使得程序简洁易懂, 但是效率并不是最高的,因此可以利用栈结构实现非递归的快速排序。求解基本思路：将每次分治的两个序列的高位和低位入栈，每次都从栈中获取一对高位和低位，分别处理。处理过程是：选取高位作为基准位置，从低位开始向高位遍历，如果比基准元素小，那么和第i个交换，如果有交换，那么i+，等一遍遍历完成后，如果i的位置不等于基准位置，那么所选的基准位置的值不是最大的而这时候i的位置之前的元素都比基准值小，那么i的位置应该是基准值，将i所在位置的值和基准位置进行交换。这时候，在i的左右就将序列分成两部分了，一部分比i所在位置值小，一部分比i所在位置值大的，然后再次将前面一部分和后面一部分的高位和低位分别入栈，再次选择基准位置，直到所选择的区间大小小于2，就可以不用入栈了。三、问题求解的整体框架结构输入要排序的元素的个数依次输入要排序的元素传入参数，调用非递归实现的快速排序函数qsort（）开始调用函数partition结束借助定义的栈 Stack st调用函数swap非递归快速排序后输出排序后的元素顺序四、主要算法1非递归快速排序算法qsrt( a, l , r )：由partition(pData, low, high)返回了轴值，st.push(low); st.push(pivot - 1); st.push(pivot + 1); st.push(high); 循环执行下列语句直到栈为空（1）high = st.top(); st.pop(); low = st.top(); st.pop();（2）若满足low high，调用 partition(pData, low, high)返回轴值; 定义tmp = pivot -1 若low tmp，st.push(low); st.push(tmp);tmp = pivot + 1;若tmp high，st.push(tmp); st.push(high);2算法时间和空间复杂度：时间复杂度：最坏情况下时间代价为T(n)=O（n*n）,最好情况下时间代价为O（nlogn）,平均时间代价也为O（nlogn）。 空间复杂度：由于引进一个栈，这个栈的大小取决于递归调用的深度，最多不会超过n，如果每次都选较大的部分进栈，处理较短的部分，递归深度最多不超过log2n，所以需要的附加存储开销为O（log2n）。 五、测试 六、总结1. 调试过程中遇到的主要问题（1）栈的定义以及初始化上出现了错误。（2）开始并未实现动态存储，只是在程序代码中规定了要排序的代码。（3）交换函数swap开始用额外变量时出错，后来不用额外变量，直接进行交换。2. 经验和体会（1） 快速排序算法的确很快，主要是因为它在数组进行分组时不是随便划分而是尽量将原数组