输入一组关键字序列，分别实现下列排序算法:
1.编写函数，实现简单选择排序算法。（√）
2.编写函数，实现直接插入排序算法。（代码无误，运行不出，待改正）
3.编写函数，实现冒泡排序算法。（√）
4.编写函数，实现二路归并算法。（待改正）
5.编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述算法。（√）
#include<stdio.h>
#include<malloc.h>
#define MAXSIZE 9//数组最大数
typedef int ElemType;
typedef struct
{
ElemType e[MAXSIZE];
int n;
}SqList;
void create(SqList *s){
ElemType i;
printf("请输入数字（以空格分开）：");
for(i=0;i<MAXSIZE;i++){
scanf("%9d",&s->e[i]);//%9d是为了防止scanf函数中超出限定值而设定
s->n++;
}
}
void out(SqList *s){
int i;
printf("当前数组顺序：");
for(int i=0;i<MAXSIZE;i++){
printf("%d",s->e[i]);
}
}
//简单选择排序
void s_sort(int e[], int n)/* e:存储线性表的数组 n：线性表的结点个数 */
{
int i, j, k, t;
for( i = 0; i < n-1; i++ ) { /* 控制n-1趟的选择步骤 */
/* 在e[i], e[i+1],...,e[n-1]中选键值最小的结点e[k] */
for( k = i, j =i+1; j < n; j++ )//第一空：j=i+1:两两对比查找最小值，k为i，j为i的下一位
if( e[k] > e[j] )
k=j;
if(e[i]!= e[k]) { /* e[i]与e[k]作交换 */ //第二空 ：如果最小值e[k]不等于e[i]，说明找到最小值，交换
t = e[i];
e[i] = e[k];
e[k] = t;
}
}
}
//插入排序:运行有错误
void si_sort( int e[], int n ) /* e:存储线性表的数组 n：线性表的结点个数 */
{
int i, j, t;
for( i = 1; i < n; i++ ){/* 控制e[i], e[i+1],...,e[n-1]的比较插入步骤 */
/* 找结点e[i]的插入位置 */
for( e[t]=e[i], j = i-1; j >= 0 && e[j]>e[t]; j-- )
e[j+1] = e[j];//记录后移
e[j+1]=e[t];//插入到正确位置
}
}
//冒泡排序 :两两交换，一次不准继续排序
void sb_sort( int e[], int n ) /* e:存储线性表的数组 n：线性表的结点个数 */
{
int j, p, h, t;//j:元素下标 p: h:结点个数，即数组长度 t: 交换用临时下标
for( h = t = n; h > 0; h = p ) {//第一空：h=n由j<h推出
for( p = j = 0; j < h; j++ )
if(e[j]>e[j+1]) {//第二空
e[t]=e[j];//第三空
e[j] = e[j+1];
e[j+1]=e[t];//第四空
p = 0;//使循环继续
}
}
}
//二路归并排序 :错误，排不了序
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++];//第二空：将较小的元素复制进a[]
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 + len;//第五空:?
if( s_end >= n ) /* 最后一段可能不足len个结点 */
s_end = len;//第六空 :?
merge_step(e,a,f_s,s_end,n); /* 相邻有序段合并 */ //第七空
f_s = s_end + 1; /* 下一对有序段中左段的开始下标为上一对末尾+1 */
}
if( f_s < n ) /* 当还剩一个有序段时， 将其从e[]复制到a[] */
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 ) { /* 交替地在e[]和p[]之间来回合并 */
if( f == 0 )
merge_pass(e,p,n,len);//第八空 :?
else
merge_pass(e,p,n,len);//第九空:?
len=len*2; /* 一趟合并后，有序结点数加倍 */ //第十空:?
f = 1 - f; /* 控制交替合并 */
}
if( f == 1 ) /* 当经过奇数趟合并时，从p[]复制到e[] */
for( f = 0; f < n; f++ )
e[f] = p[f];
free( p );
}
int main(){
int ch;
SqList s;
while(1){
printf("1、创建数组\n");
printf("2、输出数组\n");
printf("3、简单选择排序\n");
printf("4、直接插入排序\n");
printf("5、冒泡排序\n");
printf("6、二路归并排序\n");
printf("请选择：");
scanf("%d",&ch);
switch(ch){
case 1:create(&s);break;
case 2:
out(&s);
printf("\n");//将换行符写在这，避免输出段与菜单段连在一起出现
break;
case 3:
s_sort(s.e,s.n);
printf("\n");
break;
case 4:
si_sort(s.e,s.n);
printf("\n");
break;
case 5:
sb_sort(s.e,s.n);
printf("\n");
break;
case 6:
merge(s.e,s.n);
printf("\n");
break;
}
}
}
|