2

基本上我正在尝试用Java编写一个算法来确定数组中乱序的对数。因此，如果我们取 i 和 j 并且 j 在数组中的位置比 i 高，但 A[i] > A[j] 则它将这两个数字计为反转。目前这就是我所拥有的：

for(int i = 0; i<n-1; i++){
    if (A[i] > A[i+1]){
        k++;

这样做只是比较彼此相邻的对，所以现在我正在尝试修改它以找到数组中较低位置的值高于较高位置的数字的任意两个数字。我知道如何做这样的事情，但我希望运行时间为 (n+k)，其中 n 是数组的长度，k 是数组中的反转数。

编辑：这是我实现插入排序的尝试：

int k = 0;
int [] A = {5, 4, 3, 2, 1};
int n = A.length;
for(int i = 1; i < n; i++){
    int temp = A[i];
    int j;
    for (j = i - 1; j >=0 && temp < A[j]; j--){
        A[j + 1] = A[j];
    A[j + 1] = A[j];
        k++;

k 应该跟踪多少反转。对于数组 5、4、3、2、1，我返回的数字是 6。对吗？

4

2 回答 2

2

解决方法是实现插入排序，计算一对相邻元素交换的次数。这是有效的，因为插入排序只对每个反转执行交换。事实上，正如您所要求的，它的运行时间是O ( n + k )。

至于问题第二部分 - 这是更正的插入排序算法：

for (int i = 1; i < n; i++) {
    int temp = A[i];
    int j;
    for (j = i - 1; j >= 0 && temp < A[j]; j--) {
        A[j + 1] = A[j];
        k++;  // Number of inversions
    }
    A[j + 1] = temp;
}

额外说明：计算数组反转的有效方法是修改合并排序算法，该算法在O ( n log n ) 时间内运行。然而，当k较小时，O ( n + k ) 大约为O ( n )，小于O ( n log n )。实际上，合并排序的最佳情况时间仍然是O ( n log n )，而插入排序的最佳情况是O ( n )。因此，归并排序不能回答 OP 的问题O ( n + k ) 算法。

于 2015-10-14T04:35:38.587 回答
0

数组的反转计数表示 - 数组距离排序多远（或接近）。如果数组已经排序，则反转计数为 0。如果数组以相反的顺序排序，则反转计数为最大值。形式上来说，如果 a[i] > a[j] 且 i < j，则两个元素 a[i] 和 a[j] 形成一个反演示例：序列 2、4、1、3、5 有三个反演（2、 1), (4, 1), (4, 3)。

对于每个元素，计算位于其右侧且小于它的元素的数量。

int getInvCount(int arr[], int n)
{
  int inv_count = 0;
  int i, j;

  for(i = 0; i < n - 1; i++)
    for(j = i+1; j < n; j++)
      if(arr[i] > arr[j])
        inv_count++;

  return inv_count;
}

/* Driver progra to test above functions */
int main(int argv, char** args)
{
  int arr[] = {1, 20, 6, 4, 5};
  printf(" Number of inversions are %d \n", getInvCount(arr, 5));
  getchar();
  return 0;
}
于 2015-10-14T04:31:45.193 回答