C中的反算合并
从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和arrayn 2<=n<=100,000
首先，我用气泡排序解决了问题，然后遇到了时间复杂性问题。
第二，我解决了合并问题，但我做得不好
这是我的脐带
#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;
}我该把它修到哪里？
回答 2
Stack Overflow用户
发布于 2021-04-02 15:27:07
我在您的代码中找不到一些实现位，可以根据索引将数组划分为子数组(作为基于值的快速排序)，请看下面提供的代码。
int q = p + (r - l) / 2;//recommended to be used in the function mergesortint q=(p+r)/2;//your implementation尝试函数部分的代码，因为我的代码运行良好，超过50万个值，我看不到在函数merge的实现中复制值的任何子数组--我添加了注释以使您更容易理解，变量的术语略有不同。
请参阅"ANANY LEVETIN-介绍算法的设计和分析“一书，以获得关于该算法的生动说明。
看看，试试这个
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;
}Stack Overflow用户
发布于 2021-04-02 20:09:09
在阅读了一段时间的代码后，我仍然不能说我理解倒置计数的想法。不过，我可以指出其中有三件事对我来说是不正确的。
首先，我看不出在哪里调用sizein()函数来初始化n变量。
第二个问题是这里的条件：
if(data[i>data[j]]){
count+=q-i;
}您可以将i索引与数据项 data[j]的值进行比较，这看起来很奇怪。更糟糕的是，如果你要对一组几何图形或一组歌曲进行排序，这可能是不可能的，因为要比较的数据类型不兼容。更糟糕的是，即使比较成功，如int索引和data[]中的int值，如果满足比较，则比较的结果是int值1，否则为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]);
}显然，您在n-items数组中填充了从0到n-1的索引中的数据。
然后调用合并排序例程：
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或whle l <= r等过程中继续进行。
所以最初的电话不应该是
merge_sort( data, 0, n);但更确切地说
merge_sort( data, 0, n-1);https://stackoverflow.com/questions/66921074
复制相似问题
腾讯云开发者
