3快速排序20082374.doc

计算机算法的设计与分析实验报告一、描述 用快速排序的方法对数据进行排序。二、算法 设要排序的数组是A0AN-1，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。一趟快速排序的算法是： 1）设置两个变量I、J，排序开始的时候：I=0，J=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即 key=A0； 3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值AJ，并与AI交换； 4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的AI，与AJ交换； 5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j+完成的最后另循环结束)。三、编程#include #include time.h#include stdlib.htypedef int InfoType;#define n 150 /假设的文件长度，即待排序的记录数目typedef int KeyType; /假设的关键字类型typedef struct /记录类型 KeyType key; /关键字项 InfoType otherinfo; /其它数据项，类型InfoType依赖于具体应用而定义RecType;typedef RecType SeqListn+1; /SeqList为顺序表类型，表中第0个单元一般用作哨兵int Partition(SeqList R,int i,int j);void main() void QuickSort(SeqList R,int low,int high); int i; SeqList R;int srand=(unsigned)time(NULL); printf(随机产生欲排序的150个数：n); for (i=1;i=n;i+) Ri.key=rand()%1000+1; printf(排序前：n); for (i=1;i=n;i+) printf(%dt,Ri.key);if(i%10=0)printf(n); printf(n); QuickSort(R,1,n); printf(排序后：n); for (i=1;i=n;i+)printf(%dt,Ri.key);if(i%10=0) printf(n); printf(n);void QuickSort(SeqList R,int low,int high) /对Rlow.high快速排序 int pivotpos; /划分后的基准记录的位置 if(lowhigh) /仅当区间长度大于1时才须排序pivotpos=Partition(R,low,high); /对Rlow.high做划分 QuickSort(R,low,pivotpos-1); /对左区间递归排序 QuickSort(R,pivotpos+1,high); /对右区间递归排序int Partition(SeqList R,int i,int j)/调用Partition(R,low,high)时，对Rlow.high做划分，并返回基准记录的位置 RecType pivot=Ri; /用区间的第1个记录作为基准 while(ij) /用区间两端交替向中间扫描，直至i=j为止 while(i=pivot.key) /pivot相当于在位置i上j-; /从右向左扫描，查找第1个关键字小于pivot.key的记录Rj if(ij) /表示找到的Rj的关键字pivot.key Ri+=Rj; /相当于交换Ri和Rj，交换后i指针加1 while(ij & Ri.key=pivot.key) /pivot相当于在位置j上 i+; /从左向右扫描，查找第1个关键字大于pivot.key的记录Ri if(ipivot.key Rj-=Ri; /相当于交换Ri和Rj，交换后j指针减1 Ri=pivot; /