挑战数组腾挪大法

fenglsh

可以用快速排序法得到

fenglsh

//说明，定义另一个变量k，并假设k为数组L的一个元素，即数组L的总共长度为1001，
//而且k为最后一个元素，并假设元素X就放在那(k相当于L[1000])，
//那么就可以使用快速排序法得到:

i=0&#59;
j=1000 -1&#59;

while(X>;=L)i++&#59;
k=L&#59;

while(i<j)
{
   while(X<=L[j])j--&#59;
   L=L[j]&#59;
   while(X>;=L)i++&#59;
   L[j]=L&#59;

}

samhoo

fenglsh,快速排序法的时间复杂度为O(nlogn)，代价太大。

而且排序问题的时间复杂度不可能再比O(nlogn)更优，这是已被证明的命题。

所以我觉得思路不能往这上面靠，我们无需如此强的的信息--排序。

离了水的蛤蟆

#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,4,6,9,2,0}&#59;
  int   last_less_room, last_more_room,
        object_current_room&#59;

  for (last_less_room = 0, last_more_room = MAX_SIZE -1 &#59;
                last_less_room < last_more_room&#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] == 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;
}
}

aegis

菜鸟啊菜鸟，一群菜鸟！谭笨蛋的书看多了吧？只会照抄，没有一点脑子！

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

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

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

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 )
        {
            l = L [ e ]&#59;
            L [ e -- ] = L [ s ]&#59;
            L [ s ] = l&#59;
        }
        else
            s ++&#59;
    }
    return s&#59;
}

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

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

samhoo

[这个贴子最后由samhoo在 2002/10/25 07:12pm 编辑]

这是aegis的算法得出的结果：

X=5
原始：2 7 3 1 5 6
-----交换过程--------
2 7 3 1 5 6
2 7 3 1 5 6
2 6 3 1 5 7
2 5 3 1 6 7
2 5 3 1 6 7
-----交换过程--------
结果：2 5 3 1 6 7

很遗憾，牛哥您没能达到题目的要求。不仅仅是“假定数组里没有其他和 X 相同的数值
”这个条件没满足。不过还是谢谢你的关注。

aegis

x ？

samhoo

x=5

wwjxjtu

