首页 > 代码库 > 数据结构-实验六 排序
数据结构-实验六 排序
实验六 排序
l 实验目的
1、排序的基本概念
1.掌握在数组上进行各种排序的方法和算法。
2.深刻理解各种方法的特点，并能灵活应用。
3.加深对排序的理解，逐步培养解决实际问题的编程能力。
l 实验内容
1、排序的基本概念
（一）基础题
1.编写各种排序方法的基本操作函数：
（1）s_sort(int e[],int n)选择排序；
（2）si_sort(int e[],int n)直接插入排序；
（3）sb_sort(int e[],int n)冒泡排序；
（4）merge（int e[],int n）二路合并排序。
2.调用上述函数实现下列操作：
（1）对于给定的数组E[N]={213,111,222,77,400,300,987,1024,632,555}调用选择排序函数进行排序；
（2）调用直接插入函数进行排序；
（3）调用冒泡排序函数进行排序；
（4）调用二路合并排序函数进行排序。
（二）提高题
1.编写希尔排序函数对给定的数组进行排序。
2.编写快速排序函数对给定的数组进行排序。
l 实验结果
1、排序的基本概念
（一）基础题
（1）画出数据结构基本运算的流程图
（2）程序运行主要结果截图
（3）程序源代码
#include<stdio.h>
#include<conio.h>
#define N 10
int E[N]={213,111,222,77,400,300,987,1024,632,555};
void s_sort(int e[],int n)
{
int i,j,k,t;
for(i=0;i<n-1;i++)
{
for(k=i,j=i+1;j<n;j++)
if(e[k]>e[j])
k=j;
if(k!=i)
{
t=e[i];
e[i]=e[k];
e[k]=t;
}
}
}
int main()
{
int i;
printf("顺序排序,初始数据序列为:\n");
for(i=0;i<N;i++)
printf("%d ",E[i]);
s_sort(E,N);
printf("\n排序后的数据结构为：\n");
for(i=0;i<N;i++)
printf("%d ",E[i]);
getch();
}
#include<stdio.h>
#include<conio.h>
#define N 10
int E[N]={213,111,222,77,400,300,987,1024,632,555};
void si_sort(int e[],int n)
{
int i,j,t;
for(i=1;i<n;i++)
{
for(t=e[i],j=i-1;j>=0&&t<e[j];j--)
e[j+1]=e[j];
e[j+1]=t;
}
}
int main()
{
int i;
printf("直接排序，初始化数据为：\n");
for(i=0;i<N;i++)
printf("%d ",E[i]);
si_sort(E,N);
printf("\n排序后的数据结构为：\n");
for(i=0;i<N;i++)
printf("%d ",E[i]);
getch();
}
#include<stdio.h>
#include<conio.h>
#define N 10
int E[N]={213,111,222,77,400,300,987,1024,632,555};
void sb_sort(int e[],int n)
{
int j,p,h,t;
for(h=n-1;h>0;h--)
{
for(p=j=0;j<h;j++)
if(e[j]>e[j+1])
{
t=e[j];
e[j]=e[j+1];
e[j+1]=t;
//p=count2;
}
}
}
int main()
{
int i;
printf("冒泡排序,初始化数据序列为:\n");
for(i=0;i<N;i++)
printf("%d ",E[i]);
sb_sort(E,N);
printf("\n排序后的数据结构序列为：\n");
for(i=0;i<N;i++)
printf("%d ",E[i]);
getch();
}
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define N 10
int E[N]={213,111,222,77,400,300,987,1024,632,555};
void merge_step(int e[],int a[],int s,int m,int n)
{
int i,j,k;
k=i=s;
j=m+1;
while(i<=m&&j<=n)
if(e[i]<=e[j])
a[k++]=e[i++];
else
a[k++]=e[j++];
while(i<=m)
a[k++]=e[i++];
while(j<=n)
a[k++]=e[j++];
}
void merge_pass(int e[],int a[],int n,int len)
{
int f_s,s_end;
f_s=0;
while(f_s+len<n)
{
s_end=f_s+f_s+2*len-1;
if(s_end>=n)
s_end=n-1;
merge_step(e,a,f_s,f_s+len-1,s_end);
f_s=s_end+1;
}
if(f_s<n)
for( ;f_s<n;f_s++)
a[f_s]=e[f_s];
}
void merge(int e[],int n)
{
int *p,len=1,f=0;
p=(int *)malloc(n*sizeof(int));
while(len<n)
{
if(f==0)
merge_pass(e,p,n,len);
else
merge_pass(p,e,n,len);
len*=2;
f=1-f;
}
if(f==1)
for(f=0;f<n;f++)
e[f]=p[f];
free(p);
}
int main()
{
int i;
printf("归并排序，初始化数据序列为：\n");
for(i=000;i<N;i++)
printf("%d ",E[i]);
merge(E,N);
printf("\n排序后的数据序列为:\n");
for(i=0;i<N;i++)
printf("%d ",E[i]);
getch();
}
（二）提高题
（1）画出数据结构基本运算的流程图
（2）程序运行主要结果截图
（3）程序源代码
#include <stdio.h>
#include <stdlib.h>
void ShellSort(int a[], int length)
{
int increment;
int i,j;
int temp;
for(increment=length/2;increment>0;increment/=2)
{
for(i=increment;i<length;i++)
{
temp=a[i];
for(j=i-increment;j>=0&&temp<a[j];j-=increment)
{
a[j+increment]=a[j];
}
a[j+increment]=temp; //将第一个位置填上,记录后移
}
}
}
int main()
{
int i, j;
int a[]={213,111,222,77,400,300,987,1024,632,555};
printf("初始化的数据序列为:\n");
for(i=0;i<10;i++)
{
printf("%d ",a[i]);
}
ShellSort(a,10);
printf("\n排序后的序列是:\n");
for(j=0;j<10;j++)
{
printf("%d ", a[j]);
}
printf("\n");
return 0;
}
#include<stdio.h>
#include<stdlib.h>
#define MAXNUM 10
#define keytype int
typedef struct
{
keytype key;
}datatype;
datatype R[MAXNUM];
//datatype R[MAXNUM]={213,111,222,77,400,300,987,1024,632,555};
void read()
{
int i,n;
printf("请输入要输入的个数：\n");
scanf("%d",&n);
printf("请输入初始排序数据：\n");
for(i=1;i<=n;i++)
{
scanf("%d",&R[i]);
}
}
int Partition(datatype R[],int low,int high)
{
R[0]=R[low];
while(low<high)
{
while(low<high&&R[high].key>=R[0].key)
high--;
if(low<high)
{
R[low]=R[high];
low++;
}
while(low<high&&R[low].key<R[0].key)
low++;
if(low<high)
{
R[high]=R[low];
high--;
}
}
R[low]=R[0];
return low;
}
void Quick_Sort(datatype R[],int s,int t)
{
int i;
if(s<t)
{
i=Partition(R,s,t);
Quick_Sort(R,s,i-1);
Quick_Sort(R,i+1,t);
}
}
int main()
{
int i,s=1,t=10;
read();
/*printf("初始化数据为：\n");*/
Quick_Sort(R,s,t);
printf("\n快速排序数据为：\n");
for(i=1;i<=MAXNUM;i++)
printf("%d ",R[i]);
}
数据结构-实验六 排序