实验周实验报告.docx

:
1冒泡:
void sort1(int *a,int n)//冒泡
{
int i,j;
int temp;
for(i=0;i<n-1;i++)
for(j=n-2;j>=i;j--)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
相邻位置进行交换,较小的排到前面,第二层循环每次将最小的数值逐渐地像冒泡一样排到第一层循环的下标为i的位置,最终实现从小到大排序。
:
void sort2(int *a,int n)//选择
{
int i,j,k;
int temp;
for(i=0;i<n-1;i++)
{
k=i;
for(j=k+1;j<n;j++)
{
if(a[k]>a[j])
{
k=j;
}
}
if(k!=i)
{
temp=a[k];
a[k]=a[i];
a[i]=temp;
}
}
}
首层循环按顺序标记第i个元素(i=1,2,3……),第二层循环找出第i个元素之后比a[i]小的最小值,并将下标赋给k,比较k与i判断a[i]是否为最小值,否则将最小值交换在a[i]处,
始终保证a[i]为最小的,实现数据从小到大排序。
3. 插入法排序:
void sort3(int *a,int n)//插入
{
int i,j,temp;
for(i=0;i<n;i++)
{
temp=a[i];
j=i-1;
while(j>=0&&temp<a[j])
{
a[j+1]=a[j];
j--;
}
a[j+1]=temp;
}
}
第一层循环按顺序找到一个数据标记,并开始找这个数据之前的比标记的数值大的数据,再将标记的数据插入到找到的数据之前(通过数组让位的方式插入数据)。

void sort4(int *a,int n)//shell
{
int i,j,temp,k;
k=n/2;
do
{
for(i=0;i<n;i+=k)
{
temp=a[i];
j=i-k;
while(j>=0&&temp<a[j])
{
a[j+k]=a[j];
j-=k;
}
a[j+k]=temp;
}
k=k/2;
}while(k>=1);
}
Shell法事实上是一种优化的选择法排序,先是在一定间距上进行排序(间隔为k),后
来不断细化,减少了插入排序算法的时间复杂度。
:
void sort5(int *a,int i,int j)//快速
{
int m,n,k,temp;
m=i;
n=j;
k=a[j];
do{
while(a[m]<k&&m<j) m++;
while(a[n]>k&&n>i) n--;
if(m<=n)
{
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n--;
}
}while(m<=n);
if(n