数据结构_各种内排序性能比较_课程设计报告纯代码版

数据结构课程设计报告

题目：各种内排序性能的比较

学生姓名：

学号：

班级：

指导教师：

2012-6-10

实现部分

各个核心算法的代码：

#include

#include

using namespace std;

const int M=100;

int compareN=0,changeN=0; //快速排序中元素比较的次数和交换的次数

int compareN1=0,changeN1=0,K=0; //合并排序中元素比较的次数和交换的次数

void display(int r[], int n)

{

for(int i=0;i

{

cout.width(4);

cout<

}

cout<

}

void insertsort(int r[],int n) //直接插入法排序

//待排序元素用一个数组r表示，数组有n个元素

{

int a=0,b=0,k=1;//a表示元素比较的次数，b表示元素交换的次数,k 表示趟数

cout<<"插入排序的每一次的结果如下："<

cout<<"初始状态:";

display(r,n);

for(int i=1;i

{

int temp=r[i]; //把待排序元素赋给temp

int j=i-1;

while((j>=0)&&(temp

{

a++;

r[j+1]=r[j];j--; //顺序比较和移动

}

a++;

r[j+1]=temp;

b++;

cout<<"第"<

k++;

display(r,n);

}

cout<<"\t\t\t\t -->元素比较次数为

"<

cout<<"\t\t\t\t -->元素交换次数为"<

}

void bubblesort(int r[],int n) //冒泡排序

{

int a=0,b=0,k=1,flag=1; //当flag=0时停止排序(flag用于判断元素是否进行过交换)

cout<<"冒泡排序的每一次的结果如下："<

cout<<"初始状态:";

display(r,n);

for(int i=1;i

{

flag=0; //开始时元素未交换

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

{

a++;

if(r[j]

{

//发生逆序

int t=r[j];

r[j]=r[j-1]; //元素后移

r[j-1]=t;flag=1; //交换，并标记发生了交换

b++;

}

flag=1;

if(flag==0)break;

}

cout<<"第"<

k++;

display(r,n);

}

cout<<"\t\t\t\t -->元素比较次数为"<

cout<<"\t\t\t\t -->元素交换次数为"<

}

void selectsort(int r[],int n)//直接选择排序

{

int i,j,m,t,a=0,b=0,k=1;

cout<<"选择排序的每一次的结果如下："<

cout<<"初始状态:";

display(r,n);

for(i=0;i

{

m=i;

for(j=i+1;j

if(r[j]

{

a++;

m=j;

}

if(m!=i) //找到最小的后与前面的交换，以此类推

{

t=r[i];

r[i]=r[m];

r[m]=t;

b++;

}

cout<<"第"<

k++;

display(r,n);

}

cout<<"\t\t\t\t -->元素比较次数为"<

cout<<"\t\t\t\t -->元素交换次数为"<

}

//递归形式的快速排序

void quicksort(int r[],int left,int right,int n)//快速排序,递归调用，使用全局变量，结果在main函数中实现

{

int i=left,j=right,k=1;

int temp=r[i];

while(i

{

while((r[j]>temp)&&(j>i))//同时满足两个条件时才会执行j--,即向前移动j,并且如果没有发现r[j]中没有比temp小的则当i=j时停止{

compareN++; //compareN用于快速排序中计算元素比较的次数

j=j-1;

}

if(j>i) //r[j]中存在比temp小的值

{

r[i]=r[j];

i=i+1;