C中的反转计数归并排序

Question

从 1 到 n 的整数排列是一个序列 a1, a2, ..., an，使得从 1 到 n 的每个整数在序列中恰好出现一次。

一个排列中的两个整数形成一个反转，当较大的在较小的之前。

例如，在排列4 2 7 1 5 6 3中，总共有10次反转。它们是以下对：4–2、4–1、4–3、2–1、7–1、7–5、7–6、7–3、5–3、6–3。

输入n和数组[n] 2<=n<=100,000

首先我解决了冒泡排序的问题，但后来我遇到了时间复杂度问题。

其次我解决了mergesort但是我做的不好

这是我的数据线

#include <stdio.h>
#include <malloc.h>
int n;

void sizein(){
    scanf("%d",&n);
}

int count=0;
static void merge(int data[],int p,int q,int r){
    int i,j,l;
    int k=p;
    int sorted[n];
    for(i=p,j=q+1;i<=q&&j<=r;){
        sorted[k++]=(data[i]<=data[j]) ? data[i++]:data[j++];
        if(data[i>data[j]]){
            count+=q-i;
        }
    }
    if(i>q){
        for(l=j;l<=r;l++,k++){
            sorted[k]=data[l];
        }
    }
    else{
        for(l=i;l<=q;l++,k++){
            sorted[k]=data[l];
        }
    }
    for(l=p;l<=r;l++){
        data[l]=sorted[l];
    }
}

void merge_sort(int data[],int p,int r){
    if(p<r){
        int q=(p+r)/2;
        merge_sort(data,p,q);
        merge_sort(data,q+1,r);
        merge(data,p,q,r);
    }
}

int main(void){
    int i;
    int data[n];
    for(i=0;i<n;i++){
        scanf("%d",&data[i]);
    }
    merge_sort(data,0,n);
    printf("%d",count);
    return 0;
}

我应该在哪里修复它

Answer 1

我在你的代码中找不到一些根据索引将数组分成子数组的实现位（因为快速排序是根据值排序的）请查看下面提供的代码

int q = p + (r - l) / 2;//recommended to be used in the function mergesort

int q=(p+r)/2;//your implementation

尝试将此代码用于您的函数部分，因为我的代码运行良好，具有超过 50 万个值，我无法清楚地看到在您的函数实现中将值复制到的任何子数组 merge 我已添加评论为了让您更容易理解，变量的术语略有不同。

参考《ANANY LEVETIN-INTRODUCTION TO THE DESIGN AND ANALYSIS OF ALGORITHS》一书对该算法有生动的解释

看看并试试这个

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
 
    /* create temp arrays */
    int L[n1], R[n2];
 
    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
 
    /* Merge the temp arrays back into arr[l..r]*/
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    /* Copy the remaining elements of L[], if there
    are any */
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    /* Copy the remaining elements of R[], if there
    are any */
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

/* l is for left index and r is right index of the
sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r) {
        // Same as (l+r)/2, but avoids overflow for
        // large l and h
        int m = l + (r - l) / 2;
 
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
 
        merge(arr, l, m, r);
    }
}
 

/* Driver code */
int main()
{
    int arr[] = { 12, 11, 13, 5, 6, 7 };
    int arr_size = sizeof(arr) / sizeof(arr[0]);
 
    printf("Given array is \n");
    //printArray(arr, arr_size);
 
    mergeSort(arr, 0, arr_size - 1);
 
    printf("\nSorted array is \n");
    //printArray(arr, arr_size);
    return 0;
}

Answer 2

读了一段时间的代码后，我仍然不能说我理解倒数计数的想法。但是，我可以指出其中三处我认为不正确的地方。

首先，我看不到你在哪里调用 sizein() 函数来初始化 n 变量。

第二个问题是这里的条件：

    if(data[i>data[j]]){
        count+=q-i;
    }

您将 索引 i 与 数据项 data[j] 的值进行比较，这看起来很奇怪。更糟糕的是，如果要对一组几何图形或一组歌曲进行排序，由于要比较的数据类型不兼容，这可能是不可能的。更糟糕的是，即使比较成功，如 int 索引和 data[] 中的 int 值的情况，比较的结果是 int 值 1 if比较满足，否则为 0。因此，此条件将解析为

    if(data[0]){
        count+=q-i;
    }

或到

    if(data[1]){
        count+=q-i;
    }

这显然是错误的。

正确的代码如下所示：

    if (data[i] > data[j]) {
        count += q - i;
    }

如果您在运算符及其操作数之间留有适当的间距，错误会更加明显。

另一个错误潜伏在对 merge_sort() 的调用中。首先，用这个循环填充 data[] 数组：

for (i = 0; i < n; i ++) {
    scanf("%d", &data[i]);
}

显然，您用 0 到 n-1.

索引处的数据填充 n-items 数组

然后调用合并排序例程：

merge_sort( data, 0, n);

表明参数p是第一项或要排序的部分的索引，q是最后一项的过去。但是，这与递归调用不一致：

    merge_sort( data, p, q);
    merge_sort( data, q+1, r);

在第一次调用中将 q 设置为结束索引，在第二次调用中将 q+1 设置为起始索引表明结束索引包含，即即，它是要排序的段中最后一项的位置。否则这两个调用将使项目 data[q] 未排序。这也遵循内部循环，在 i <= q 或 l <= r 等

时继续

所以最初的调用不应该是

merge_sort( data, 0, n);

而是

merge_sort( data, 0, n-1);

C中的反转计数归并排序

inversion count mergesort in C

c

sorting

mergesort