【重点!!!】【归并排序】剑指offer——面试题36：数组中的逆序对

力扣
本质是实现了归并排序（MergeSort）

solution1

思路链接

Python

# 版本1
class Solution:
    def reversePairs(self, record: List[int]) -> int:
        n = len(record)
        copy_array = record.copy()
        return self.merge_sort(record, 0, n - 1, copy_array)

    def merge_sort(self, record, start, end, copy_array):
        if start >= end:
            return 0
        res = 0
        mid = (end + start) // 2
        res = self.merge_sort(record, start, mid, copy_array) + self.merge_sort(record, mid + 1, end, copy_array)
        copy_array[start: end + 1] = record[start: end + 1] # copy_array临时保存原始序列
        l, r, k = start, mid + 1, start
        while l <= mid or r <= end:
            if l > mid:
                break
            if r > end or copy_array[l] <= copy_array[r]: # 注意: 需要使用原始数列对比!!!
                record[k] = copy_array[l]
                l += 1
            else: # copy_array[l] > copy_array[r]
                record[k] = copy_array[r]
                res += mid - l + 1
                r += 1
            k += 1

        return res

# 版本2
class Solution:
    def reversePairs(self, record: List[int]) -> int:
        n = len(record)
        copy_array = record.copy()
        return self.merge_sort(record, 0, n - 1, copy_array)

    def merge_sort(self, record, start, end, copy_array):
        if start >= end:
            return 0
        res = 0
        mid = (end + start) // 2
        res = self.merge_sort(record, start, mid, copy_array) + self.merge_sort(record, mid + 1, end, copy_array)
        copy_array[start: end + 1] = record[start: end + 1] # copy_array临时保存原始序列
        l, r, k = start, mid + 1, start
        while l <= mid and r <= end:
            if copy_array[l] <= copy_array[r]:
                record[k] = copy_array[l]
                l += 1
            else:
                record[k] = copy_array[r]
                res += mid - l + 1
                r += 1
            k += 1
            
        while l <= mid:
            record[k] = copy_array[l]
            l += 1 
            k += 1

        while r <= end:
            record[k] = copy_array[r]
            r += 1 
            k += 1

        return res

Java

// 版本1
class Solution {
    public int reversePairs(int[] record) {
        int[] copyArray = new int[record.length]; // 注意：这里要提前定义号备用数组!!!
        return mergeSort(record, 0, record.length - 1, copyArray);
    }

    public int mergeSort(int[] record, int start, int end, int[] copyArray) {
        if (start >= end) {
            return 0;
        }
        int mid = start + (end - start) / 2;
        int res = mergeSort(record, start, mid, copyArray) 
                + mergeSort(record, mid + 1, end, copyArray);
        for (int i = start; i <= end; ++i) {
            copyArray[i] = record[i];
        }
        int l = start, r = mid + 1, k = start;
        while (l <= mid || r <= end) { // 注意：这里是"或"！！！
            if (l > mid) {
                break;
            } else if (r > end || copyArray[l] <= copyArray[r]) {
                record[k++] = copyArray[l++];
            } else if (copyArray[l] > copyArray[r]) {
                record[k++] = copyArray[r++];
                res += mid - l + 1;
            }
        }

        return res;
    }
}

// 版本2
class Solution {
    int ans = 0;
    public int reversePairs(int[] record) {
        int n = record.length;
        if (n < 2) {
            return 0;
        }
        int[] tmp = new int[n];
        mergeSort(record, 0, n - 1, tmp);
        return ans;
    }

    public void mergeSort(int[] record, int start, int end, int[] tmp) {
        if (start < end) {
            int mid = start + (end - start) / 2;
            mergeSort(record, start, mid, tmp);
            mergeSort(record, mid + 1, end, tmp);
            merge(record, start, mid, end, tmp);
        }

    }

    // 升序merge
    public void merge(int[] record, int start, int mid, int end, int[] tmp) {
        for (int i = start; i <= end; ++i) {
            tmp[i] = record[i];
        }
        int l = start, r = mid + 1, k = start;
        while (l <= mid || r <= end) {
            if (l > mid) {
                break;
            } else if (r > end || tmp[l] <= tmp[r]) {
                record[k] = tmp[l];
                ++l;
            } else {
                ans += mid - l + 1;
                record[k] = tmp[r];
                ++r;
            }
            ++k;
        }
    }
}

// 版本3
class Solution {
    public int reversePairs(int[] record) {
        if (record.length <= 1) {
            return 0;
        }
        int[] tmpArray = new int[record.length]; // 注意：这里要提前定义号备用数组!!!

        return mergeSort(0, record.length - 1, record, tmpArray);
    }

