id]递增有序,因此a[i~mid]与a[j]构成逆序对,共mid-i+1个
{
temp[k++] = a[j++];
inversion += mid - i + 1;
}
}
while (i <= mid)
temp[k++] = a[i++];
while (j <= last)
temp[k++] = a[j++];
memcpy(a + first, temp, sizeof(int) * (last - first + 1));
return inversion;
}
int MergeInversionR(int a[], int first, int last, int temp[])
{
int inversion = 0;
if (first < last)
{
int mid = (first + last) >> 1;
inversion += MergeInversionR(a, first, mid, temp); //找左半段的逆序对数目
inversion += MergeInversionR(a, mid + 1, last, temp);//找右半段的逆序对数目
inversion += Merge(a, first, mid, last, temp); //在找完左右半段逆序对以后两段数组有序，然后找两段之间的逆序对。最小的逆序段只有一个元素。
}
return inversion;
}
int MergeInversion(int a[], int n)
{
int inversion = 0;
int *temp = new int[n];
memset(temp, 0, sizeof(int)*n);
inversion = MergeInversionR(a, 0, n - 1, temp);
delete []temp;
return inversion;
}
三、堆排序
见 利用堆实现堆排序&优先队列。
|