几种常见的排序算法的实现与性能分析数据结构课程设计报告

void Selectsort() //选择排序 {

int i,j,k,h; for(k=1;k<=L;k++)

printf(\getchar(); printf(\for(i=1;i<=L;i++) { h=i; }

printf(\for(i=1;i<=L;i++)

printf(\printf(\

for(j=i+1;j<=L;j++) {times++; {

R[0]=R[h];R[h]=R[i];R[i]=R[0]; } h=j;

printf(\尚未排序的数据为（回车继续）：\

if (R[j]

if(h!=j)

changes+=3; }

printf(\最终排序结果为：\

printf(\选择排序的比较次数为%d\ printf(\选择排序的比较次数为%d\ times=0; changes=0;

20

}

开始

定义临时中间变量k，并赋初值 输入要排序的一组元素

将二叉树转换成堆 i=总元素个数-1 N i<=1 Y

i--,k++ 将堆的根植和最后一个值交换

输出比较次数和移动次数 结束 21

4.27堆排序关键字比较次数和移动次数的流程图

此函数void CreateHeap(int root,int index)的程序代码如下：

void CreateHeap(int root,int index)//建堆 {

int j,temp,finish; j=2*root; temp=R[root]; finish=0;

while (j<=index&&finish==0) {

if (j

if (R[j]

j++; times++; }

if(temp>=R[j]) {

finish=1; //堆建立完成 times++; }

}

else { }

R[j/2]=R[j];//父结点=当前结点 j=j*2;

changes++;

22

}

R[j/2]=temp; //父结点=root值

void HeapSort() { }

void Heap() { int k;

printf(\尚未排序的数据为（回车继续）：\ for(k=1;k<=L;k++)

printf(\printf(\getchar(); HeapSort(); printf(\

printf(\最终排序结果为：\for(k=1;k<=L;k++)

printf(\printf(\int i,j,temp,k;

for(i=(L/2);i>=1;i--)//将二叉树转换成堆 { }

temp=R[i+1];//堆（heap）的root值和最后一个值交换 R[i+1]=R[1]; R[1]=temp; CreateHeap(1,i); CreateHeap(i,L);//建堆

for(i=L-1,k=1;i>=1;i--,k++)

changes+=3;

printf(\堆排序的比较次数为%d\ printf(\堆排序的移动次数为%d\

23