3

我正在用 C# 编写代码来对数组进行排序,我想要右侧的所有负值和左侧的所有正值,不应该按降序排列

namespace SortApp
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] newInt = new int[] { 5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10 };
            int size = 12, i= 0;             // or newInt.Length

            for (i = 0; i < newInt.Length; i++)
            {
                if (newInt[i] < 0 && newInt[size] > 0)
                {
                    int temp = newInt[i];
                    newInt[i] = newInt[size];
                    newInt[size] = temp;
                    size--;
                }
            }
            for (i = 0; i < newInt.Length; i++)
            {
                Console.Write(newInt[i]);
                Console.Write(" ");
            }
        }
    }
}

但输出是这样的(-20 在错误的一边):

5 10 9 8 -20 6 7 -14 15 -16 -4 -1 -2

但预期的输出是:

5 10 9 8 15 6 7 -14 -20 -16 -4 -1 -2 

为什么我的代码没有产生我想要的输出?

4

5 回答 5

5

您的解决方案错误地决定何时完成循环。i此外,它在循环头中无条件地递增,size即使它指向负数也不会递减。

以下是您修复它的方法:

for (i = 0; i < size ; ) {
    if (newInt[i] < 0 && newInt[size] >= 0) {
        int temp = newInt[i];
        newInt[i] = newInt[size];
        newInt[size] = temp;
        size--;
        i++;
        continue;
    }
    if (newInt[i] >= 0) {
        i++;
    }
    if (newInt[size] < 0) {
        size--;
    }
}

这是关于 ideone 的演示

您可以为您的leftandright指针使用更具可读性的标识符来重写此循环,而不是使用iand size。这将使您的算法在代码中看起来更加“对称”,以识别其设计中的对称性:

int left = 0, right = newInt.Length-1;
while (left < right) {
    if (newInt[left] < 0 && newInt[right] >= 0) {
        int temp = newInt[left];
        newInt[left] = newInt[right];
        newInt[right] = temp;
        right--;
        left++;
        continue;
    }
    if (newInt[left] >= 0) {
        left++;
    }
    if (newInt[right] < 0) {
        right--;
    }
}

这是替代实现的 ideone 链接

于 2013-01-06T04:43:37.903 回答
3

试试这个解决方案:

var newInt = new[] {5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10};
var solution = newInt.GroupBy(i => i > 0).
    SelectMany(g => g).
    ToArray();

您的算法的问题是,当您减少时size,您最终会得到newInt[size]一个负值,并且if不会输入该块。

于 2013-01-06T04:38:16.010 回答
1

一个非常简单的解决方案的一般想法是启动一个索引,left在数组的开头调用它,然后在数组right的末尾调用另一个索引。

递增left直到找到负数,或直到left == right。当你遇到一个负数时,递减right直到你找到一个正数,或者直到right == left.

如果left正在索引一个负数并且right正在索引一个正数,则交换这两个项目并left再次开始递增。

总体思路,未经测试:

int left = 0;
int right = a.Length-1;
while (left < right)
{
    if (a[left] < 0)
    {
        while (right > left)
        {
            if (a[right] >= 0)
            {
                // swap here
                int temp = a[left];
                a[left] = a[right];
                a[right] = temp;
                break;
             }
             --right;
        }
    }
    ++left;
}
于 2013-01-06T05:12:57.603 回答
1

这会产生具有最少循环的所需顺序

int[] newInt = new int[] { 5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10 };
int lt = 0;
int rt = newInt.Length - 1;
while (true) {
    // Find first negative number
    while (newInt[lt] >= 0 && lt < rt) {
        lt++;
    }

    // Find last positive number
    while (newInt[rt] < 0 && rt > lt) {
        rt--;
    }

    if (lt == rt) {
        break; // Finished
    }

    // Swap
    int temp = newInt[lt];
    newInt[lt] = newInt[rt];
    newInt[rt] = temp;
}
//TODO: Print result
于 2013-01-06T05:18:48.837 回答
0

如果您可以使用泛型和 linq,那么最简单的解决方案是:

int[] newInt = new int[] { 5, -2, -1, -4, -20, 6, 7, -14, 15, -16, 8, 9, 10 };
newInt.ToList().Sort();
newInt.Reverse();
newInt = newInt.ToArray();

希望这会有所帮助!

于 2013-01-06T04:33:23.953 回答