    public int mergeSort(int start, int end, int[] record, int[] tmpArray) {
        if (start >= end) {
            return 0;
        }
        int mid = start + (end - start) / 2;
        int res = mergeSort(start, mid, record, tmpArray) + mergeSort(mid + 1, end, record, tmpArray);
        for (int i = start; i <= end; ++i) { // 暂存左、右子数组
            tmpArray[i] = record[i];
        }
        int lInx = start, rInx = mid + 1;
        for (int i = start; i <= end; ++i) { // 归并排序的合并过程要理解！！！
            if (lInx <= mid && rInx <= end) {
                if (tmpArray[lInx] <= tmpArray[rInx]) {
                    record[i] = tmpArray[lInx++];
                } else {
                    record[i] = tmpArray[rInx++];
                    res += mid - lInx + 1; // 记录逆序对
                }
            } else if (lInx > mid && rInx <= end) {
                record[i] = tmpArray[rInx++];
            } else if (lInx <= mid && rInx > end) {
                record[i] = tmpArray[lInx++];
            }
        }

        return res;
    }
}

##Solution1:
20180905整理
参考网址：https://www.nowcoder.com/profile/4474567/codeBookDetail?submissionId=23467046
需对常见的排序思想熟悉。。
20180906更：
这种方法有一个地方不是很好理解，就是在递归调用函数传入参数时。这种操作免去了主动复制的情况，还是solution2好理解一点。。。

class Solution {
public:
    int InversePairs(vector<int> data) {
        int length = data.size();
        if (length <= 0) return 0;
        vector<int> copy;
        //生成了一个副本
        for (int i = 0; i < length; i++)
            copy.push_back(data[i]);
        long long count = InversePairsCore(data, copy, 0, length - 1);
        return count % 1000000007;
    }
    long long InversePairsCore(vector<int> &data, vector<int> &copy, int start, int end) {
        if (start == end) {
            copy[start] = data[start];
            return 0;
        }
        int length = (end - start)/ 2;
        //注意在递归时，传入参数的次序不同！！！
        long long left = InversePairsCore(copy, data, start, start + length);
        long long right = InversePairsCore(copy, data, start + length + 1, end); 
        //i初始化为前半段最后一个数字的下标
        int i = start + length;
        //j初始化为后半段最后一个数字的下标
        int j = end;
        int indexcopy = end;
        long long count = 0;
        while (i >= start && j >= start + length + 1) {
            if (data[i] > data[j]) {
                copy[indexcopy--] = data[i--];
                //count = count + j - (start + length + 1) + 1;
                count = count + j - start - length; 
            } else
                copy[indexcopy--] = data[j--];
        }
        for(; i >= start; i--)
            copy[indexcopy--] = data[i];
        for(; j >= start + length + 1; j--)
            copy[indexcopy--] = data[j];
        return left + right + count;
    }
};

##Solution2:
比Solution1稍微好理解一点~~~

class Solution {
public:
    int InversePairs(vector<int> data) {
        int length = data.size();
        if (length <= 0) return 0;
        vector<int> copy;
        //生成了一个副本
        for (int i = 0; i < length; i++)
            copy.push_back(data[i]);
        long long count = InversePairsCore(data, copy, 0, length - 1);
        return count % 1000000007;
    }
    long long InversePairsCore(vector<int> &data, vector<int> &copy, int start, int end) {
        if (start == end) {
            copy[start] = data[start];
            return 0;
        }
        int mid = (start + end) >> 1;
        //增加了显示复制，递归时参数不用调换顺序~~
        long long left = InversePairsCore(data, copy, start, mid);
        long long right = InversePairsCore(data, copy, mid + 1, end); 
        //i初始化为前半段最后一个数字的下标
        int i = mid;
        //j初始化为后半段最后一个数字的下标
        int j = end;
        int indexcopy = end;
        long long count = 0;
        //此时data[]中的前后两段分别有序，那么利用copy[]做过程变量把两段有序数列归并排序
        //然后再把copy[]中归并排序后的值逐一赋值到（显示复制的作用）data[]相应位置
        //这样data[]和copy[]中[start, end]中均为有序数列
        while (i >= start && j >= mid + 1) {
            if (data[i] > data[j]) {
                copy[indexcopy--] = data[i--];
                //count = count + j - (start + length + 1) + 1;
                count = count + j - mid; 
            } else
                copy[indexcopy--] = data[j--];
        }
        for(; i >= start; i--)
            copy[indexcopy--] = data[i];
        for(; j >= mid + 1; j--)
            copy[indexcopy--] = data[j];
        //比solution1增加了显示复制的过程，在递归时不用调换顺序了~~~
        for (int i = start; i <= end; i++)
            data[i] = copy[i];
        return left + right + count;
    }
};