挑战数组腾挪大法

wwjxjtu

不好意思，前几次都是即时写的，没有经过测试，下面是经过测试的，希望各位能发现问题！
void specsort(int *num,int x,int len){
int i,j,tmp,pos,val,var,k,nx=0&#59;
tmp=len-1&#59;
for(i=0&#59;i<tmp&#59;i++){
if(*(num+i)>;x){
for(j=tmp&#59;j>;i&#59;j--){
if(*(num+j)<x){
val=*(num+i)&#59;
*(num+i)=*(num+j)&#59;
*(num+j)=val&#59;
tmp=j-1&#59;
break&#59;
}
else if(*(num+j)==x){
pos=j&#59;
nx++&#59;
}
}
}
else if(*(num+i)==x){
pos=i&#59;
nx++&#59;
}
if(i==j) break&#59;
}
if(nx==0){
printf(&quot;No such value %d in array&quot;,x)&#59;
exit(0)&#59;
}
if(i==j) tmp=*(num+i)>;=x&amp;&amp;pos<i?i-1:i&#59;
else{
if(*(num+i)>;=x) tmp=pos>;i?i:i-1&#59;
else if(*(num+i+1)>;=x) tmp=pos>;i?i+1:i&#59;
}
*(num+pos)=*(num+tmp)&#59;
*(num+tmp)=x&#59;
pos=nx&#59;
k=j=1&#59;
var=tmp>;len-tmp?tmp:len-tmp&#59;
for(i=1&#59;i<=var&amp;&amp;nx>;1&#59;i++){
if(tmp>;=i&amp;&amp;*(num+tmp-i)==x){
val=(num+tmp-i)&#59;
*(num+tmp-i)=*(num+tmp-j)&#59;
*(num+tmp-j)=val&#59;
nx--&#59;
j++&#59;
}
if(tmp+i<len&amp;&amp;*(num+tmp+i)==x){
val=*(num+tmp+i)&#59;
*(num+tmp+i)=*(num+tmp+k)&#59;
*(num+tmp+k)=val&#59;
nx--&#59;
k++&#59;
}
}
printf(&quot;value x=%d's  nums:%d\n&quot;,x,pos)&#59;
printf(&quot;The left position is :%d\n&quot;,tmp-j+1)&#59;
}

samhoo

各位“程序员”情结浓厚如是！

前面给出了模板，以利于高效交流，更深入的探讨。本想比较比较时间，
看看谁可以发挥到极致，看看一段集中的小程序是如何进化的。
可是三位陆续给出的解答，在samhoo已经整理的情况下，仍未能照此执行，
哪怕是举手之劳，嘿嘿。

sorry,我是再没有精力逐个整理，也不会再“希望各位能发现问题”了。
谢谢各位的参与，尽管仍有遗憾。

离了水的蛤蟆

我没有发现问题呀，这是我的机器上运行的结果：
Number of elements to sort=>;1000000
Seed for random number generator (integer)=>;345678
X=14338
L[]=19454 7084 24182 7795 23488 18221 15545 10591 14569 5637 25832 22887 18232 7
949 27961 24949 24469 19989 291 9932 21814 ...(too much number, ignore)
-----------------------------------------------------------------
436816 436855
Check :correct.
Time  : 0.600 seconds.
-----------------------------------------------------------------
position=436816
L[]=9615 7084 11244 7795 1183 8439 8506 10591 5056 5637 4593 8136 592 7949 7470
6621 3875 13969 291 9932 13627 ...(too much number, ignore)

samvelly

void main()
{
longL[20]={6,7,2,4,5,7,8,5,3,5,4,5,6,2,3,4,8,9,6,1}&#59;
long x = 5, tmp&#59;
longp1,p2,s1,i&#59;

for(p1=0, p2=19, s1=0&#59; p1<＝p2&#59; )
{
if( L[p1] >; x )
        {
        tmp = L[p2]&#59;
        L[p2--] = L[p1]&#59;
           L[p1] = tmp&#59;
        }
        else if( L[p1] == x ){
        p1++&#59;
        }
        else{
        L[s1++] = L[p1++]&#59;
        }
}

for( i=s1&#59;i<＝p2&#59;i++ ){
L = x&#59;
}

for( i=0&#59;i<20&#59;i++ )
printf(&quot;%d\n&quot;, L)&#59;

}

西北风

/******************************************************************************
name : a.c
function: 算法演示，把数组中等于5的元素放在中间，大于的放在后面，小于者放在前面
memo:   
   约定：数组中至少有一个5元素
   这个程序我测试过的，应该解决本题目。很高兴能与大家认识，望诸位以后多多提携小弟。
version:
     1.0.0.0        xibeifeng      2002.11.26
*******************************************************************************/

#include <stdio.h>;
#include <string.h>;
#include <stdlib.h>;

#define N 1000

int Display( int *pData )
{
    int i&#59;

    for( i = 0&#59; i < N&#59; i ++ ) {
        printf( &quot;%5d&quot;, pData )&#59;
        if( (i+1) % 22 == 0 ) {
            printf( &quot;\n&quot; )&#59;
        }
    }
    printf( &quot;\n\n&quot; )&#59;

    return 0&#59;
}


int Partition( int *pData )
{
    int i&#59;
    int t1, t2&#59;
    int pos5start, pos5end&#59;
    int iFlag&#59;
    int iNo4Flag&#59;

    pos5start = 0&#59;  
    pos5end = 0&#59;
    t1 = 0&#59;
    t2 = 0&#59;
    iFlag = 0&#59;
    iNo4Flag = 0&#59;

    for( i = 0&#59; i < N&#59; i ++ ) {
        if( pData < 5 ) {
            t1 = pData[0]&#59;
            pData[0] = pData&#59;
            pData = t1&#59;
            break&#59;
        }
    }

    if( i == N ) {

        iNo4Flag = 1&#59;

        for( i = 0&#59; i < N&#59; i ++ ) {
            if( pData >; 5 ) {
                if( t2 == 0 ) {
                    t2 = pData&#59;
                }
                pData = pData - t2 + 4&#59;
            }
        }

        for( i = 0&#59; i < N&#59; i ++ ) {
            if( pData < 5 ) {
                t1 = pData[0]&#59;
                pData[0] = pData&#59;
                pData = t1&#59;
                break&#59;
            }
        }
    }

    for( i = 1&#59; i < N&#59; i ++ ) {
        if( pData == 5 ) {
            t1 = pData[1]&#59;
            pData[1] = pData&#59;
            pData = t1&#59;
            break&#59;
        }
    }

   

    for( i = 2&#59; i < N&#59; i ++ ) {
        if( pData >; 5 ) {
            t1 = pData[2]&#59;
            pData[2] = pData&#59;
            pData = t1&#59;
            break&#59;
        }
    }

    for( i = 0&#59; i < N&#59; i ++ ) {

        if( (0==iFlag) &amp;&amp; (pData<5) ) {
            continue&#59;
        }

        if( (0==iFlag) &amp;&amp; (pData==5) ) {
            iFlag = 1&#59;
            pos5start = i&#59;
            continue&#59;
        }

        if( (1==iFlag) &amp;&amp; (pData==5) ) {
            continue&#59;
        }

        if( (1==iFlag) &amp;&amp; (pData>;5) ) {
            pos5end = i - 1&#59;
            iFlag = 2&#59;
            continue&#59;
        }

        if( (1==iFlag) &amp;&amp; (pData<5) ) {
            pData[pos5start] = pData&#59;
            pData = 5&#59;
            pos5start ++&#59;
            continue&#59;
        }

        if( (2==iFlag) &amp;&amp; (pData>;5) ) {
            continue&#59;
        }

        if( (2==iFlag) &amp;&amp; (pData<5) ) {
            t1 = pData[pos5end+1]&#59;
            pData[pos5end+1] = 5&#59;
            pData[pos5start] = pData&#59;
            pData = t1&#59;
            pos5start ++&#59;
            pos5end ++&#59;
            continue&#59;
        }

        if( (2==iFlag) &amp;&amp; (pData==5) ) {
            t1 = pData[pos5end+1]&#59;
            pData[pos5end+1] = 5&#59;
            pData = t1&#59;
            pos5end ++&#59;
            continue&#59;
        }
    }


    if( iNo4Flag == 1 ) {
        for( i = 0&#59; i < N&#59; i ++ ) {
            if( pData != 5 ) {
                pData = pData - 4 + t2&#59;&#59;
            }
        }
    }


    return 0&#59;
}

main()
{

    int i, *data&#59;

    data = (int *)malloc( sizeof(int)*N )&#59;
    if( NULL == data ) {
        perror( &quot;malloc fail&quot; )&#59;
        return -1&#59;
    }

    srand( time(NULL) )&#59;

    for( i = 0&#59; i < N&#59; i ++ ) {
        data =  1 + rand()%20&#59;
    }

    i = rand()%N&#59; data = 5&#59;
    i = rand()%N&#59; data = 5&#59;
    i = rand()%N&#59; data = 5&#59;
   


/*    Display( data )&#59;  */
    Partition( data )&#59;
/*    Display( data )&#59; */


    return 0&#59;
}

蓝色键盘

原帖由 "aegis" 发表：
菜鸟啊菜鸟，一群菜鸟！谭笨蛋的书看多了吧？只会照抄，没有一点脑子！

无论干什么，都要先考虑算法！

比 x 小的放在前面，比 x 大的放到后面！算法都告诉你们了，还不会？！

从前面开始，比 x 小，则跳过，比 x 大，和“最后”的那个交换，
反复进行；直到 ok。

int MyCode ()  // return x position
{
    long L [ 1000 ], l;
    int s, e;

    for ( s = 0, e = 999; s < e
    {
        if ( L [ s ] >; X )
        {
            l = L [ e ];
            L [ e -- ] = L [ s ];
            L [ s ] = l;
        }
        else
            s ++;
    }
    return s;
}

上面假定数组里没有其他和 X 相同的数值
简单吧？一群菜鸟

当然还可以有更好的算法，不是菜鸟的自己做吧

呵呵，有意思，建议定义一个100000000的long数据，然后做所谓腾挪大法，建议你构造一个哈希函数，看看效率如何？？？

menp9999

原帖由 "离了水的蛤蟆"]e_room 发表：
) ......这一段）
如果两头都停止在等于X的数的位置，那么从它们之间找到一个不等于X的数,
与两端的数进行互换，这样循环就能够继续下去，直至last_less_room和last_more_room之间全部都是X。

好思路.
这个题目的目的其实并没有要求排序.
实际就是从第一个数查找大于X的数,查到一个就相应的从最后反向查找小于X的数,交换一下.
我想这位朋友的答案就是最后的答案了.

menp9999

[quote]原帖由 "蓝色键盘"]呛牵?幸馑迹?ㄒ槎ㄒ逡桓?00000000的long数据，然后做所谓腾挪大法，建议你构造一个哈希函数，看看效率如何？？？[/quote 发表：

构造HASH不符合题目的意思,在最坏的情况呢?你的空间消耗是多少?而且HASH要设计指针,看起来指针没有空间消耗,其实会没有么?

wangz

原帖由 "aegis" 发表：
;
        }
        else
            s ++;
    }
    return s;
}

