关于简单选择排序、直接插入排序和冒泡排序

Question

实验内容：
输入一组关键字序列分别实现下列排序算法：
实现简单选择排序、直接插入排序和冒泡排序。

提示：关键字序列可用随机数产生。
在TC2中产生随机数列程：
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
void main(void)
{int i;
randomize();
for(i=0;i<10;i++)
printf("%6d\n ",R(100));

下面是我自己根据课本编的：
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
void main(void)
{int i;
randomize();
for(i=0;i<10;i++)
printf("%6d\n ",R(100));
D_InsertSort(R,i);
printf("the new list is:%6d\n ",R(i));
SelectSort(R,i);
printf("the new list is:%6d\n ",R(i));
BubbleSort(R,i);
printf("the new list is:%6d\n ",R(i));
}

void SelectSort(datatype R[],int n)
{for(i=1;i<n;i++)
{k=i;
for(j=i+1;j<=n;j++)
if(R[j].key<R[k].key)
k=j;
if(i!=k)
{R[0]=R[k];
R[k]=R[i];
R[i]=R[0]
}
}

void BubbleSort(datatype R[],int n)
{int i,j;
int swap;
for(i=1;i<=n-1;i++)
{swap=0;
for(j=1;j<=n-i;j++)
if(R[j].key>R[j+1].key)
{
R[0]=R[j];
R[j]=R[j+1];
R[j+1]=R[0];
swap=1;
}
if(swap==0)break;
}
}

void D_InsertSort(datatype R[].int n)
{
for(i=2;i<=n;i++)
if(R[i].key<R[i-1].key)
{R[0]=R[i];
for(j=i-1;R[0].key<R[j].key;j--)
R[j+1]=R[j];
R[j+1]=R[0];
}
}

在WIN-TC中运行，它给我的提示是：
22：变量列表语法错误。也就是void D_InsertSort(datatype R[].int n) 这种，好像这三个算法都是一样的提示。。。

不知道是怎么回事。。。。。在线高分等解答！！

Answer 1

直接插入排序
说明：逐个将后一个数加到前面的排好的序中。在直接插入排序过程中，对其中一个记录的插入排序称为一次

排序；直接插入排序是从第二个记录开始进行的，因此，长度为n的记录序列需要进行n-1次排序才能完成整个

序列的排序。时间复杂度为O(n2)。
void InsertSort(elemtype x[],int n)
/*用直接插入法对x[0]-x[n-1]排序*/
{
int i,j;
elemtype s;
for(i=0;i<n-1;i++)
{
s=x[i+1];
j=i;
while(j>-1&&s.key<x[j].key)
{
x[j+1]=x[j];
j--;
}
x[j+1]=s;
}
}

－－－－－－－－－－－－－－－－－－－－－
希尔排序
说明：希尔排序又称缩小增量排序，增量di可以有各种不同的取法，但最后一次排序时的增量必须为1，最简

单可取di+1=di/2（取小）。时间复杂度为O(n(log2n)2)。

void ShellSort(elemtype x[],int n,intd[],int Number)
/*用希尔排序法对记录x[0]-x[n-1]排序，d为增量值数组*/
/*Number为增量值个数，各组内采用直接插入法排序*/
{
int i,j,k,m,Span;
elemtype s;
for(m=0;m<Number;m++)
{
Span=d[m];
for(k=0;k<Span;k++)
{
for(i=k;i<n-1;i+=Span)/*这个for之后的是“组内采用直接插入法排序”*/
{
s=x[i+Span];
j=i;
while(j>-1&&s.key<x[j].key)
{
x[j+Span]=x[j];
j-=Span;
}
x[j+Span]=s;
}
}
}
}

－－－－－－－－－－－－－－－－－－－－－－－－－－－－
直接选择排序
说明：每次将后面的最小的找出来插入前面的已排好的序中。同理，具有n个记录的序列要做n-1次排序。
时间复杂度为O(n2)。
void SelectSort(elemtype x[],int n)
/*用直接选择排序法对x[0]-x[n-1]排序*/
{
int i,j,Small;
elemtype Temp;
for(i=0;i<n-1;i++)
{
Small=i;
for(j=i+1;j<n;j++)
if(x[j].key<x[Small].key)
Small=j;

if(Small!=i)
{
Temp=x[i];
x[i]=x[Small];
x[Small]=Temp;
}
}
}

－－－－－－－－－－－－－－－－－－－－－－－－－－
冒泡排序
说明：两个两个比较，将大的往后移。通过第一次冒泡排序，使得待排序的n个记录中关键字最大的记录排到

了序列的最后一个位置上。然后对序列中前n-1个记录进行第二次冒泡排序。。。对于n个记录的序列，共需进

行n次冒泡排序。时间复杂度为O(n2)。

void BubbleSort(elemtype x[],int n)
/*用冒泡排序法对x[0]-x[n-1]排序*/
{
int i,j,flag=1;
elemtype Temp;
for(i=1;i<n&&flag==1;i++)
{
flag=0;
for(j=0;j<n-i;j++)
{
if(x[j].key>x[j+1].key)
{
flag=1;
Temp=x[j];
x[j]=x[j+1];
x[j+1]=Temp;
}
}
}
}

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
快速排序
说明：又叫分区交换排序，是对冒泡排序方法的一种改进。时间复杂度为O(nlog2n)。

void QuickSort(elemtype x[],int low,int high)
/*用递归方法对记录x[0]-x[n-1]进行快速排序*/
{
int i,j;
elemtype Temp;

i=low;
j=high;
Temp=x[low];

while(i<j)
{
/*在序列的右端扫描*/
while(i<j&&Temp.key<=x[j].key)j--;
if(i<j)
{
x[i]=x[j];
i++;
}

/*在序列的左端扫描*/
while(i<j&&x[i].key<Temp.key)i++;
if(i<j)
{
x[j]=x[i];
j--;
}
}
x[i]=Temp;

/*对子序列进行快速排序*/
if(low<i-1)QuickSort(x,low,i-1);
if(j+1<high)QuickSort(x,j+1,high);
}

－－－－－－－－－－－－－－－－－－－－－－－－－
归并排序
说明：所谓归并排序就是将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。
时间复杂度为O(nlog2n)。

void merge(r,l,m,h,r1,r2)/*r[l,m]及r[m+1,h]分别有序，归并后置于r2中*/
sqlist r,r2;
int l,m,h;
{
int i,j,k;
k=l;/*k是r2的指示器，i、j分别为s1、s2的指示器*/
i=l;
j=m+1;

while(i<=m&&j<=h)
{
if(r[i].key<=r[j].key)
{
r2[k]=r[i];
i++;
}
else
{
r2[k]=r[j];
j++;
}
k++;
}
if(i>m) /*s1结束*/
while(j<=h)
{
r2[k]=r[j];
j++;k++;
}
else
while(i<=m)
{
r2[k]=r[i];
i++;k++;
}
}

Answer 2

变量列表语法错误，也就是(datatype R[].int n)这个部分，我看了你的程序，你前面好象没有定义出数组以及类型，所以没法传递参数。而且中间是用逗号隔开的吧。

Answer 3

帮你修改好了。

你的程序错误太多了。

你之前学过更高级的语言吧？居然这样用：R[i].key>R[j].key

#include<stdlib.h>
#include<stdio.h>
#include<time.h>

#define datatype int

void SelectSort(datatype R[],int n)
{
int i,k,j;

for(i=1;i<n;i++)
{
k=i;
for(j=i+1;j<=n;j++)
//if(R[j].key<R[k].key)
if(R[j]<R[k])
k=j;
if(i!=k)
{
R[0]=R[k];
R[k]=R[i];
R[i]=R[0];
}
}
}

void BubbleSort(datatype R[],int n)
{
int i,j;
int swap;

for(i=1;i<=n-1;i++)
{
swap=0;
for(j=1;j<=n-i;j++)
//if(R[j].key>R[j+1].key)
if(R[j]>R[j+1])
{
R[0]=R[j];
R[j]=R[j+1];
R[j+1]=R[0];
swap=1;
}
if(swap==0)break;
}
}

void D_InsertSort(datatype R[],int n)
{
int i,j;

for(i=2;i<=n;i++)
//if(R[i].key<R[i-1].key)
if(R[i]<R[i-1])
{
R[0]=R[i];
//for(j=i-1;R[0].key<R[j].key;j--)
for(j=i-1;R[0]<R[j];j--)
R[j+1]=R[j];
R[j+1]=R[0];
}
}

void main(void)
{
datatype R[11]={0};
int i;

//randomize();
srand((unsigned)time(NULL));
for(i=1;i<=10;i++)
{
R[i]=rand()%100;
printf("%6d",R[i]);
}
printf("\n");

D_InsertSort(R,10);
//printf("the new list is:%6d\n ",R(i));
printf("the new list is:\n");
for(i=1;i<=10;i++)
{
printf("%6d",R[i]);
}
printf("\n");

SelectSort(R,10);
//printf("the new list is:%6d\n ",R(i));
printf("the new list is:\n");
for(i=1;i<=10;i++)
{
printf("%6d",R[i]);
}
printf("\n");

BubbleSort(R,10);
//printf("the new list is:%6d\n ",R(i));
printf("the new list is:\n");
for(i=1;i<=10;i++)
{
printf("%6d",R[i]);
}/**/
printf("\n");
getchar();
}本回答被提问者采纳

Answer 4

改成这样:
void D_InsertSort(datatype* R, int n);
其他的类似.

Answer 5

经典排序之冒泡排序