[已解决]编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)

Kitty喜欢小鱼干

/*----------------------本算法有误，请各位检查并帮助修改-------------------*/

//编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。

//例如：{1, 2, 3, 4, -1, 1, -2, -1, -4} -->  {-4, -1, -2, -1, 4, 1, 3, 2, 1}

#include <stdio.h>

void Func(int list[], int n){
    int i=0, j=n-1, temp, k;
    int *List;
    while( i < j ){
        while (list[i]<0) i++;
        while (list[j]>0) j--;

        if( list[i] > list[j] ){
            temp = list[i];
            list[i] = list[j];
            list[j] = temp;
        }
    }

    for( k=0; k<n; k++ ){
        List[k] = list[k];
        printf("%d", List[k]);
    }
    return;
}

int main(){
    int a[9] = {1, 2, 3, 4, -1, 1, -2, -1, -4};
    Func(a, 9);
    return 0;
}

最佳答案

月排行榜 / 总排行榜

人造人

2018-8-14 14:58:21

无符号整形 发表于 2018-8-14 17:00
额 你这个复杂度是O(n^2)了呀。

这次应该没问题了

1. //编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。
   
2. //例如：{1, 2, 3, 4, -1, 1, -2, -1, -4} -->  {-4, -1, -2, -1, 4, 1, 3, 2, 1}
   
3. 
   
4. #include <stdio.h>
   
5. 
   
6. void Swap(int *a, int *b)
   
7. {
   
8.         int tmp = *a;
   
9.         *a = *b;
   
10.         *b = tmp;
    
11. }
    
12. 
    
13. void Fun(int data[], int len)
    
14. {
    
15.         int dest = 0;
    
16. 
    
17.         for(int i = 0; i < len; ++i)
    
18.         {
    
19.                 if(data[i] < 0)
    
20.                 {
    
21.                         Swap(&data[i], &data[dest++]);
    
22.                 }
    
23.         }
    
24. }
    
25. 
    
26. void Print(int data[], int len)
    
27. {
    
28.         for(int i = 0; i < len; ++i)
    
29.         {
    
30.                 printf("%d ", data[i]);
    
31.         }
    
32.         printf("\n");
    
33. }
    
34. 
    
35. int main(void)
    
36. {
    
37.         int a[9] = {1, 2, 3, 4, -1, 1, -2, -1, -4};
    
38.         //Func(a, 9);
    
39.         Fun(a, 9);
    
40.         Print(a, 9);
    
41.         return 0;
    
42. }
    

复制代码

跳转到最佳答案楼层

人造人

无符号整形 发表于 2018-8-14 17:00
额 你这个复杂度是O(n^2)了呀。

这次应该没问题了

1. //编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。
   
2. //例如：{1, 2, 3, 4, -1, 1, -2, -1, -4} -->  {-4, -1, -2, -1, 4, 1, 3, 2, 1}
   
3. 
   
4. #include <stdio.h>
   
5. 
   
6. void Swap(int *a, int *b)
   
7. {
   
8.         int tmp = *a;
   
9.         *a = *b;
   
10.         *b = tmp;
    
11. }
    
12. 
    
13. void Fun(int data[], int len)
    
14. {
    
15.         int dest = 0;
    
16. 
    
17.         for(int i = 0; i < len; ++i)
    
18.         {
    
19.                 if(data[i] < 0)
    
20.                 {
    
21.                         Swap(&data[i], &data[dest++]);
    
22.                 }
    
23.         }
    
24. }
    
25. 
    
26. void Print(int data[], int len)
    
27. {
    
28.         for(int i = 0; i < len; ++i)
    
29.         {
    
30.                 printf("%d ", data[i]);
    
31.         }
    
32.         printf("\n");
    
33. }
    
34. 
    
35. int main(void)
    
36. {
    
37.         int a[9] = {1, 2, 3, 4, -1, 1, -2, -1, -4};
    
38.         //Func(a, 9);
    
39.         Fun(a, 9);
    
40.         Print(a, 9);
    
41.         return 0;
    
42. }
    

