挑战数组腾挪大法

b

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

要求：1）如何不使用额外的数组；2）时间复杂度不大于O(n)

有没有办法做到呢？</P>
<>题目：给定一个数组long L[n],且已知X是其中的一个元素(等于X的元素可能不止一个)，如何使得小于X的元素位于数组左边，大于X的元素位于数组右边，并得到X在数组中的下标。
要求：1）如何不使用额外的数组；2）时间复杂度不大于O(n)

提示:
A）为了能使讨论能集中于算法本身，而不是无关主旨的细节，下面附上模板程序，只需实现Partition函数即可验证程序是否正确。
B）如果大家能遵守一定的“八股”，我们沟通的效率会高些。(事实上,没有多少人可以有耐心看别人的代码，能看看算法以及测试结果就不错了,下面的“八股”直面这一事实)


八股：
一）算法说明
二）编译运行平台，机器类型/主频
三）Partition函数代码
四）至少给出前4组测试数据的结果
  i  )L[]={5,5,5,5,5,5,7,1,6,8}; n=10; X=5; （在main函数提供，注释掉其中一些语句即可）
  ii )n=10的随机数组
  iii)n=10,000,000的随机数组
  iv )n=50,000,000的随机数组(小心，别影响别人工作)
  v  ）其他自己认为具有“边界”特性的数组。


模板程序：
#include&lt;string.h&gt;
#include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;
#include&lt;time.h&gt;

#define DISPLAY \
  { \
  int i; \
  printf("L[]="); \
  for (i = 0; i &lt; num; i++){ \
     if (i &gt; 20 ){ \
         printf("...(too much number, ignore)"); \
         break; \
     } \
     printf("%d ", L); \
  } \
  printf("\n"); \
  }


int  Partition(long *L, int n, long X);  /* 实现这个函数 */
long *MakeRandomList(int *num);
long *CreateList(int n);
int  Check(long *L, int num, int X, int position);
int  SWAP(long *L, int a, int b);

int main()
{
long X;
long *L;
//long L[]={5,5,5,5,5,5,7,1,6,8};
int  num = 10;
int  pos = 0;
clock_t start_time, end_time;
double  duration;


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

printf("X=%ld\n", X);
DISPLAY
printf("-----------------------------------------------------------------\n");

start_time=clock();  
pos = Partition(L, num, X);
end_time=clock();

printf("Check :");  
if (Check(L, num, X, pos))
     printf("incorrect.\n");
else
     printf("correct.\n");
     
duration = (double)(end_time - start_time) / CLOCKS_PER_SEC;
printf("Time  : %.3f seconds.\n", duration);

printf("-----------------------------------------------------------------\n");
printf("position=%ld\n", pos);
DISPLAY

free(L);
return 0;
}


/*
* L：输入数组
* n：数组大小
* X：X元素
* 返回X在数组中的下标
*/
int  Partition(long *L, int n, long X)
{
//在这里插入你的代码
}


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

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

return (L);
}

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

printf("\nNumber of elements to sort=&gt;");
scanf("%d",num);

printf("Seed for random number generator (integer)=&gt;");
scanf("%d",&amp;seed);
srand(seed);

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

return(L);           /* Return the List */
}

int Check(long *L, int num, int X, int position)
{
int i, lpos = -1, rpos = -1;

for (i = 0; i &lt; num; i++)
   if (L == X){
     lpos = i;
     break;
   }
   else if (L &gt; X)
     return -1;

for (i = num - 1; i &gt;= 0; i--)
   if (L == X){
     rpos = i;
     break;
   }
   else if (L &lt; X)
     return -1;
           
if ((lpos == -1) || (rpos == -1) || (position &lt; lpos) || (position &gt;rpos))
   return -1;

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

return 0;
}

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

temp = L[a];
L[a] = L;
L = temp;
return 0;
}
</P>