如何找到排序整数数组的最小步骤数

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;
        }

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;
        }

你的算法的问题是，它只尝试交换相邻的元素。

3,4,2,5,1的最佳排序方式是将3与5交换，这是一个非相邻交换，然后将2与3交换。

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

1)首先，使用c#内置的排序函数将数组按降序排序。

2)现在，您可以使用这个排序数组作为比较-从左到右遍历数组。每次在未排序数组中看到与已排序数组中相同空间的元素对应的元素!=时，请在未排序数组中更深入地查看已排序数组中的值，并执行一次交换。

。

3、4、2、5、1

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

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

Unsorted现在是5,4,2,3,1

4 == 4

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

Unsorted现在是5,4,3,2,1

2 == 2

1 == 1

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

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

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

你把它弄反了，你想

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

既然你在问为什么你得到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步)

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

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;
}

开头:

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

第一轮结果:

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

第二轮结果:

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

第三轮结果:

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

第4轮结果:

{ 5,4,3,2,1}; // same result and passes is incremented to be 4 

您没有提到数组应该按降序排序，这通常不是默认的预期行为(至少在"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中测试)。

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

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;
    }