void specsort(long L[],long X,int pos){
int i,j,tmp1,tmp2=999&#59;
for(i=0&#59;i<1000&#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;
}

samhoo

[这个贴子最后由samhoo在 2002/10/26 12:13pm 编辑]

实在是愚钝，费了牛劲才把它实现出来。
MoveIt是完成交换的核心函数。
Check用于检验结果的正确性。

MakeRandomList生成随机数组
CreateList分配内存。
它们无关主题，图省事直接从别的书抄过来了。

不知道还有没有更明了的算法。

wwjxjtu算法复杂度为O(n^2)，代价太高。
蛤蟆兄不如简单说明一下思路。


#include<stdio.h>;

/*
* 问题：给定一个数组long L[n],且已知X是其中的一个元素, 请调整该数组
* 使得所有小于X的元素位于数组左边, 大于X的元素位于数组右边, 并得到X
* 在数组中的下标.
*
* 要求：1)如何不使用额外的数组&#59; 2)时间复杂度不大于O(n)
*
* 算法: left = 0&#59; right = n - 1&#59;
* 1)比较L[left]和X, 如果小于X, left加1, 重复本步骤&#59;
*   如果等于X跳到步骤2&#59; 如果大于X, 跳到步骤3.
* 2)比较L[left]以右的数, 如果小于X,交换之, left加1, 重复本步骤
*   如果等于X, left加1, 重复本步骤&#59; 如果大于X, 跳到步骤3.
* 3)做法与步骤1相似, right向左移动.
* 4)做法与步骤2相似, right向左移动.
* 5)交换L[left], L[right]&#59;
*/

#define DISPLAY \
    { \
    int i&#59; \
    printf(&quot;L[]=&quot&#59; \
    for (i = 0&#59; i < num&#59; i++) \
       printf(&quot;%d &quot;, L)&#59; \
    printf(&quot;\n&quot&#59; \
    }

int  Check(long *L, int num, int X, int position)&#59;
int  SWAP(long *L, int a, int b)&#59;
long *MakeRandomList(int *num)&#59;
long *CreateList(int n)&#59;
int  MoveIt(long *L, int n, long X)
{

    int left = 0, left_ep = 0, right = n -1, right_ep = n - 1&#59;

    /* 大数:大于X的数&#59; 小数:小于X的数 */
    while(left < right){
        /* 找到左边用于交换的大数 */
        while( (L[left] <= X) &amp;&amp; (left < right) ){
            if (L[left] < X){ /* 如果是小数,向右移动 */
            left++&#59;
            left_ep++&#59;
            }
            else{
                while((L[left] == X) &amp;&amp; (left <= right))
                left++&#59;

                if (left >; right)
                break&#59;

                SWAP(L, left, left_ep)&#59;
                if (L[left] < X){
                    left++&#59;
                    left_ep++&#59;
                }
                else
                    left = left_ep&#59;
            }
        }
   
        /* 找到右边用于交换的小数 */
        while( (L[right] >;= X) &amp;&amp; (left < right) ){
            if (L[right] >; X){
                right--&#59;
                right_ep--&#59;
            }
            else{
                while((L[right] == X) &amp;&amp; (left <= right))
                    right--&#59;

                if (left >; right)
                    break&#59;

                SWAP(L, right, right_ep)&#59;

                if (L[right] >; X){
                    right--&#59;
                    right_ep--&#59;
                }
                else
                    right = right_ep&#59;
            }
        }

        /* 交换 */
        if (left < right){
            SWAP(L, left, right)&#59;
            left++&#59;
            left_ep++&#59;
            right--&#59;
            right_ep--&#59;
        }
    }
    return left_ep&#59;
}

int main()
{
long X&#59;
long *L&#59;
//long L[]={5,5,5,5,5,5,7,1,6,8}&#59;
int  num = 10&#59;
int  pos = 0&#59;

L=MakeRandomList(&amp;num)&#59;
X = L[(num - 1) / 2]&#59;

printf(&quot;X=%ld\n&quot;, X)&#59;
DISPLAY
    printf(&quot;--------------------------------------------------------------------\n&quot&#59;

pos = MoveIt(L, num, X)&#59;

if (Check(L, num, X, pos))
printf(&quot;incorrect.\n&quot&#59;
else
printf(&quot;correct.\n&quot&#59;

    printf(&quot;--------------------------------------------------------------------\n&quot&#59;
printf(&quot;position=%ld\n&quot;, pos)&#59;
DISPLAY

return 0&#59;
}

long *CreateList(int n)
/* Allocates memory for an array of n longs */
{
   long *L&#59;

   L = (long *) malloc( n * sizeof(long) )&#59;
   if( L == NULL) { /* Exit program if memory cannot be allocated */
      printf(&quot;\nCannot allocate enough memory for list.\n&quot&#59;
      exit(0)&#59;
   }

   return (L)&#59;
}

long *MakeRandomList(int *num)
{
   long *L&#59;               /* pointer to List */
   unsigned int seed&#59;     /* seed for random number generator */
   int i&#59;                 /* index of for loop */

   printf(&quot;\nNumber of elements to sort=>;&quot&#59;
   scanf(&quot;%d&quot;,num)&#59;

   printf(&quot;\nSeed for random number generator (integer)=>;&quot&#59;
   scanf(&quot;%d&quot;,&amp;seed)&#59;
   srand(seed)&#59;

   /* Allocate memory for # of elements. If memory cannot be allocated,
      display message and terminate program. Read in the elements. */
   L = CreateList(*num)&#59;
   if (L == NULL) {
      printf(&quot;\nCannot allocate enough memory for number list.\n&quot&#59;
      exit(0)&#59;
   }
   for (i = 0&#59; i < *num&#59; ++i)
      L = rand()&#59;

   return(L)&#59;           /* Return the List */
}

int Check(long *L, int num, int X, int position)
{
int i, lpos, rpos&#59;

for (i = 0&#59; i < num&#59; i++)
if (L == X)
break&#59;
lpos = i&#59;

for (i = num - 1&#59; i >;= 0&#59; i--)
if (L == X)
break&#59;
rpos = i&#59;

for (i = lpos&#59; i <= rpos&#59; i++)
if (L != X)
return -1&#59;

for (i = 0&#59; i < lpos&#59; i++)
if (L >; X)
return -1&#59;

for (i = num - 1&#59; i >; rpos&#59; i--)
if (L < X)
return -1&#59;

if ( (position < lpos) || (position >; rpos) )
return -1&#59;

return 0&#59;
}


int SWAP(long *L, int a, int b)
{
long temp&#59;

temp = L[a]&#59;
L[a] = L&#59;
L = temp&#59;
return 0&#59;

}

这是几组输出结果：
X=5
L[]=5 5 5 5 5 5 7 1 6 8
--------------------------------------------------------------------
correct.
--------------------------------------------------------------------
position=1
L[]=1 5 5 5 5 5 5 7 6 8


Number of elements to sort=>;10

Seed for random number generator (integer)=>;1
X=31051
L[]=16838 5758 10113 17515 31051 5627 23010 7419 16212 4086
--------------------------------------------------------------------
correct.
--------------------------------------------------------------------
position=9
L[]=16838 5758 10113 17515 5627 23010 7419 16212 4086 31051

欢迎给出反例子（如果有的话）