go|由递归排序引申出的小和问题和逆序数对问题算法|数据结构

递归排序的思想是将带牌列数组不断的拆成俩部分，再将有序的左右的俩部分合并。
小和问题：在一个数组中，每一个数左边比当前小的数累加起来，叫做这个数组的小和。求一个数组的小和。
逆序对问题，在一个数组中，打印出数组所有左边数大于右边数的组合。
下面是归并排序的代码（go语言）

// 写一个归并排序 func mergeSort(arr *[]int, l, r int) { // 这部分是拆 if l == r { return } mid := l + ((r - l) >> 1) mergeSort(arr, l, mid) mergeSort(arr, mid+1, r) merge(arr, l, mid, r) }func merge(arr *[]int, l, mid, r int) { p, q := l, mid+1 help := make([]int, r-l+1) i := 0 for p <= mid && q <= r { if (*arr)[p] <= (*arr)[q] { help[i] = (*arr)[p] p = p + 1 i = i + 1 } else { help[i] = (*arr)[q] q = q + 1 i = i + 1 } } for p <= mid { help[i] = (*arr)[p] p = p + 1 i = i + 1 } for q <= r { help[i] = (*arr)[q] q = q + 1 i = i + 1 } for i := 0; i < len(help); i++ { (*arr)[l+i] = help[i] }}

下面是解决小和问题和逆序数对问题的代码：

func smallSum(arr []int, l, r int) int { if len(arr) == 0 || l == r { return 0 } mid := l + ((r - l) >> 1) return smallSum(arr, l, mid) + smallSum(arr, mid+1, r) + merge2(arr, l, mid, r) }func merge2(arr []int, l, mid, r int) int { p, q := l, mid+1 i := 0 result := 0 help := make([]int, r-l+1) for p <= mid && q <= r { if arr[p] < arr[q] { result = result + arr[p]*(r-q+1) help[i] = arr[p] p = p + 1 i = i + 1 } else { help[i] = arr[q] q = q + 1 i = i + 1 } } for p <= mid { help[i] = arr[p] p = p + 1 i = i + 1 } for q <= r { help[i] = arr[q] i = i + 1 q = q + 1 } p, q = l, mid+1 for p <= mid { for arr[p] > arr[q] { fmt.Println(arr[p], arr[q]) if q < r { q = q + 1 } else { break } } p = p + 1 q = mid + 1 } for i := 0; i < len(help); i++ { arr[l+i] = help[i] } return result }

【go|由递归排序引申出的小和问题和逆序数对问题】