排序性能分析(8)

课设 排序性能分析

{

R[0]=R[j+1]; //R[0]不是哨兵仅作暂存单元 R[j+1]=R[j];

R[j]=R[0];

echange=TRUE; //发生了交换，故将交换标志置为真 }

if(!exchange) //本趟排序未发生交换，提前终止算法 return; } }

(5) 快速排序

void quicksort(SeqList R,int low,int high) {

int pivotpos; //划分后的基准记录的位置 if (low<high) {

pivopos=partition(R,low,high);

quicksort(R,low,pivotpos-1); //对左区间递归排序 quicksort(R,pivotpos+1,hidh); //对右区间递归排序 } }

int partition(SeqList R,int i, int j) {

ReceType pivot=R[i]; //用区间的第一个记录作为基准

while(i<j) //从区间两端交替向中间扫描，直至i=j为止 {

while(i<j&&R[j].key>=pivot.key)

j--; //从右向左扫描，查找第1个关键字小于pivot.key的记录R[j] if(i<j)

R[i++]=R[j]; //相当于交换R[i]和R[j],交换后i指针加1 while(i<j&&R[i].key<=pivot.key)

i++; //从左向右扫描，查找第1个关键字大于pivot.key的记录R[i] if(i<j)

R[j--]=R[i]; }