欢迎访问民科维基!注册一个账号,参与民科补完计划

若您想捐助我们可以点这里!欢迎所有对待建条目感兴趣的同学加入QQ群:699597090

张仰彪

来自民科维基
跳转至: 导航搜索
人物图片
上传测试图片20180309.jpg
人物信息
人物姓名 张仰彪
网络ID sadfgsdfg
人物职业
不明
人物类别
不被承认 C级民科
代表理论
张仰彪第二排序法

张仰彪,信息学民科,曾在CSDN论坛发表理论,研究新的排序算法。

代表理论

张仰彪第二排序法

将待排序数组内放错位置的数据标记为“站错位置”,并自动地将这些“站错位置”的数据按照它们相互之间的内在关系而分成几个不同的小组。排序时从最前头开始清查,若遇到的“没有站错”,就快速通过去查下一个。如果查到一个“站错位置”的数据,就停下来在这个位置上连续地排查运作,直到将这个“站错位置”的数据及其所在小组的全部成员都清理到正确的位置上,然后才继续前行去查下一个位置。直到清查的次数比队列的长度小1时,队列中所有“站错位置”的数据都已被清理到了正确的位置上,排序完毕。

张仰彪在CSDN发布后,被人指出代码中有大量bug,其中不乏for循环遍历方向搞反等低级错误,从而导致已经归位的数据被再次归位浪费效率,某些样例数据无法输出正确结果甚至出现死循环。 [1]

算法效率

时间复杂度:O(n2)

空间复杂度:O(n)

稳定度:较差(低于冒泡排序)

代码


#include < stdio.h >
void  main ( ) 
{ 
 int  a [10]; 
 int  i;              /* 记录排序的次数,并用于输入输出 */ 
 int  j = 0;            /* 记录当前排序的位置 */ 
 int  temp;          /* 数据交换时的存储中介 */ 
 int  order;          /* 记录数据在数组里的大小排名,从小向大算 */ 
 printf ( " Input 10 numbers:\n" ); 
 for ( i=0;i < 10;i++ )          /* 输入任意10个整数 */ 
     scanf ( " %d",&a[i] ); 
 printf ( " \n" ); 
 for ( i=0;i < 9;i ++ )        /* 排序的总次数比待排序数组的长度小1 */ 
 { 
     order = j;              /* 数据的排名从当前位置开始向后计算 */ 
     for ( int x = j+1;x < 10;x ++ )      /* 计算当前数据在数组里的排名 */ 
       if ( a[x] < a[j] )  order ++;              
     
     if ( order > j )      /* 如果当前数据的排名大于它现在的位置 */  
     { 
       while ( a[j] = = a[order] )  order ++;  /* 处理数组里的重复数据 */ 
       temp = a[order];          /* 将这个数据交换到正确的位置上 */ 
       a[order] = a[j]; 
       a[j] = temp; 
     } 
     else        /* 如果当前数据的排名等于(不可能小于)它现在的位置 */  
       j ++;                    /* 开始排下一个位置上的数据 */      
 } 
 printf ( " The sorted numbers is:\n" ); 
 for ( i=0;i < 10;i ++ )          /* 输出排好序的10个整数 */ 
     printf ( " %d",a[i] ); 
 printf ( " \n" ); 

}



张仰彪第三排序法

张仰彪第三排序法的原理:它将待排序数组内的数据以两个为一对进行处理,排序的过程可以分成两种不同的步骤:

a步骤是将各对数据进行比较和交换。

b步骤是在各对数据之间进行比较和交换。

a、b两种步骤交替进行,直到发现其中一个步骤完成后,接下来的另一个步骤没有交换数据,此时数组内各对数据自身都已有序,并且各对数据之间也已经有序,排序完毕。

张仰彪在CSDN发布代码后,被网友挑出循环嵌套中的bug且发现大量样例数据无法输出正确结果,还有人指出该算法与已有的奇偶排序法类似。 [2]

算法效率

时间复杂度:O(n2)

空间复杂度:O(n)

稳定度:较差(低于冒泡排序)

代码

