福建农林大学计算机与信息学院实验报告
排序与基本算法
一、 实验目的和要求
1) 深刻理解排序的定义和各种排序方法的特点，并能灵活运用。
2) 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。
3) 了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。
二、 实验内容和原理
实验内容：
实现奇偶交换排序
三、 实验环境
Windows XP系统
visual c++6.0
四、 算法描述及实验步骤
#include "stdio.h"
void changesort(int a[],int n)
{int flag=1,temp,i;
while(flag)
{flag=0;
for(i=1;i<n-1;i+=2)
if(a[i]>a[i+1])
{temp=a[i];
a[i+1]=temp;
flag=1;
}
for(i=0;i<n-1;i+=2)
if(a[i]>a[i+1])
{temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
flag=1;
}
}
}
main()
{int a[100],n,i;
printf("please input the number of the data you want to sort:");
scanf("%d",&n);
for(i=0;i<1;i++)
scanf("%d",&a[i]);
changesort(a,n);
for(i=0;i<n;i++)
printf("%d ",a[i]);
}
五、 调试过程
六、 实验结果
七、 总结
（1）深刻理解排序的定义和各种排序方法的特点，并能灵活运用。
（2）掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。
（3）了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的性能的分析方法。
第二篇：数据结构实验报告--用简单数组实现下面各种排序算法
数据结构实验报告
实验名称： 实验4——用简单数组实现排序
日 期： 20##年12月6日
1．实验要求
使用简单数组实现下面各种排序算法，并进行比较。
排序算法：
1、插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、简单选择排序
6、堆排序（选作）
7、归并排序（选作）
8、基数排序（选作）
9、其他
要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）
4、对2和3的结果进行分析，验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性
2. 程序分析
2.1 存储结构
数组：
数组下标： 0 1 2 3 4 5 6
2.2 关键算法分析
快速排序为代码：
1．将i 和j分别指向待排序区域的最左侧记录和最右侧记录的位置；
2．重复下述过程，直到i=j
2.1右侧扫描，直到记录j的关键码小于基准记录的关键码；
2.2 如果i<j，则将r[j]与r[i]交换，并将i++；
2.3左侧扫描，直到记录i的关键码大于基准记录的关键码；
2.4 如果i<j，则将r[i]与r[j]交换，并将j--；
3．退出循环，说明i和j指向了基准记录所在位置，返回该位置；
直接顺序排序
void InsertSort(int r[], int n)
{ int ay=0;int ab=0;
for (int i=2; i<n; i++)
{ ab++;
r[0]=r[i]; //设置哨兵
for (int j=i-1; r[0]<r[j]; j--) //寻找插入位置
r[j+1]=r[j]; //记录后移
r[j+1]=r[0];
ay++;
}
for(int k=1;k<n;k++)//循环输出数据
cout<<r[k]<<" ";
cout<<"\n";
cout<<"关键字移动次数："<<3*ay<<endl;
cout<<"关键字比较次数："<<ab<<endl;
}
希尔排序
void ShellSort(int r[], int n)
{ int by=0;int bb=0;
int i;
int d;
int j;
for (d=n/2; d>=1; d=d/2) //以增量为d进行直接插入排序
{
for (i=d+1; i<n; i++)
{ bb++;
r[0]=r[i]; //暂存被插入记录
for (j=i-d; j>0 && r[0]<r[j]; j=j-d)
r[j+d]=r[j]; //记录后移d个位置
r[j+d]=r[0];
by++;
}
}
for(i=1;i<n;i++)//循环输出数据
cout<<r[i]<<" ";
cout<<"\n";
cout<<"关键字移动次数："<<3*by<<endl;
cout<<"关键字比较次数："<<bb<<endl;
}
起泡排序
void BubbleSort(int r[], int n)
{int cy=0;int cb=0;
int temp;
int exchange;
int bound;
exchange=n-1; //第一趟起泡排序的范围是r[0]到r[n-1]
while (exchange) //仅当上一趟排序有记录交换才进行本趟排序
{ cb++;
bound=exchange;
exchange=0;
for (int j=0; j<bound; j++) //一趟起泡排序
if (r[j]>r[j+1])
{
temp=r[j];
r[j]=r[j+1];
r[j+1]=temp;
exchange=j; //记录每一次发生记录交换的位置
cy++;
}
}
for(int i=0;i<n;i++)//循环输出数据
cout<<r[i]<<" ";
cout<<"\n";
cout<<"关键字移动次数："<<3*cy<<endl;
cout<<"关键字比较次数："<<(2*n-1-cb)*cb/2<<endl;
}
快速排序一次划分
int Partition(int r[], int first, int end)
{
int i=first; //初始化
int j=end;
int temp;
while (i<j)
{
while (i<j && r[i]<= r[j])
j--; db++; //右侧扫描
if (i<j)
{
temp=r[i]; //将较小记录交换到前面
r[i]=r[j];
r[j]=temp;
i++; dy++;
}
while (i<j && r[i]<= r[j])
i++; db++; //左侧扫描
if (i<j)
{
temp=r[j];
r[j]=r[i];
r[i]=temp; //将较大记录交换到后面
j--; dy++;
}
}
return i; //i为轴值记录的最终位
}
//快速排序
void QuickSort(int r[], int first, int end)
{
if (first<end)
{ //递归结束
int pivot=Partition(r, first, end); //一次划分
QuickSort(r, first, pivot-1);//递归地对左侧子序列进行快速排序
QuickSort(r, pivot+1, end); //递归地对右侧子序列进行快速排序
}
}
简单选择排序
void SelectSort(int r[ ], int n)
{ int ey=0,eb=0;
int i;
int j;
int index;
int temp;
for (i=0; i<n-1; i++) //对n个记录进行n-1趟简单选择排序
{ eb++;
index=i;
for (j=i+1; j<n; j++) //在无序区中选取最小记录
if (r[j]<r[index])
index=j;
if (index!=i)
{
temp=r[i];
r[i]=r[index];
r[index]=temp;
ey++;
}
}
for(i=0;i<n;i++)
cout<<r[i]<<" ";
cout<<"\n";
cout<<"关键字移动次数："<<3*ey<<endl;
cout<<"关键字比较次数："<<eb*(eb+1)/2<<endl;}
3. 程序运行结果
平均情况下快速排序为最优排序
4总结
排序过程通常要进行下列两种基本操作1.关键码之间的比较2.移动;记录从一个位置移动到另一个位置。所以在待排序的个数一定的情况下，算法的执行时间主要消耗在关键码之间的比较和记录的移动上，因此高效率的算法应该尽可能少的关键码比较次数和记录的移动次数。评价排序算法的另一个主要指标是执行算法所需要的辅助存储空间