在快速排序法中引入对相同数据的处理.pdf

在快速排序法中引入对相同数据的处理 马国华 郑州大学信息管理系，河南郑州 (450052) 摘 要: 本文在进一步研究快速排序法和位置计算法的基础上，对于待排序数据中的相同数 据作了专门处理，有效地减少了数据比较和数据交换的操作次数，从而改进了快速排序法， 提高了程序的运行效率。 关键词: 快速排序法；位置计算法；数据处理 1. 引言 [1] 快速排序法 ，其基本执行过程是:对于待排序的数据序列（存放在数组中），首先任 意选取一个数据（通常可选第一个或中间的一个数据）作为枢轴（或支点，pivot ），而后将 所有小于枢轴的元素移到枢轴之前，大于或等于枢轴的元素移到枢轴之后。对两部分重复这 一划分过程直至排序完成。 数据比较和数据移动是排序算法的基本操作。对同样的排序问题，由于快速排序法所进 行数据比较和数据移动的平均操作次数最少，从时间上平均性能优于其它各种排序方法，快 速排序法由此得名。 作者在设计“期刊文献管理信息系统(JMIS 1.0)”应用软件[2]时考虑到，对数据库建索引倒 排档时，在待排序的数据（如主题词、著者名称、期刊名称等）中存在大量的相同数据，为 此在深入研究快速排序法和位置计算法的基础上[3][4] ，本文对快速排序法提出了改进。 2. 改进算法、程序与实现过程 改进的快速排序法，其基本思想是:从待排序的数据序列中顺序选取一个数据作枢轴， 将小于枢轴的元素向前移动，大于枢轴的元素向后移动，等于枢轴的元素位置不动，而将其 下标存入一数组，这样数据序列被分为两部分；然后按等于枢轴的元素位置，对前一部分， 将小于枢轴的元素向前移动，等于枢轴的元素向后移动；对后一部分，将等于枢轴的元素向 前移动，大于枢轴的元素向后移动；一趟排序结束，排序数据被分为小于枢轴的、等于枢轴 的和大于枢轴的三个部分。对小于枢轴的和大于枢轴的两个部分重复排序过程直至完成。 该算法用 Turbo C 2.0 实现，源程序如下： #include stdio.h #include string.h #define N 10 int ly[N],cm=0,ex=0; void sort(char *dp[],int left,int right) {char *temp;int kw,k,ll,rr,bjz,t1,t2; t1=0;t2=N;ll=left;rr=right;ex++;temp=dp[ll]; do {while(rrll) {cm++;bjz=strcmp(temp,dp[rr]); if(bjz0){ex++;dp[ll]=dp[rr];ll++;break;} else if(bjz==0){t2--;ly[t2]=rr;} rr--;} while(llrr) - 1 - {cm++;bjz=strcmp(temp,dp[ll]); if(bjz0){ex++;dp[rr]=dp[ll];rr--;break;} else if(bjz==0){t1++;ly[t1]=ll;} ll++;} }while(llrr); kw=ll;rr--;ll++; for(k=1;k=t1ly[k]rr;rr--) if(ly[t1]==rr)t1--; else {ex+=2;dp[kw]=dp[ly[k]];dp[ly[k]]=dp[rr];kw=rr;k++;} for(k=N-1;k=t2ly[k]ll;ll++) if(ly[t2]==ll)t2++; else {ex+=2;dp[k