一道面试题

tail_2003

：将一个数组中的所有素数移到数组的前面，而非素数移到后面，要求数据的位置不改变。多谢解答！

怪怪虎

原帖由 tail_2003 于 2006-8-22 22:26 发表
要求数据的位置不改变

什么意思

foolfoolbird

不知道要不要很高效的算法!
正在思考!
写了个垃圾的代码?
不知道能不能满足要求?
#include"stdio.h"
#include"math.h"
int isp(int x);
main()
{
int i;

int j=0;

int k=0;

int iData[10]={56,45,79,46,23,19,86,59,96,35};

int iData1[10];
for(i=0; i<10; i++)
{

   if(isp(iData[i]))
   {
  
   iData[j++]=iData[i];
  
   }
   else
   {
   
   iData1[k++]=iData[i];
  
   }

}

  k=0;

  for(i=j; i<10; i++)
  {

  iData[j++]=iData1[k++]   ;

  }

  for(i=0; i<10; i++)
  {

  printf("%d\n",iData[i]);

  }









}
再想想有什么高效一点的算法!

foolfoolbird

又想了一个看看这个怎么样?

1. 
   
2. 
   
3. 
   
4. #include"stdio.h"
   
5. #include"math.h"
   
6. int isp(int x);
   
7. main()
   
8. {
   
9.   int i;
   
10. 
    
11.   int j=0;
    
12. 
    
13.   int k=0;
    
14. 
    
15.   int t;
    
16. 
    
17.   int iData[10]={56,45,79,46,23,19,86,59,96,35};
    
18. 
    
19.   int iData1[10];
    
20.   for(i=0;i<10;i++)
    
21.   {
    
22.      if(isp(iData[i])==1)
    
23.     {
    
24. 
    
25.        for(k=i; k>j;k--)
    
26.      {
    
27.    
    
28.        t=iData[k];
    
29. 
    
30.        iData[k]=iData[k-1];
    
31. 
    
32.        iData[k-1]=t;
    
33.   
    
34.      }
    
35.   
    
36.       j++;
    
37.     }
    
38. 
    
39. 
    
40. }
    
41. 
    
42. for(i=0; i<10; i++)
    
43. {
    
44. 
    
45.   printf("%d\n",iData[i]);
    
46. 
    
47. }
    
48. 
    
49. }
    
50. 
    
51. int isp(int x)
    
52. {  int i;
    
53. 
    
54.    if(x==0||x==1)return 0;
    
55. 
    
56.    if(x==2)return 1;
    
57. 
    
58. 
    
59.    for(i=2;i<=sqrt(x);i++)
    
60.    if((x%i)==0)return 0;
    
61. 
    
62.          
    
63.    return 1;
    
64. 
    
65. }
    
66. 
    
67. 
    
68. 
    
69. 
    
70. 
    
71. 
    
72. 
    
73. 
    
74. 
    

复制代码

[ 本帖最后由 foolfoolbird 于 2006-8-23 00:07 编辑 ]

tail_2003

多谢foolfoolbird 的回答

yunongfang1981

从数组头到尾次检查每各数是否为素数，如果是,将数组前面的第一个非素数到该数的部分循环右移。

void main() {
int *Head = &iData[0];
int *End = &iData[9];
int *ptr_prm = Head;
int *ptr_data = Head;

for(;ptr_data <= End; ptr_data++)
{
    if(is_prm(*ptr_data)) {
        cycle_shift_right(&ptr_prm[1], ptr_data);
        ptr_prm++;
    }     
}

return; //finish

}

void cycle_shift_right(int *head, int *end)
{
    int temp = end[0];
    int *ptr = end;
    for(;ptr>head;ptr--){
        ptr[0] = ptr[-1];
    }
    head[0] = temp;   
}

[ 本帖最后由 yunongfang1981 于 2006-8-23 11:24 编辑 ]

foolfoolbird

呵呵！
都用的是轮换着把素数往前面移还有没有其他的好方法阿？

starxing

在 使用 另外两个数组，一个存放素数，一个放非素数，
最好把这两个数据合并。

japuser

#include <stdio.h>
#include <math.h>
int isp(int x);
void check(int y);
int i,j;
int a[10]={1,2,3,4,5,6,7,8,9,10};

main()
{
i=0;
while(i<10)
{
check(i);
printf("%d\n",a[i]);
i++;
}
}


int isp(int x)
{  int i;

   if(x==0||x==1)return 0;

   if(x==2)return 1;


   for(i=2;i<=sqrt(x);i++)
   if((x%i)==0)return 0;

         
   return 1;
}

void check(int x)
{
int temp;
if (x<10)
{
if(isp(a[x])==1)
check(x+1);
else
{
temp=a[x];
for(j=x;j>i;j--)
a[j]=a[j-1];
a[i]=temp;

}
}
}