09 | 归并排序：如何解决逆序数问题？

逆序对问题 public int reversePairs(int[] nums) { if (nums == null || nums.length == 0) { return 0; } return reversePairs(nums, 0, nums.length - 1); } public int reversePairs(int[] arr, int l, int r) { if (l < r) { int mid = l + ((r - l) >> 1); return reversePairs(arr, l, mid) + reversePairs(arr, mid + 1, r) + reverseMarge(arr, l, mid, r); } return 0; } public int reverseMarge(int[] arr, int l, int m, int r) { int count = 0; int[] help = new int[r - l + 1]; int i = 0; int p1 = l; int p2 = m + 1; while (p1 <= m && p2 <= r) { count += arr[p1] > arr[p2] ? m - p1 + 1 : 0; help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++]; } for (; (p2 < r + 1) || (p1 < m + 1); p2++, p1++) { help[i++] = p1 > m ? arr[p2] : arr[p1]; } for (int j = 0; j < help.length; j++) { arr[l + j] = help[j]; } return count; }

因为我是学的go因此我就用go写的 受益匪浅 func InversionNumber(data []int)int{ l:=len(data) if l==2{ if data[0]>data[1]{ return 1 }else{ return 0 } }else if l==1{ return 0 } leftData:=data[:l/2] rightData:=data[l/2:] left:=InversionNumber(leftData) right:=InversionNumber(rightData) sort.Ints(leftData) sort.Ints(rightData) count:=0 i:=len(leftData)-1 j:=len(rightData)-1 for i>=0&&j>=0{ if leftData[i]>rightData[j]{ count+=j+1 i-- }else{ j-- } } return left+right+count }

归并排序有两个小问题： 1. l + r 可能会溢出：l + (r - l) >> 2 2. 每层merge重新分配空间，实践中会大大降低效率。建议先分配好整个数组所需空间作为auxiliary array

def inversion_number(nums): def across_numbers(nums, left, mid, right): l, r = left, mid + 1 temp = [] inversion = 0 while l <= mid or r <= right: if r > right or (l <= mid and nums[l] <= nums[r]): temp.append(nums[l]) l += 1 else: temp.append(nums[r]) r += 1 inversion += mid + 1 - l # 与左侧数组剩余元素分别产生一个逆序对 for i in range(right - left + 1): nums[left + i] = temp[i] return inversion def algorithm(nums, left, right): if left >= right: return 0 mid = (left + right) >> 1 left_numbers = algorithm(nums, left, mid) right_numbers = algorithm(nums, mid + 1, right) return left_numbers + right_numbers + across_numbers(nums, left, mid, right) return algorithm(nums, 0, len(nums) - 1)

图3中的是不是有问题，如果第一个数组中的元素大于第二个数组中同位置元素，这样merge的顺序就有问题了吧？ 总感觉略过了太多细节了，看的稀里糊涂。

java code public class test1 { public int inversion_number(int[] arr, int l, int r) { if (l == r) return 0; int mid = (l + r) >> 1; int a = inversion_number(arr, l, mid); int b = inversion_number(arr, mid + 1, r); int c = across_number(arr, l, mid, r); return a + b + c; } public int across_number(int[] arr, int l, int mid, int r) { int num = 0; int n = r - l + 1; int [] temp = new int[n]; int p1 = l, p2 = mid + 1, k = 0; while (p1 <= mid || p2 <= r) { if (p2 > r || (p1 <= mid && arr[p1] <= arr[p2])) { temp[k++] = arr[p1++]; } else { temp[k++] = arr[p2++]; int lsize = mid-p1+1; num = num + lsize; } } for (int i = 0, j = l; i < n; i++, j++) { arr[j] = temp[i]; } return num; } public static void main(String[] args) { test1 t = new test1(); int[] arr = new int[] {7,9,2,6,14,12}; int inversion_number = t.inversion_number(arr, 0, 5); System.out.println(inversion_number); } }

java来一发归并排序和逆序对的综合体 public class MergeSort { static int mergeSort(int[] arr, int l, int r) { if (l == r) return 0; int mid = (l + r) >> 1; int lNum = mergeSort(arr, l, mid); int rNum = mergeSort(arr, mid + 1, r); int acrossNum = merge(arr, l, mid, r); return lNum + rNum + acrossNum; } static int merge(int[] arr, int l, int mid, int r) { int[] mergedArr = new int[r - l + 1]; int i = l, j = mid + 1, k = 0, acrossInversionNumber = 0; while (i <= mid || j <= r) { if ((j > r) || (i <= mid && arr[i] < arr[j])) { // 此处注意 (j > r) 和 (i <= mid && arr[i] < arr[j]) 的位置不能调换，否则arr[j]会越界 mergedArr[k++] = arr[i++]; } else { mergedArr[k++] = arr[j++]; acrossInversionNumber += mid - i + 1; } } for (int t = 0; t < mergedArr.length; t++) { arr[t + l] = mergedArr[t]; } return acrossInversionNumber; } public static void main(String[] args) { int[] arr = {7, 9, 2, 6, 14, 12}; System.out.println("before merge sort: " + JSON.toJSONString(arr)); int inverseNumber = mergeSort(arr, 0, arr.length - 1); System.out.println("afger merge sort: " + JSON.toJSONString(arr)); System.out.println("inverseNumber: " + inverseNumber); } }

醍醐灌顶的感觉