挑战数组腾挪大法

离了水的蛤蟆

您的高程调试过吗？

aegis

sorry, 少打了一个符号...


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

   for ( s = 0, e = 999&#59; s < e&#59
   {
       if ( L [ s ] >;= X )  // !!!!!!!! should be >;= X
       {
           l = L [ e ]&#59;
           L [ e -- ] = L [ s ]&#59;
           L [ s ] = l&#59;
       }
       else
           s ++&#59;
   }
   return s&#59;
}

aegis

菜鸟！知道思路了还弄那么复杂，绝对菜鸟！

aegis

对比一下 samboo 和 aegis 的程序……

什么叫 c 语言的简洁美？

所谓菜鸟，就是把简单的事情越搞越复杂
所谓高手，就是把看似复杂的事情弄简单

还有 samboo 你的 swap 实现不是 c 程序员的，是标准的谭笨蛋的 basic
要不要我教教你？

samhoo

aegis，拜托你把程序调过了，再来充大佬，行吗？
别以为记住了几个运算符的优先级，就可以跳来跳去，娱乐大众。

你的两个错误结果：
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086
--------------------------------------------------------------------
incorrect.
--------------------------------------------------------------------
position=8
L[]=16838 5758 10113 17515 4086 5627 23010 7419 16212 31051

X=5
L[]=7 9 5 1 5 5 5 8 5 1
--------------------------------------------------------------------
incorrect.
--------------------------------------------------------------------
position=2
L[]=1 1 5 5 5 5 8 5 9 7

aegis

你是一个大笨蛋，没看我说的吗？这个程序适用于 L [1000] 中没有重复的 X&#59;

问题：给定一个数组long L[1000],且已知X是其中的 ！一个！ 元素，如何使得
小于X的元素位于数组左边，大于X的元素位于数组右边，并得到X在数组中的下标。

7 9 5 1 5 5 5 8 5 1   里面有几个 5 ?

你不识数啊？

aegis

你的算法的 时间复杂度是多少？ O(n)? 呸！

beggar

下面引用由aegis在 2002/10/25 04:05pm 发表的内容：
菜鸟啊菜鸟，一群菜鸟！谭笨蛋的书看多了吧？只会照抄，没有一点脑子！
无论干什么，都要先考虑算法！
比 x 小的放在前面，比 x 大的放到后面！算法都告诉你们了，还不会？！
从前面开始，比 x 小，则跳过，比 x ...

这位非菜鸟,你好
谭笨蛋?你说的是谭浩强谭老先生吗?谭老先生的书怎么了?你看过吗?你知道谭老先生的书的目的是什么吗?我记得我看的第一本C语言的书就是谭老先生的书.是他让我认识了C,试问这里有几位没有看过谭老先生的书?又有几个不知道谭老先生呢?单这点.老先生让我敬佩.他的书是给初学者认识C接解C而不是要把读者培养成为工程师或程序员.网上许多人说老先生的书看后什么都懂,但就是不会编程.这说明老先生的目的已经达到了.懂而不会编程?我不知道哪个人能把什么东西看会的.我也不知道为什么那么多学校为什么要把老先生的书作为学生学习C的第一本教材.如果说有一本书可以适用于一个程序员的各个阶段,我很想要这本书,你有吗?望借我一看.如果你根本没有看过老先生的书我想你没有资格对老先生的书作任何评价.


话说远了,就以这个贴子来说吧.我很欣慰你还知道有算法.我也很高兴又认识了你这么一位&quot;非菜鸟&quot;.更高兴的是你居然也知道你的算法对原始数据有要求,而且是要求X在这么多数中不能重复.
你的程式是以1000个数的数组.1000个数中不能有重复的数?是原始数据要求算法还是算法来决定原始数据.我这个菜鸟不太清楚,忘点明.如果就为了1000个数就要用算法,还要考虑时间空间复杂度? 我不知道你脑子里有没有时间空间的概念. 不知道你的&quot;算法&quot;是否有实用价值.上万,百万个数有没有可能不重复?是否还要求原始数据已经排好序你直接找就行了???

  说起来好象很容易啊.菜鸟们随便改改就行了,要解决上面说的问题你觉得随便改改就行吗?

我很想听听&quot;高手&quot;的&quot;高见&quot;.你如何解决这个问题.希望你只是随便改改而没有浪费你太多的时间.

wwjxjtu

