利用双向走动法改进冒泡排序算法C语言源代码[黑盟核心成员]

作 者： BugEyes

传统的冒泡排序法是这样操作：从前往后，依次比较两个相邻的元素，如果逆序则交换这两个元素值，然后继续往后操作；到了数据尾部时，就找出了一个最大值（或最小值）。然后重复上面的操作n-1次（n为元素个数）。

相关的改进办法：按照上面的办法来操作的话，第一次扫描把最大数（或最小数）放到最后面的位置，第二次扫描时其实只需要扫描到倒数第二个位置就可以了，因为最后一个位置已经不需要判断了，以后的操作都是类似的。这样可以减小程序运行时间。

双向走动法（以升序排序为例）：首先，从前往后扫描，如果相邻两个元素前面的比后面的大，则交换，继续往后；到尾部以后，再往回走，如果后面的元素比前面的小，则交换，继续往前走；到了头以后，再往后走。为了减少走动次数，我们用变量start表示头，用变量end表示尾。每找到一个剩余数据中的最大数，就让变量end减1，每找到一个剩余数据中的最小数，就让变量start加1。循环条件为start<=end。

代码如下：

＃i nclude
＃i nclude

void maopao(int source[],int n)
{
int start=0,end=n-1;
int i;
while(start<=end)/*如果还有元素没有确定其位置*/
{
for(i=start;iif(source[i]>source[i+1])
{
int t;
t=source[i];
source[i]=source[i+1];
source[i+1]=t;
}
end--;/*找到最大数*/
for(i=end;i>start;i--)/*寻找剩余元素的最小元素*/
if(source[i]{
int t;
t=source[i];
source[i]=source[i-1];
source[i-1]=t;
}
start++;/*找到一个最小数*/
}
}

void output(int data[],int n)
{
int i;
for(i=0;i{
if(i%10==0)
printf("\n");
printf("%4d",data[i]);
}
}

int check(int data[],int n)
{/*检查结果数据是否已升序排列*/
int i;
for(i=0;iif(data[i]>data[i+1])
return 0;
return 1;
}

void main()
{
int data[500];
int i;
srand(time(NULL));
for(i=0;i<500;i++)
data[i]=random(500);
printf("\nThe original data is:\n");
output(data,500);
maopao(data,500);
printf("\nAfter sort:\n");
output(data,500);
printf("\n");
if(check(data,500)==1)
printf("\nRight.");
else
printf("\nWrong.");
}