双向冒泡法算法改进代码.txt

c语言的一些常见的算法以及思考和改进的文章,写的很不错,花费了很大的精力从网络了搜罗的,希望大家喜欢.

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

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

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

代码如下：

＃i nclude <stdlib.h>
＃i nclude <time.h>

void maopao(int source[],int n)
{
int start=0,end=n-1;
int i;
while(start<=end)/*如果还有元素没有确定其位置*/
{
for(i=start;i<end;i++)/*寻找剩余元素的最大数*/
if(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]<source[i-1])
{
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<n;i++)
{
if(i%10==0)
printf("\n");
printf("%4d",data[i]);
}
}

int check(int data[],int n)
{/*检查结果数据是否已升序排列*/
int i;
for(i=0;i<n-1;i++)
if(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.");
}

写完以后，自己想了一下，这个算法是可以改进的。改进后的代码请看：
http://bugeyes.blog.edu.cn/user1/20989/archives/2005/1015546.shtml 
//-----------------------------------------------------
朋友们如果转载或引用本站的内容，请尊重作者的劳动，注意保留完整，并注明文章原始url。谢谢！_____________BugEyes

对双向走动法冒泡排序的进一步改进[原创] 
       看了看自己写的代码

http://bugeyes.blog.edu.cn/user1/20989/archives/2005/1012747.shtml

       感觉还需要改进，主要是在双向走动时可能存在“空走”的现象，即可能经过几次走动以后，某位置（设为j）开始到end之间的数据已经按序排好了，这时我们可以直接把end拿到j位置来，而不需要一次次的执行end--；同样可能经过几次走动后，start到某位置（设为j）之间的数据也已经按序排好了，这样也可以直接把start拿到j位置，而不需要一次次的start++。这就是我的主要思路，实现代码如下：

＃i nclude <stdlib.h>
＃i nclude <time.h>

int maopao(int source[],int n)
{/*原来的代码，主要用来和新的方法比较，不多解释*/
   int start=0,end=n-1;
   int i;
   int count=0;
   while(start<end)
   {
      for(i=start;i<end;i++)
         if(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]<source[i-1])
          {
              int t;
              t=source[i];
              source[i]=source[i-1];
              source[i-1]=t;
          }
      start++;
      count++;
   }
   return count;
}

int maopao1(int source[],int n)
{/*新方法*/
   int start=0,end=n-1;
   int i,j;
   int count=0;
   while(start<end)
   {
      for(i=start;i<end;i++)
          if(source[i]>source[i+1])
          {
             int t;
             t=source[i];
             source[i]=source[i+1];
             source[i+1]=t;
             j=i;/*记录交换位置*/
          }
      end=j;/*把下一次向后走动的终点限定在最后一次交换的位置*/
      for(i=end;i>start;i--)
          if(source[i]<source[i-1])
          {
               int t;
               t=source[i];
               source[i]=source[i-1];
               source[i-1]=t;
                j=i;
          }
      start=j;/*把下一次向前走动的终点限定为最后一次的交换位置*/
      count++;
   }
   return count;
}

void init(int data[],int n)
{
   int i;
   for(i=0;i<n;i++)
      data[i]=random(500);/*为了比较两种方法，没有使用随机种子*/
}

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

int check(int data[],int n)
{
   int i;
   for(i=0;i<n-1;i++)
      if(data[i]>data[i+1])
           return 0;
   return 1;
}

void main()
{
   int data[800];
   int count1,count2;
   init(data,800);
   count1=maopao(data,800);
   if(check(data,800)==1)
      printf("\nRight.");
   else
      printf("\nWrong.");
   printf("\nFirst:%d",count1);
   init(data,800);
   count2=maopao1(data,800);
   if(check(data,800)==1)
      printf("\nRight.");
   else
      printf("\nWrong.");
   printf("\nSecond:%d",count2);
}

运行结果：

Right.
First:400
Right.
Second:211

可见这个改进还是有效果的。另外,我还没有想到这个算法的实用性.暂时归类到人工智能吧,想象有个人来回走动,对数据排序.

后记:简单想了一下,这个改进应该比

http://bugeyes.blog.edu.cn/user1/20989/archives/2005/167836.shtml

中第三种方法减少了"空走"的次数.等有时间再验证一下.

写了一下，不一定准确，验证代码如下：

#define N 90
＃i nclude <stdlib.h>
＃i nclude <time.h>

int maopao0(int source[],int n)
{
   int i,j,p;
   int count=0;
   for(i=n-1;i>0;i=p)
     for(j=p=0;j<i;j++)
     {
       count++;
       if(source[j]>source[j+1])
       {
           int t;
           t=source[j];
           source[j]=source[j+1];
           source[j+1]=t;
           p=j;
       }
     }
   return count;
}

int maopao(int source[],int n)
{
   int start=0,end=n-1;
   int i;
   int count=0;
   while(start<end)
   {
      for(i=start;i<end;i++)
      {
         count++;
         if(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--)
      {
          count++;
          if(source[i]<source[i-1])
          {
             int t;
             t=source[i];
             source[i]=source[i-1];
             source[i-1]=t;
           }
      }
      start++;
   }
   return count;
}

int maopao1(int source[],int n)
{
   int start=0,end=n-1;
   int i,j;
   int count=0;
   while(start<end)
   {
      for(i=start;i<end;i++)
      {
         count++;
         if(source[i]>source[i+1])
         {
              int t;
              t=source[i];
              source[i]=source[i+1];
              source[i+1]=t;
              j=i;
          }
      }
      end=j;
      for(i=end;i>start;i--)
      {
          count++;
          if(source[i]<source[i-1])
         {
             int t;
             t=source[i];
             source[i]=source[i-1];
             source[i-1]=t;
             j=i;
         }
      }
      start=j;
   }
   return count;
}

void init(int data[],int n)
{
   int i;
   for(i=0;i<n;i++)
      data[i]=random(500);
}


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

int check(int data[],int n)
{
   int i;
   for(i=0;i<n-1;i++)
      if(data[i]>data[i+1])
          return 0;
   return 1;
}

void main()
{
   int data[N];
   int count1,count2,count3;
   init(data,N);
   count1=maopao(data,N);
   if(check(data,N)==1)
      printf("\nRight.");
   else
      printf("\nWrong.");
   printf("\nFirst:%d",count1);
   init(data,N);
   count2=maopao1(data,N);
   if(check(data,N)==1)
      printf("\nRight.");
   else
      printf("\nWrong.");
   printf("\nSecond:%d",count2);
   init(data,N);
   count3=maopao0(data,N);
   if(check(data,N)==1)
      printf("\nRight.");
   else
      printf("\nWrong.");
   printf("\nThird:%d",count3);
}

测试结果:

N=90时,结果为

Right.
First:4005
Right.
Second:2566
Right.
Third:3828

N=80时,结果为:

Right.
First:3160
Right.
Second:2120
Right.
Third:3145

N=50时,结果为：

Right.
First:1225
Right.
Second:869
Right.
Third:1138