声明一下，我的算法的复杂度不是O(n^2),而是O(n),如果写成下面这样，将更明显些(不过以前写的是有些问题(int pos应为int *pos)，在网吧上网有些匆忙,现在改一下)：
int specsort(long L[],long X){
int i,j,tmp1,tmp2=999,pos&#59;
for(i=0&#59;i<tmp2&#59;i++){
if(L>;X){
for(j=tmp2&#59;j<i&#59;j--){
if(L[j]<x){
tmp=L[j]&#59;
L[j]=L&#59;
L=tmp&#59;
tmp2=j&#59;
break&#59;
}
}
if(j==i) break&#59;
}
else if(L==x) pos=i&#59;
}
}
tmp=L[pos]&#59;
L[pos]=L[tmp2-1]&#59;
L[tmp2-1]=tmp&#59;
pos=tmp2-1&#59;
return pos&#59;
}

离了水的蛤蟆

#include        <stdio.h>;
#include        <fcntl.h>;
#include        <sys/errno.h>;
extern int      errno&#59;
#define         MAX_SIZE        10
#define         OBJECT_NUMBER   7

#define         INT_EXCHANGE(a,b) \
       {\
               int     temp_int&#59; \
               temp_int = my_array[a]&#59; \
               my_array[a] = my_array&#59; \
               my_array = temp_int&#59; \
               }

main ()
{
int   my_array[MAX_SIZE] = {3,5,7,1,8,7,6,7,2,0}&#59;
int   last_less_room, last_more_room,
       object_current_room, temp_room&#59;

for (last_less_room = 0, last_more_room = MAX_SIZE -1 &#59;
               last_less_room < last_more_room&#59
   {
{
int i&#59;
for (i=0&#59; i<MAX_SIZE&#59; i++) printf (&quot;%d &quot;, my_array)&#59;
printf (&quot;\n&quot&#59;
}
     while (my_array[last_less_room] < OBJECT_NUMBER) last_less_room ++&#59;
     while (my_array[last_more_room] >; OBJECT_NUMBER) last_more_room --&#59;
     if (last_less_room >;= last_more_room)
       {
         break&#59;
       }

     if (my_array[last_less_room] == my_array[last_more_room])
       {
for (temp_room = last_less_room+1&#59;
(temp_room<(last_more_room-1))
&amp;&amp; (my_array[temp_room] == OBJECT_NUMBER)&#59; temp_room++)&#59;
if (my_array[temp_room] == OBJECT_NUMBER)
   {
     break&#59;
   }
else if (my_array[temp_room] >; OBJECT_NUMBER)
   {
     INT_EXCHANGE (temp_room, last_more_room)&#59;
   }
else if (my_array[temp_room] < OBJECT_NUMBER)
   {
     INT_EXCHANGE (temp_room, last_less_room)&#59;
   }

continue&#59;
       }

     if (my_array[last_less_room] == OBJECT_NUMBER)
       {
         object_current_room = last_less_room&#59;
         while (((last_less_room + 1) < (MAX_SIZE - 1))
               &amp;&amp; (my_array[last_less_room + 1] < OBJECT_NUMBER))
           {
             last_less_room ++&#59;
           }
         INT_EXCHANGE (last_less_room, object_current_room)&#59;
         if (((last_less_room + 1) < MAX_SIZE)
               &amp;&amp; (my_array[last_more_room] < OBJECT_NUMBER))
           {
             INT_EXCHANGE (last_less_room + 1, last_more_room)&#59;
           }
       }
     if (my_array[last_more_room] == OBJECT_NUMBER)
       {
         object_current_room = last_more_room&#59;
         while (((last_more_room - 1) >; 0)
               &amp;&amp; (my_array[last_more_room - 1] >; OBJECT_NUMBER))
           {
             last_more_room --&#59;
           }

         INT_EXCHANGE (last_more_room, object_current_room)&#59;
         if ((last_more_room >; 0)
               &amp;&amp; (my_array[last_less_room] >; OBJECT_NUMBER))
           {
             INT_EXCHANGE (last_more_room - 1, last_less_room)&#59;
           }
       }

   }
{
int i&#59;
for (i=0&#59; i<MAX_SIZE&#59; i++) printf (&quot;%d &quot;, my_array)&#59;
printf (&quot;\n&quot&#59;
}
}

输出的结果是：
3 5 7 1 8 7 6 7 2 0
3 5 1 7 0 7 6 7 2 8
3 5 1 0 7 2 6 7 7 8
3 5 1 0 2 7 6 7 7 8
3 5 1 0 2 6 7 7 7 8
3 5 1 0 2 6 7 7 7 8