上面假定数组里没有其他和 X 相同的数值
简单吧？一群菜鸟

当然还可以有更好的算法，不是菜鸟的自己做吧

同意这位仁兄意见，这只是腾挪，又不是排序！！

biansj

这是老头我的解答

我的平台为：
winxp-cgywin
intel-p4-1.8
512M
gcc编译器

结果：

Number of elements to sort=>;10000000
Seed for random number generator (integer)=>;1
X=356357611
L[]=1481765933 1085377743 1270216262 1191391529 812669700 553475508 445349752 1344887256 730417256 1812158119 147699711 880268
1 1889772843 686078705 2105754108 182546393 1949118330 220137366 1979932169 1089957932 1873226917 ...(too much number, ignore)
-----------------------------------------------------------------
Check :correct.
Time : 0.270 seconds.
-----------------------------------------------------------------
position=1660433
L[]=126327593 46166452 192565618 137712912 20451713 225182725 97345414 103854117 33560245 261810579 147699711 24076199 2350035
347814638 174345139 182546393 167555317 220137366 271580728 167974811 331088965 ...(too much number, ignore)

Number of elements to sort=>;50000000
Seed for random number generator (integer)=>;1
X=1755472876
L[]=1481765933 1085377743 1270216262 1191391529 812669700 553475508 445349752 1344887256 730417256 1812158119 147699711 88026835
1 1889772843 686078705 2105754108 182546393 1949118330 220137366 1979932169 1089957932 1873226917 ...(too much number, ignore)
-----------------------------------------------------------------
Check :incorrect.
Time : 0.811 seconds.
-----------------------------------------------------------------
position=40870704
L[]=1481765933 1085377743 1270216262 1191391529 812669700 553475508 445349752 1344887256 730417256 739188062 147699711 880268351
125787503 686078705 1039920646 182546393 350985345 220137366 503919052 1089957932 996044826 ...(too much number, ignore)

