文档介绍：快速排序实验报告
《程序设计实践》报告
学号江元 ;
姓名 090241111 ;
题目序号 2011年题目: ;
难度等级 B
一、题目
写出快速排序的非递归算法
二、问题分析及求解基快速排序实验报告
《程序设计实践》报告
学号江元 ;
姓名 090241111 ;
题目序号 2011年题目: ;
难度等级 B
一、题目
写出快速排序的非递归算法
二、问题分析及求解基本思路
问题分析:
快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。而在程序设计中虽然应用递归技术, 能够使得程序简洁易懂, 但是效率并不是最高的,因此可以利用栈结构实现非递归的快速排序。
求解基本思路:
将每次分治的两个序列的高位和低位入栈，每次都从栈中获取一对高位和低位，分别处理。处理过程是:选取高位作为基准位置，从低位开始向高位遍历，如果比基准元素小，那么和第i个交换，如果有交换，那么i++，等一遍遍历完成后，如果i的位置不等于基准位置，那么所选的基准位置的值不是最大的而这时候i的位置之前的元素都比基准值小，那么i的位置应该是基准值，将i所在位置的值和基准位置进行交换。这时候，在i的左右就将序列分成两部分了，一部分比i所在位置值小，一部分比i所在位置值大的，然后再次将前面一部分和后面一部分的高位和低位分别入栈，再次选择基准位置，直到所选择的区间大小小于2，就可以不用入栈了。
三、问题求解的整体框架结构
输入要排序的元素开始的个数
依次输入要排序的
元素
借助定义的栈 Stack st
传入参数，调用非递
归实现的快速排序函调用函数partition 数qsort()
调用函数swap 非递归快速排序后输结束出排序后的元素顺序
四、主要算法
1(非递归快速排序算法qsrt( a, l , r ):
由partition(pData, low, high)返回了轴值，(low); (pivot - 1);
(pivot + 1); (high);
循环执行下列语句直到栈为空
(1)high = (); (); low = (); ();
(2)若满足low < high，调用 partition(pData, low, high)返回轴值; 定义tmp = pivot -1
若low < tmp，(low);