复制代码

人造人

看不懂你的代码，我自己写了一个

1. //编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。
   
2. //例如：{1, 2, 3, 4, -1, 1, -2, -1, -4} -->  {-4, -1, -2, -1, 4, 1, 3, 2, 1}
   
3. 
   
4. #include <stdio.h>
   
5. 
   
6. #if 0
   
7. void Func(int list[], int n)
   
8. {
   
9.         int i = 0, j = n - 1, temp, k;
   
10.         int *List;
    
11. 
    
12.         while(i < j)
    
13.         {
    
14.                 while(list < 0) i++;
    
15.                 while(list[j] > 0) j--;
    
16. 
    
17.                 if(list > list[j])
    
18.                 {
    
19.                         temp = list;
    
20.                         list = list[j];
    
21.                         list[j] = temp;
    
22.                 }
    
23.         }
    
24. 
    
25.         for(k = 0; k < n; k++)
    
26.         {
    
27.                 List[k] = list[k];
    
28.                 printf("%d", List[k]);
    
29.         }
    
30.         return;
    
31. }
    
32. #endif
    
33. 
    
34. void Swap(int *a, int *b)
    
35. {
    
36.         int tmp = *a;
    
37.         *a = *b;
    
38.         *b = tmp;
    
39. }
    
40. 
    
41. void Fun(int data[], int len)
    
42. {
    
43.         for(int i = 0; i < len; ++i)
    
44.         {
    
45.                 if(data[i] > 0)
    
46.                 {
    
47.                         for(int j = i + 1; j < len; ++j)
    
48.                         {
    
49.                                 if(data[j] < 0)
    
50.                                 {
    
51.                                         Swap(&data[i], &data[j]);
    
52.                                         break;
    
53.                                 }
    
54.                         }
    
55.                 }
    
56.         }
    
57. }
    
58. 
    
59. void Print(int data[], int len)
    
60. {
    
61.         for(int i = 0; i < len; ++i)
    
62.         {
    
63.                 printf("%d ", data[i]);
    
64.         }
    
65.         printf("\n");
    
66. }
    
67. 
    
68. int main(void)
    
69. {
    
70.         int a[9] = {1, 2, 3, 4, -1, 1, -2, -1, -4};
    
71.         //Func(a, 9);
    
72.         Fun(a, 9);
    
73.         Print(a, 9);
    
74.         return 0;
    
75. }
    

复制代码

无符号整形

人造人 发表于 2018-8-14 16:08
看不懂你的代码，我自己写了一个

额 你这个复杂度是O(n^2)了呀。

人造人

无符号整形 发表于 2018-8-14 17:00
额 你这个复杂度是O(n^2)了呀。

O(n)就是一次循环
一次循环要如何完成这个功能？

无符号整形

人造人 发表于 2018-8-14 17:08
这次应该没问题了

好像对的……
我怎么没想到……

人造人

无符号整形 发表于 2018-8-14 17:10
好像对的……
我怎么没想到……

^_^

claws0n

人造人 发表于 2018-8-14 17:08
这次应该没问题了

负数值不对，还是我理解题目错了？?

人造人

claws0n 发表于 2018-8-14 17:33
负数值不对，还是我理解题目错了？?

//编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。

claws0n

人造人 发表于 2018-8-14 17:37
//编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。

我知道，但排序需不需要考虑？

人造人

claws0n 发表于 2018-8-14 17:47
我知道，但排序需不需要考虑？

这个题目没有要求排序

claws0n

人造人 发表于 2018-8-14 17:47
这个题目没有要求排序

好~~

Kitty喜欢小鱼干

人造人 发表于 2018-8-14 14:58
这次应该没问题了

谢谢！原来我最需要的其实是这一节代码。

void Print(int data[], int len)
{
        for(int i = 0; i < len; ++i)
        {
                printf("%d ", data);
        }
        printf("\n");
}