1. 
   
2. int Partition(long *L, int n, long X)
   
3. 
   
4. {
   
5.         //在这里插入你的代码
   
6. 
   
7.         int start_pos=0,end_pos=n-1,tmp,dup_num=0;
   
8. 
   
9.         for(;;)
   
10.         {
    
11. 
    
12.                 if(end_pos-start_pos-dup_num==0||(end_pos-start_pos-dup_num==1&&L[start_pos]<=L[end_pos-dup_num]))
    
13. 
    
14.                         break;
    
15. 
    
16.                 while(L[start_pos++]<X&&start_pos!=end_pos-dup_num);
    
17. 
    
18.                 start_pos==0? : start_pos--;
    
19. 
    
20.                 while(L[end_pos--]>;X&&start_pos!=end_pos-dup_num);
    
21.                
    
22.                 end_pos==n-1? : end_pos++;
    
23. 
    
24.                 if(start_pos!=end_pos-dup_num)
    
25. 
    
26.                         switch(L[end_pos]==X)
    
27.                         {
    
28. 
    
29.                                 case 1:
    
30. 
    
31.                                         if(L[start_pos]==X)
    
32.                                         {
    
33.                                                 dup_num++ ;
    
34.                                                 tmp=L[start_pos];
    
35.                                                 L[start_pos]=L[end_pos-dup_num];
    
36.                                                 L[end_pos-dup_num]=tmp;
    
37.                                         }
    
38.                                         else
    
39.                                         {
    
40.                                                 tmp=L[start_pos];
    
41.                                                 L[start_pos]=L[end_pos];
    
42.                                                 L[end_pos]=tmp;
    
43. 
    
44.                                                 tmp=L[start_pos];
    
45.                                                 L[start_pos]=L[end_pos-dup_num-1];
    
46.                                                 L[end_pos-dup_num-1]=tmp;
    
47. 
    
48.                                                 end_pos--;
    
49.                                         }
    
50. 
    
51.                                         break;
    
52. 
    
53.                                 case 0:
    
54. 
    
55.                                         tmp=L[start_pos],L[start_pos]=L[end_pos],L[end_pos]=tmp;
    
56. 
    
57.                                         break;
    
58. 
    
59.                                 default:
    
60. 
    
61.                                         break;
    
62. 
    
63.                         }
    
64. 
    
65.         }
    
66. 
    
67.         return end_pos;
    
68. 
    
69. }
    

复制代码

非常感谢samhood的这种交流方式，还有程序模板！！

真省力气，算法我也不说明了，反正也没人看。