归并排序

复习一波,发现都快忘光了QAQ… 利用二分的思想,不断分割排序区间。

void mergearray(int*a, int first, int mid, int last, int*temp)
{
    int i = first, j = mid+1, k = last,m=0;
    while (i <= mid&&j <= last) {
        if (a[i] < a[j])
            temp[++m] = a[i++];
        else
            temp[++m] = a[j++];
    }
    while (i <= mid)
        temp[++m] = a[i++];
    while (j <= last)
        temp[++m] = a[j++];
    for (i = 1; i <= m; i++)
        a[first+i-1] = temp[i];//这里要注意前面数组的下标
}
void mergesort(int*a, int first, int last, int*temp)
{
    if (first < last) {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);
        mergesort(a, mid + 1, last, temp);
        mergearray(a, first, mid, last, temp);
    }
}

归并排序课用于计算逆序对,因为如果是非逆序的数,那么在mergearray的时候前面的肯定比后面的小,如果出现一个比后面大的,那么这个数后面的所有前面的数都一定比后面的数大。

int cnt=0;
void mergearray(int*a, int first, int mid, int last, int*temp)
{
    int i = first, j = mid+1, k = last,m=0;
    while (i <= mid&&j <= last) {
        if (a[i] < a[j])
            temp[++m] = a[i++];
        else
            temp[++m] = a[j++],cnt+=mid-i+1;//其实只有这里不同
    }
    while (i <= mid)
        temp[++m] = a[i++];
    while (j <= last)
        temp[++m] = a[j++];
    for (i = 1; i <= m; i++)
        a[first+i-1] = temp[i];
}
void mergesort(int*a, int first, int last, int*temp)
{
    if (first < last) {
        int mid = (first + last) / 2;
        mergesort(a, first, mid, temp);
        mergesort(a, mid + 1, last, temp);
        mergearray(a, first, mid, last, temp);
    }
}