数据结构课程设计十种排序算法比较.doc

合肥学院
计算机科学与技术系

课程设计报告
2014 ～2015 学年第 学期

课程
数据结构与算法
课程设计名称
内部排序算法比较
学生姓名

学号

专业班级

指导教师

2015 年 1 月

【课题22、】内部排序算法比较
一、问题分析和任务定义
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
根据对本设计任务要求的理解和分析，按以下两点问题进行分析：
题目要求对十种排序算法进行比较，比较的主要内容是关键字的比较次数和移动次数，其中待排序数用。

二、数据结构的选择和概要设计
为了实现十种排序算法，产生的随机数用顺序表存储比较方便。顺序表数据类型（存储结构）描述如下：
typedef int KeyType;
struct rec
{
KeyType key;
};
typedef rec sqlist[N];
2.主程序与各模块之间的关系是：
(1) void gensort(int b[],int n)起泡排序
(2) void insertsort(sqlist b,int n)插入排序
(3) void so(sqlist num,int n)折半插入排序
(4) void shellsort(sqlist b,int n)希尔排序
(5) void gentsort(int b[],int n)选择排序
(6) void output(sqlist b,int n)快速排序
(7) void sort3(sqlist nu,int n) //2-路插入排序
(8) void Merge(sqlist a, sqlist b, int low, int mid, int high)二路归并排序
(9) void MergePass(sqlist a, sqlist b, int n, int lenth)一趟归并排序
(10) void MergeSort(sqlist a, int n) //进行二路归并
(11) void sift(sqlist r,int s,int m) 堆排序
(12) void init(int a[])//随机生成N个整数

三、详细设计和编码
在整个课程设计中，要求实现要求的功能，必须要有主函数，并通过主函数调用各功能子模块，以上展示各个模块的功能，以下将分析主函数和各个模块中的具体算法和实现。
1.起泡排序函数的实现
函数声明：void gensort(int b[],int n)
起泡排序的基本思想是将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行比较为止。起泡排序是一种稳定的排序方法，在随机产生数的情况下，总的时间复杂度为O(n2)。

2. 选择排序函数的实现
函数声明：void gentsort(int b[],int n)
选择排序法的基本思想是：第i趟排序通过n-i次关键码的比较，在n-1+i
(1 <= i <= n-1)个记录中选取关键码最小的记录，并和第i个记录交换作为有序序列的第i个记录。选择排序是一种稳定的排序方法，总的时间复杂度是O(n2)。
3. 插入排序函数的实现
函数声明：void insertsort(sqlist b,int n)
直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入到排好序的有序表中，直到无序区中没有记录为止，从而得到一个新的有序表。直接插入排序是一种稳定的排序方法，其时间复杂度为O(n)。
4. 希尔排序函数的实现
函数声明：void shellsort(sqlist b,int n)
希尔排序又称增量缩小排序，基本思想是先将序列按增量划分为元素个数相同的若干子序列，在子序列内分别进行直接插入排序，然后不断缩小增量直至为1，最后使用直接插入排序法完成排序。
5. 折半插入排序函数的实现
函数声明：void Dichotomy(int a[],int n)；
二分排序法的基本思想是：在插入第i个元素时，对前面的0～(i-1)个元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半元素进行折半，直到left>right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。
6. 快速排序函数的实现
函数声明：void output(sqlist b,int n)//输出元素值
首先选一个轴值（即比较的基准），将待排序记录分割成独立的两部分，左侧记录的关键码均小于或等于轴值，右侧记录的关键码均大于或等于轴值，然后分别对这两部分重复上述过程，直到整个序列有序。快速排序是一种不稳定的排序方法，时间复杂度为O（nlog2n）
7. 堆排序函数的实现
函数声明：void sift(sqlist r,int s,int m)
首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它们从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，依此类推，直到堆中只有一个记录为止。堆排序是一种不稳定的排序方法，总的时间复杂度为O(nlog2n)。
8.二路归并排序函数的实现
函数声明：void Merge(sqlist a, sqlist b, int low, int mid, int high)
void MergePass(sqlist a, sqlist b, int n, int lenth)
void MergeSort(sqlist a, int n)
合并排序：这里的合并排序和下边要描述的快速排序都采用了分而治之的思想，但两者仍然有很大差异。合并排序是将一个无序数组n[1…r]分成两个数组n[1…r/2]与n[r/2+1…r]，分别对这两个小数组进行合并排序，然后再将这两个数组合并成一个大数组。由此我们看出合并排序时一个递归过程（非递归合并排序这里不做讨论）。合并排序的主要工作便是“合并”，两个小规模数组合并成大的，两个大的再合并成更大的，当然元素比较式在合并的过程中进行的。

