北邮数据结构实验 第三次实验 排序

int exchange=Max; int bound,j; while(exchange) {

bound=exchange; exchange=0;

for(j=1;j

comparetimes[2]++;

if(parray[j]>parray[j+1]) {

parray[0]=parray[j]; parray[j]=parray[j+1]; parray[j+1]=parray[0]; exchange=j;

movetimes[2]+=3; } } }

return 0; }

/***********************************************************快速排**********************************************************************/ int Sort::QuickSort(long int parray[]) {

QuickSortRecursion(parray,1, Max); return 0; }

int Sort::QuickSortRecursion(long int parray[], int first=1, int end=Max) {

if (first

int pivot=QuickSortPatition(parray, first, end);

QuickSortRecursion(parray, first, pivot-1);//左侧子序列排序 QuickSortRecursion(parray, pivot+1, end); //右侧子序列排序 }

return 0; }

int Sort::QuickSortPatition(long int r[], int first, int end ) {

int i=first; int j=end; int temp;

第17页

序

while (i

while (i

j--;

comparetimes[3]++;

} //右侧扫描 if (i

temp=r[i]; //将较小记录交换到前面 r[i]=r[j]; r[j]=temp; i++;

movetimes[3]+=3; }

while (i

i++;

comparetimes[3]++;

} //左侧扫描 if (i

temp=r[j]; r[j]=r[i];

r[i]=temp; //将较大记录交换到后面 j--;

movetimes[3]+=3; } }

return i; //i为轴值记录的最终位置 }

/***********************************************************选择排**********************************************************************/ int Sort::SelectSort(long int parray[]) {

int i,j,index,temp;

for (i=1; i

index=i;

for (j=i+1; j<=Max; j++) {

comparetimes[4]++; //在无序区中选取最小记录 if (parray[j]

第18页

序

}

if (index!=i) {

temp=parray[i];

parray[i]=parray[index]; parray[index]=temp; movetimes[4]+=3; } }

return 0; }

/*************************************************************堆排序***********************************************************************/ int Sort::HeapSort(long int parray[]) {

int i;

for (i=Max/2; i>=1; i--)

HeapSortSift(parray, i, Max) ; for (i=1; i

parray[0]=parray[Max-i+1]; parray[Max-i+1]=parray[1]; parray[1]=parray[0]; movetimes[5]+=3;

HeapSortSift(parray, 1, Max-i); }

return 0; }

void Sort::HeapSortSift(long int parray[], int k, int m) {

int i,j; i=k;

j=2*i; //置i为要筛的结点，j为i的左孩子 while (j<=m) //筛选还没有进行到叶子 {

if (j

j++;

comparetimes[5]++;

} //比较i的左右孩子，j为较大者 if (parray[i]>parray[j]) {

comparetimes[5]++;

第19页

break;

} //根结点已经大于左右孩子中的较大者 else {

parray[0]=parray[i]; parray[i]=parray[j]; parray[j]=parray[0]; movetimes[5]+=3; i=j;

j=2*i; //被筛结点位于原来结点j的位置 } } }

/************************************************************归并排序*********************************************************************/ int Sort::MergeSort(long int parray[]) {

long int r1[Max+1]; int h(1);

while (h

MergePass(parray, r1, h); //归并 h=2*h;

MergePass(r1, parray, h); h=2*h; }

return 0; }

void Sort::Merge(long int parray[], long int r1[], int s, int m, int t) //一次归并 {

int i=s; int j=m+1; int k=s;

while (i<=m && j<=t) {

comparetimes[6]++; movetimes[6]++;

if (parray[i]<=parray[j]) {

第20页