3

假设我有一个整数数组：

1 2 5 3 7 6

什么是一个足够简单的算法来确定这是排序方式（即1 2 3 5 6 7）数字的偶数还是奇数排列？性能在这里并不是很重要；我宁愿有一个简单的代码。

4

7 回答 7

5

Simple Code(Assume n numbers are stored in array a):

int f()
{
    int cnt=0;
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if (a[i]>a[j]) cnt++;
    return cnt%2;
}

If f() returns 0, then it is even permutation and returns 1, then it is odd.

于 2013-05-09T14:44:59.077 回答
1

另一个以 O(nlogn) 运行的简单代码，而 tr[] 是一个最初全为 0 的数组。

int ans=0;
for(int i=1;i<=n;i++)
{
    for(int j=a[i];j;j-=j&-j) ans+=tr[j];
    for(int j=a[i];j<=n;j+=j&-j) tr[j]++;
}
printf((n*(n-1)/2-ans)%2?"odd\n":"even");
于 2013-05-13T04:09:33.537 回答
1

根据维基百科，符号由反转的数量（元素对乱序）决定。这给出了一个 O(n**2) 算法

于 2013-05-09T14:39:18.077 回答
1

尝试实现您自己的堆排序算法版本，其复杂度为 O(n log n) 并计算排列次数以构建您的签名（我假设您知道我在说什么）。

示例代码：

public static void HeapSort(int[] input)
{
    //Build-Max-Heap
    int heapSize = input.Length;
    for (int p = (heapSize - 1) / 2; p >= 0; p--)
        MaxHeapify(input, heapSize, p);

    for (int i = input.Length - 1; i > 0; i--)
    {
        //Swap
        int temp = input[i];
        input[i] = input[0];
        input[0] = temp;

        heapSize--;
        MaxHeapify(input, heapSize, 0);
    }
}

private static void MaxHeapify(int[] input, int heapSize, int index)
{
    int left = (index + 1) * 2 - 1;
    int right = (index + 1) * 2;
    int largest = 0;

    if (left < heapSize && input[left] > input[index])
        largest = left;
    else
        largest = index;

    if (right < heapSize && input[right] > input[largest])
        largest = right;

    if (largest != index)
    {
        int temp = input[index];
        input[index] = input[largest];
        input[largest] = temp;

        MaxHeapify(input, heapSize, largest);
    }
}
于 2013-05-09T14:49:02.580 回答
1

当我不可避免地需要再次找到它时，简单且在 python 中完成：

def is_even(p):

    if len(p) == 1:
        return True

    trans = 0

    for i in range(0,len(p)):
        j = i + 1

        for j in range(j, len(p)):
            if p[i] > p[j]: 
                trans = trans + 1

    return ((trans % 2) == 0)
于 2018-05-25T19:37:26.173 回答
0

将排列分解为独立循环的乘积。奇数周期是奇数。偶数周期是偶数。加起来。

于 2013-05-09T14:37:24.053 回答
0

这个向量的置换矩阵行列式的符号应该会给你答案。

于 2013-05-09T14:34:37.287 回答