9.2-路插入函数的实现
9.2-路插入排序是在折半插入排序的基础上发展。其目的是减少排序过程中记录移动的次数，但为此需要n个记录的辅助空间。具体做法是：另设一个和L.r同类型的数组d，首先将L.r[1]赋值给的d[1],将d[1]看成是排好序的序列中处与中间位置的记录，然后从L.r中第2个记录起依次插入到的d[1]之前或之后的有序序列中。先将待排序记录的关键字和d[1]的关键字比较，若L.r[i].key<d[1].key,则将L.r[i]插入到d[1]之前的有序表中。反之，将L.r[i]插入到d[i]之后的有序表中。在实现算法时，将d看成一个循环向量，并将两个指针first和final分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在d中的位置。
四、上机调试过程
测试结果:

2 结果分析
实验结果与我们对这十种种算法的性能理论分析基本吻合：插入排序与冒泡排序的时间复杂度为O(n*n)，而后三种排序算法的时间复杂度为O(nlogn)。实验结果还显示出虽然冒泡排序和插入排序的时间复杂度相同，但插入排序的性能仍然比冒泡排序好，尤其在排序时间方面。

七、参考文献
[1] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。
[2] 王立柱，C语言与数据结构.北京：清华大学出版社，2003年6月第1版。
八、附录
以上是对本设计的实现功能和算法等的全面分析，以下是带注释的源代码算法
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#define N 100
int p,q;
int g=0;int h=0;
//起泡排序
void gensort(int b[],int n)
{
int i,j;int s=0,t=0;
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
t++;
if(b[i]>b[j])
{
int temp=b[i];
b[i]=b[j];
b[j]=temp;
s+=3;
}}}
cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;
}

//插入排序
typedef int KeyType;

struct rec
{
KeyType key;
};
typedef rec sqlist[N];

void insertsort(sqlist b,int n)
{
int i,j;int s=0,t=0;
for(i=2;i<n;i++)
{
b[0].key=b[i].key;
s++;
j=i-1;
t++;
while(b[0].key<b[j].key)
{
b[j+1]=b[j];
j--;
s++;
t++;
}
b[j+1]=b[0];
s++;
}
cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;
}
//折半插入排序
void so(sqlist num,int n)

{
int s=0;
int low,high,m;//分别指向低、高、中的位置

int i,j,k=0,t;//i,j循环 k交换次数 t哨兵

for(i=1;i<n;i++)

{

t=num[i].key ;

low=0;high=i-1;

while(low<=high)

{

m=(low+high)/2;

if(t<num[m].key)
{high=m-1;
k++;}
else low=m+1;

}

for(j=i-1;j>=high+1;j--)

{

num[j+1].key=num[j].key;

s++;

}

num[high+1].key=t;

}

cout<<"移动次数="<<s<<","<<"比较次数="<<k<<endl;

}

//希尔排序
void shellsort(sqlist b,int n)
{
int i,j,gap;
rec x;
int s=0,t=0;
gap=n/2;
while(gap>0)
{
for(i=gap+1;i<n;i++)
{
j=i-gap;
while(j>0)
{
t++;
if(b[j].key>b[j+gap].key)
{
x=b[j];b[j]=b[j+gap];
b[j+gap]=x;j=j-gap;
s+=3;
}
else j=0;
gap=gap/2;
}}
cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;
}}

//选择排序
void gentsort(int b[],int n)
{
int i,j,k;
int s=0,t=0;
for(i=0;i<n-1;i++)
{
k=i;
for(j=i+1;j<n;j++)
{
t++;
if(b[k]>b[j])
{k=j;}
}
if(k!=i)
{int temp=b[k];
b[k]=b[i];
b[i]=temp;
s+=3;
}}
cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;
}

//快速排序
void output(sqlist b,int n)//输出元素值
{
for(int i=0;i<n;i++)
cout<<setw(4)<<b[i].key;
cout<<endl;
}

void display(int n,int m)//输出计数
{
cout<<"移动次数="<<n<<","<<"比较次数="<<m<<endl;
}

void BeforeSort()//初始化计数器
{
p=0;q=0;
}
void quicksort(sqlist r,int s,int t)
{
int i=s,j=t;
if(s<t)
{
r[0]=r[s];p++;
while(i<j)
{
p++;
while(i<j&&r[j].key>=r[0].key)
j--;
r[i]=r[j];
q++;
p++;
p++;
while(i<j&&r[i].key<=r[0].key)
i++;
r[j]=r[i];q++;p++;
}
r[i]=r[0];p++;
}
else return;
quicksort(r,s,j-1);
quicksort(r,j+1,t);
}
void sort(sqlist r,int s,int t)
{
BeforeSort();
quicksort(r,s,t);
display(p,q);
}

//2-路插入排序

void sort3(sqlist nu,int n)

