北邮数据结构实验报告-排序

化，不论是效率还是结构优化，都需要精心设计。 3.改进

本程序代码设计时运用了递归的调用方式，效率还可以通过将其转换为栈模拟的方式得以提高。另外还可以进一步考虑算法时间的精确统计，以便从时间角度比较这几种排序算法的优劣。

完整源代码

#include using namespace std;

void Insertsort(int r[],int n,int* compare,int* move); void ShellInsert(int r[],int n,int* compare,int* move); void Bubblesort(int r[],int n,int* compare,int* move); int Partion(int r[],int first,int end,int* compare,int* move); void Qsort(int r[],int i,int j,int* compare,int* move); void Selectsort(int r[],int n,int* compare,int* move);

void Insertsort(int r[],int n,int* compare,int* move)//插入排序 {

*compare=0; { } }

void ShellInsert(int r[],int n,int* compare,int* move)//希尔排序 {

int x=r[i];

for(j=i-1;x=0;j--) { }

if(j>=0) (*compare)++; r[j+1]=x;

(*move)++; r[j+1]=r[j]; *move=0; int i; int j;

for(i=1;i

(*compare)++;

*compare=0; {

for(int i=d;i<=n-1;i++)//从a[d]往后逐个元素确定是否需要前移 { } } }

void Bubblesort(int r[],int n,int* compare,int* move)//交换（冒泡）排序 { {

for(int i=n-1;i>j;i--) {

if(r[i]

(*compare)++; (*move)+=3; *compare=0; *move=0; int x;

if(r[i]

int x=r[i];

for(j=i-d;(j>=0)&&(x

(*compare)++; (*compare)++; (*move)++; r[j+d]=r[j];

*move=0; int j;

for(int d=n/2;d>=1;d=d/2)//间距越来越小

if(j>=0) r[j+d]=x; }

else (*compare)++;

for(int j=0;j

x=r[i]; r[i]=r[i-1]; r[i-1]=x; } }

else (*compare)++; }

}

int Partion(int r[],int first,int end,int* compare,int* move)//快速排序中的轴定位 { int i=first; int j=end;

int zhou=r[i];//默认第一个元素为轴 while(i

if(i

(*compare)++; (*compare)++; i++;

while((i=zhou)) //查看右侧元素与轴的大小关系 { } if(i

(*compare)++; (*move)++; }

while((i

(*compare)++; j--;

r[i]=r[j];//发现轴右侧的某数比轴值小，将其前置

(*move)++;

r[j]=r[i];//发现轴左侧的某数比轴值小，将其后置

} }

r[i]=zhou;//最后确定轴的位置 return i; }

void Qsort(int r[],int i,int j,int* compare,int* move)//快速排序 { if(i

int centre=Partion(r,i,j,compare,move); Qsort(r,i,centre-1,compare,move); Qsort(r,centre+1,j,compare,move); }

}

void Selectsort(int r[],int n,int* compare,int* move)//选择排序 { {

int min=i;

for(int j=i+1;j

(*compare)++;

if(r[j]

(*move)+=3; int Min; Min=r[min]; r[min]=r[i]; r[i]=Min; } } }

void main() { int i;

int compare=0; int move=0;

cout<<\请您先输入一个正序数组哦\int n;

cout<<\请输入数组中含有的元素数量：\cin>>n; int *r=new int[n];

cout<<\请输入数组中的元素：\for(i=0;i>r[i]; int *a=new int[n]; for(i=0;i

*compare=0; *move=0;

for(int i=0;i