数据结构实验报告——排序

int Sort::QuickSortPatition(long int r[], int first, int end ) { int i=first; int j=end;

int temp;

while (i

{

while (i

comparetimes[3]++;

}

if (i

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

r[j]=temp;

i++;

movetimes[3]+=3;

}

while (i

{

右侧扫描

将较小记录交换到前面17

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++)

18

{

comparetimes[4]++; 在无序区中选取最小记录

if (parray[j]

index=j;

}

if (index!=i) }

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

int i;

for (i=Max2; i>=1; i--)

HeapSortSift(parray, i, Max) ; {

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

} }

return 0;

for (i=1; i

19 {

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

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

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

int i,j; i=k;

j=2*i; 置i为要筛的结点，j为i的左孩子

return 0;

while (j<=m) 筛选还没有进行到叶子 {

if (j

{

j++;

comparetimes[5]++;

比较i的左右孩子，j为较大者

}

if (parray[i]>parray[j])

20