4

我有一个整数数组 int[] number = { 3,4,2,5,1};

排序的最小步骤数应该是 2。但我得到了 4。

static void Main(string[] args)
        {
            int[] number = { 3,4,2,5,1};

           int result =  get_order(number);

            Console.ReadKey();
        }

        public static int get_order(int[] input1)
        {
            input1 = input1.OrderByDescending(o => o).ToArray();
            bool flag = true;
            int temp;
            int numLength = input1.Length;
            int passes = 0;

            for (int i = 1; (i <= (numLength - 1)) && flag; i++)
            {
                flag = false;
                for (int j = 0; j < (numLength - 1); j++)
                {
                    if (input1[j + 1] > input1[j])
                    {
                        temp = input1[j];
                        input1[j] = input1[j + 1];
                        input1[j + 1] = temp;
                        flag = true;
                    }
                }
                passes++;
            }
            return passes+1;
        }

有什么问题以及我需要在我的代码中做哪些更改？

编辑

实现@Patashu，算法，

public static int get_order(int[] input1)
        {
            var sorterArray = input1.OrderByDescending(o => o).ToArray();
            var unsortedArray = input1;
            int temp1;
            int swap = 0;

            int arrayLength = sorterArray.Length;
            for (int i = 0; i < arrayLength; i++)
            {
                if (sorterArray[i] != unsortedArray[i])
                {
                    temp1 = unsortedArray[i];
                    unsortedArray[i] = sorterArray[i];
                    for (int j = i + 1; j < arrayLength; j++)
                    {
                        if (unsortedArray[j] == sorterArray[i])
                        {
                            unsortedArray[j] = temp1;
                            swap++;
                            break;
                        }
                    } 
                }
            }

            return swap;
        }
4

6 回答 6

3

您的算法的问题在于它只尝试交换相邻元素。

3,4,2,5,1 最好通过将 3 与 5 交换（这是不相邻的交换）进行排序，然后将 2 与 3 交换。

因此，我建议您通过执行以下操作找到更好的算法：

1）首先，使用C#内置的排序功能对数组进行降序排序。

2) 现在，您可以使用这个排序后的数组作为比较 - 从左到右遍历数组。每次你在未排序数组中看到一个元素，它与排序数组中相同空间中的元素是 != 时，请更深入地查看未排序数组以获取排序数组在那里的值，然后进行一次交换。

例如

3,4,2,5,1

Sort using Sort -> 5,4,3,2,1 是我们的排序数组

3 是 != 5 - 在未排序的数组中查找 5 - 找到它，交换它们。

未排序现在是 5,4,2,3,1

4 == 4

2 是 != 3 - 在未排序的数组中查找 3 - 找到它，交换它们。

未排序现在是 5,4,3,2,1

2 == 2

1 == 1

我们在未排序数组的末尾，我们进行了两次交换。

编辑：在你的算法实现中，它看起来几乎是正确的，除了

代替

unsortedArray[j] = sorterArray[i];
unsortedArray[i] = temp1;

你有它倒退，你想要

unsortedArray[j] = temp1;
unsortedArray[i] = sorterArray[i];
于 2013-06-13T04:06:40.637 回答
2

由于您问的是为什么要执行 4 个步骤，而不是如何计算通行证，因此正确的方法是简单地单步执行您的代码。在您的情况下，代码很简单，可以在一张纸上、在调试器中或在添加调试语句时逐步完成。

Original: 3, 4, 2, 5, 1

Pass: 1: 4, 3, 5, 2, 1
Pass: 2: 4, 5, 3, 2, 1
Pass: 3: 5, 4, 3, 2, 1
Pass: 4: 5, 4, 3, 2, 1

基本上你看到的是每次迭代你都会将一个数字排序到正确的位置。在第一个 2 结束时处于正确的位置。然后是 3、4、5。

啊! 但这只是你说的3次通行证。但是您实际上是在递增passes，flag这表明您实际上做了一个额外的步骤，对数组进行排序（以相反的顺序）但您不知道这一点，因此您必须仔细检查（这是通过 4 ）。

于 2013-06-13T04:10:31.847 回答
1

为了提高性能，您不需要从头开始检查数组。比最后一个相等的元素更好。

static int MinimumSwaps(int[] arr)
{
    int result = 0;
    int temp;
    int counter = 0;
    for (int i = 0; i < arr.Length; ++i)
    {
        if (arr[i] - 1 == i)
        {
            //once all sorted then
            if(counter==arr.Length)break;
            counter++;
            continue;
        }
        temp = arr[arr[i]-1];
        arr[arr[i] - 1] = arr[i];
        arr[i] = temp;
        result++;//swapped
        i = counter ;//needs to start from the last equal element
    }
    return result;
}
于 2021-04-27T15:26:40.293 回答
0

在开始时：

{ 3,4,2,5,1}; // passes = 0

第一轮结果：

{ 4,3,2,5,1};
{ 4,3,5,2,1}; // passes = 1

第 2 轮结果：

{ 4,5,3,2,1}; // passes = 2

第三轮结果：

{ 5,4,3,2,1}; // passes = 3 and flag is set to true

第四轮结果：

{ 5,4,3,2,1}; // same result and passes is incremented to be 4
于 2013-06-13T04:09:37.113 回答
0

您没有提到数组应该按降序排序，这通常不是默认的预期行为（至少在“C”/C++ 中）。转：

3, 4, 2, 5, 1

进入：

1, 2, 3, 4, 5

一个确实需要 4 个（不相邻的）交换。然而，把它变成：

5, 4, 3, 2, 1

只有两次交换就足够了。以下算法找到O(m)交换操作的交换m次数，其中 是交换次数，它始终严格小于数组中的项目数，n（或者复杂度是O(m + n)循环迭代）：

int n = 5;
size_t P[] = {3, 4, 2, 5, 1};

for(int i = 0; i < n; ++ i)
    -- P[i];
// need zero-based indices (yours are 1-based)

for(int i = 0; i < n; ++ i)
    P[i] = 4 - P[i];
// reverse order?

size_t count = 0;
for(int i = 0; i < n; ++ i) {
    for(; P[i] != i; ++ count) // could be permuted multiple times
        std::swap(P[P[i]], P[i]); // look where the number at hand should be
}
// count number of permutations

这确实找到了两个交换。请注意，排列在此过程中被破坏。可以在此处找到此算法的测试用例（使用 Visual Studio 2008 测试）。

于 2014-04-07T14:16:58.927 回答
0

这是您问题的解决方案:)

static int MinimumSwaps(int[] arr)
    {
        int result = 0;
        int temp;
        int counter = 0;
        for (int i = 0; i < arr.Length; ++i)
        {
            if (arr[i] - 1 == i)
            {
                //once all sorted then
                if(counter==arr.Length)break;
                counter++;
                continue;
            }
            temp = arr[arr[i]-1];
            arr[arr[i] - 1] = arr[i];
            arr[i] = temp;
            result++;//swapped
            i = 0;//needs to start from the beginning after every swap
            counter = 0;//clearing the sorted array counter
        }
        return result;
    }
于 2019-11-17T12:49:43.443 回答