{//int max=n;
#define max 20

int first,final;//头尾指针

int cache[max+1];//中转站

int i,j,s=0;//i,j循环变量 k计数器
int t=0;
for(i=0;i<n;i++)

{

if(0==i)

{

first=0;

final=0;

cache[0]=nu[0].key;

}

else

{

if(nu[i].key>=cache[final])

{t++;

final++;

cache[final]=nu[i].key;

s++;

}

else if(nu[i].key<=cache[first])

{t++;

if(first==0)first=n;

first--;

cache[first]=nu[i].key;

s++;

}

else

{ t++;

for(j=first;nu[i].key>cache[j];)

{

if(0==j)

cache[n-1]=cache[0];

else

cache[j-1]=cache[j];

s++;j++;

if(j==n)j=0;

}

if(0==first)first=n-1;

else first--;

if(0==j)j=n;

cache[j-1]=nu[i].key;

s++;

}

}

}

for(i=first,j=0;j<n;j++)

{

nu[j].key=cache[i];

i++;

if(i==n)i=0;

}

cout<<"移动次数="<<s<<","<<"比较次数="<<t<<endl;

}
//二路归并
void Merge(sqlist a, sqlist b, int low, int mid, int high)
{

int i= low, j = mid + 1,k = low;
while ((i <= mid) && (j <= high))
{

if(a[i].key <= a[j].key)
{
h++;
b[k++] = a[i++];
g++;
++i;

}
else
{
h++;
b[k++] = a[j++];
g++;

++j;

}
++k;
}
// if(i <= mid)
while(i <= mid)
{ b[k++] = a[i++];
g++;

}
//else
while(j <= high)
{ b[k++]=a[j++];
g++;

}

}
//进行一趟归并
void MergePass(sqlist a, sqlist b, int n, int lenth)
{

int i = 0, k=0;
while(i <= n - 2*lenth)
{
Merge(a, b, i, i + lenth -1, i + 2*lenth -1);
i += 2*lenth;

}
if(i < n - lenth )
{
Merge(a, b, i, i + lenth -1, n-1);
}
else
for(k = i; k <= n-1; k++)
{b[k] = a[k];
g++;

}

}
//进行二路归并
void MergeSort(sqlist a, int n)
{sqlist b;

//int* b=(int*)malloc(n*sizeof(int));
int lenth = 1;
while(lenth < n/2+1)
{
MergePass(a, b,n, lenth);
lenth = 2*lenth;
MergePass(b, a, n, lenth);
lenth = 2*lenth;

}
cout<<"移动次数="<<g<<","<<"比较次数="<<h<<endl;

}

//堆排序
void sift(sqlist r,int s,int m)
{
int j;
rec x;
x=r[s];
for(j=2*s;j<=m;j*=2)
{q++;
if(j<m&&(r[j].key<r[j+1].key))
++j;
q++;
if(!(x.key<r[j].key)) break;
r[s]=r[j];s=j;p++;}
r[s]=x;p++;
}
void heapsort(sqlist &r,int m)
{
int i;rec w;
for(i=m/2;i>0;--i)
sift(r,i,m);
for(i=m;i>1;--i)
{
w=r[i];r[i]=r[1];
r[1]=w;
p+=3;
sift(r,1,i-1);
}
}
void sorting(sqlist &r,int t)
{
BeforeSort();
heapsort(r,t);
display(p,q);
}

void init(int a[])//随机生成N个整数并
{
int i;
//#define N 100;
srand ( ( unsigned int ) time ( NULL ) );
for(i=0;i<N;i++)
a[i]=rand()%99+1;
}

void main()

{
int g=0;
int h=0;

int a1[N],i;
int e=N;
sqlist a,b,c,d,num,R,nu,a2,b2;
int c1[N];
int low=0,high=10;
int dat[N];

init(a1);//随机产生个数
for(i=0;i<N;i++)
{
c1[i]=a1[i];
a[i].key=a1[i];
b[i].key=a1[i];
c[i].key=a1[i];
d[i].key=a1[i];
num[i].key=a1[i];
R[i].key=a1[i];
nu[i].key=a1[i];
dat[i]=a1[i];

}
cout<<"排序前数组:\n";
for(i=0;i<N;i++)
cout<<setw(4)<<a1[i];
cout<<endl;
cout<<"起泡排序运行结果:\n";
gensort(a1,sizeof(a1)/sizeof(int));
cout<<"插入排序运行结果:\n";
insertsort(a,N);
cout<<"希尔排序运行结果:\n";
shellsort(b,N);
cout<<"选择排序运行结果:\n";
gentsort(c1,N);

cout<<"快速排序运行结果:\n";
sort(c,low,high);
cout<<"堆排序运行结果:\n";
sorting(d,N);
cout<<"折半插入排序运行结果:\n";
so(num,N);
cout<<"二路插入排序运行结果:\n";
sort3( nu, N);
cout<<"二路归并的排序结果\n";
MergeSort(a2,N);
cout<<"基数排序的排序结果\n";

}