论坛 › 数据结构与算法 › 编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)

Kitty喜欢小鱼干 发表于 2018-8-14 14:58:20

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

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

//编写一个算法，将数组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<0) i++;
      while (list>0) j--;

      if( list > list ){
            temp = list;
            list = list;
            list = temp;
      }
    }

    for( k=0; k<n; k++ ){
      List = list;
      printf("%d", List);
    }
    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:10 编辑

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

这次应该没问题了


//编写一个算法，将数组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 Swap(int *a, int *b)
{
        int tmp = *a;
        *a = *b;
        *b = tmp;
}

void Fun(int data[], int len)
{
        int dest = 0;

        for(int i = 0; i < len; ++i)
        {
                if(data < 0)
                {
                        Swap(&data, &data);
                }
        }
}

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

int main(void)
{
        int a = {1, 2, 3, 4, -1, 1, -2, -1, -4};
        //Func(a, 9);
        Fun(a, 9);
        Print(a, 9);
        return 0;
}

人造人 发表于 2018-8-14 16:08:34

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

//编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)。
//例如：{1, 2, 3, 4, -1, 1, -2, -1, -4} -->{-4, -1, -2, -1, 4, 1, 3, 2, 1}

#include <stdio.h>

#if 0
void Func(int list[], int n)
{
        int i = 0, j = n - 1, temp, k;
        int *List;

        while(i < j)
        {
                while(list < 0) i++;
                while(list > 0) j--;

                if(list > list)
                {
                        temp = list;
                        list = list;
                        list = temp;
                }
        }

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

void Swap(int *a, int *b)
{
        int tmp = *a;
        *a = *b;
        *b = tmp;
}

void Fun(int data[], int len)
{
        for(int i = 0; i < len; ++i)
        {
                if(data > 0)
                {
                        for(int j = i + 1; j < len; ++j)
                        {
                                if(data < 0)
                                {
                                        Swap(&data, &data);
                                        break;
                                }
                        }
                }
        }
}

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

int main(void)
{
        int a = {1, 2, 3, 4, -1, 1, -2, -1, -4};
        //Func(a, 9);
        Fun(a, 9);
        Print(a, 9);
        return 0;
}

无符号整形 发表于 2018-8-14 17:00:47

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

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

人造人 发表于 2018-8-14 17:04:31

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

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

无符号整形 发表于 2018-8-14 17:10:47

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

好像对的……
{:10_266:}我怎么没想到……

人造人 发表于 2018-8-14 17:20:18

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

^_^

claws0n 发表于 2018-8-14 17:33:33

本帖最后由 claws0n 于 2018-8-14 17:36 编辑

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

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

人造人 发表于 2018-8-14 17:37:56

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

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

claws0n 发表于 2018-8-14 17:47:17

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

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

人造人 发表于 2018-8-14 17:47:58

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

这个题目没有要求排序

claws0n 发表于 2018-8-14 17:49:55

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

好~~

Kitty喜欢小鱼干 发表于 2018-8-15 15:34:59

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

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

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

查看完整版本: 编写一个算法，将数组a中所有负数移到整数之前，且时间复杂度是 O(n)