#include < stdio.h >
void  main ( )
{
  int  a [10];
  int  i;               /* 记录排序的当前位置,并用于输入输出 */
  int  j= -1 ,  t= -1;       /* 记录一次排序循环中交换数据的次数 */
  int  temp;           /* 数据交换时的存储中介 */
  
  printf ( " Input 10 numbers:\n" );
  for ( i=0;i < 10;i++ )           /* 输入任意10个整数 */
     scanf ( " %d",&a[i] );
  printf ( " \n" );
  
  while(j>0 || t>0)  /* 如果数据对内部排序或数据对之间排序曾交换数据*/ 
  {
     j = 0;              /* 先清零 */
     for ( i = 0;i < =8;i +=2 )      /* 从头至尾,逐对排序 */
     {
        if ( a[i] > a[i+1] )  
        {
           temp = a[i];          
           a[i] = a[i+1];
           a[i+1] = temp;
           j++;               /* 记住有了一次数据交换 */
        } 
     }
     if(j= =0 && t!= -1)  break;   /* t= -1说明是头一个排序步骤,此时即使数 
                                      据对内部有序,还要检查数据对之间是否有序*/ 
     t=0;                /* 先清零 */
     for ( i = 1;i < =8;i +=2 )      /* 从第二至尾,在各对数据之间排序 */
     {
        if ( a[i] > a[i+1] )  
        {
           temp = a[i];          
           a[i] = a[i+1];
           a[i+1] = temp;
           t++;               /* 记住有了一次交换 */
        } 
     }
     if(t= =0)  break;  
  }
       
  printf ( " The sorted numbers is:\n" );
  for ( i=0;i < 10;i ++ )           /* 输出排好序的10个整数 */
     printf ( " %d",a[i] );
  printf ( " \n" );
}

张仰彪选择排序法

第二排序法和第三排序法被CSDN网友指出bug后,张仰彪痛定思过,改进并发明了张仰彪选择排序法,自称平均效率能提升12.5%(最优情况25%,最差情况0%)。

再次被网友挑出循环嵌套中的bug,被指并未根本上改变算法的面貌,仅仅是增加了代码的复杂程度和阅读难度,效率更低。

[3]

算法效率

时间复杂度:O(n2)

空间复杂度:O(n)

稳定度:较差(低于冒泡排序)

代码

#include < stdio.h >
void  main ( )
{
  int  a [10];
  int  i,x;                /* 记录排序的次数和当前排序的位置 */
  int  min1, min2 ,min3;      /* 记录查到的最小、次小等数据的位置 */
  int  temp;            /* 数据交换时的存储中介 */
       
  printf ( " Input 10 numbers:\n" );
  for ( i=0;i < 10;i++ )           /* 输入任意10个整数 */
     scanf ( " %d",&a[i] );
  printf ( " \n" );
  for ( i=0;i < =8;i +=2 )         /* 排序时一个循环向前跨两步 */
  {
     min1=i;  min2=i+1;    /* 若查不到更小的数据,最小数据就在当前位置, 
           将次小的初值设为i+1,是为了处理最小就是当前的特殊情况*/
     for ( int x = i+1;x < =9;x ++ )  /* 查找当前位置(含)后面两个小数据 */
     {
        if ( a[x] < a[min1] )          
        {
           min2=min1;    /* 先将原先最小数据的下标存到min2里 */
           min1=x;      /* 再将新查到的最小数据的位置存到min1里 */  
        }  
     }                /* 获得当前位置后边的最小和次小数据的位置*/
     
     for(x=min1+2; x<9; x++)    /* 在最小数后面的找出一个最小的*/
     {    /* 因为最小数后面的数虽然都比最小大,但却可能小于次小0*/
        min3=min1+1;
        if(a[x]<a[min3])  min3=x;
     }         /*即使当前就是最小,仍可用此for( )循环找到一个次小*/
     if(a[ min3] <= a[min2])  min2=min3;     /* 这才是真正的次小*/
                   /* 之所以用<=,是尽可能把次小的位置向后定*/
     if(min2!=i)  /* 次小不在当前位置,先交换最小不会错移次小*/
     {
        temp=a[min1];      /*先交换最小到当前位置*/
        a[min1]=a[i];
        a[i]=temp;
        temp=a[min2];        /*然后再交换次小到当前之后*/
        a[min2]=a[i+1];
        a[i+1]=temp;
     }
     else    /*min2=i, 次小在当前位置上,此时先交换最小会错移次小*/
     {
        if(min1=i+1)   /*次小在当前位置,后边第一个就是最小*/
        {
           temp=a[min2];       /*将次小和最小互换位置即可*/
           a[min2]=a[min1];
           a[min1]=temp;
        }
        else    /*次小在当前位置,后边相隔一个以上才是最小*/
        {
           temp=a[min2];       /*先交换次小到当前之后*/
           a[min2]=a[i+1];
           a[i+1]=temp;
  
           temp=a[min1];       /*然后再交换最小到当前位置*/
           a[min1]=a[i];
           a[i]=temp;
        }
     }
  }   
  printf ( " The sorted numbers is:\n" );
  for ( i=0;i < 10;i ++ )           /* 输出排好序的10个整数 */
     printf ( " %d",a[i] );
  printf ( " \n" );
}

最后

引用小说·电视剧·电影的台词表达自己的观点。

参考文献

外部链接

CSDN个人主页