数据结构笔记--归并排序及其拓展题（小和问题、逆序对问题）

目录

1--归并排序

2--小和问题

3--逆序对问题

---

1--归并排序

        归并排序的核心思想：将一个无序的序列归并排序为一个有序的系列；通过递归将无序的序列二分，从底层开始将二分的序列归并排序为有序序列；

#include <iostream>
#include <vector>class Solution{
public:std::vector<int> Merge_Sort(std::vector<int> arr){if(arr.size() <= 1) return arr;split(arr, 0, arr.size() - 1);return arr;}// 二分void split(std::vector<int> &arr, int l, int r){if(l == r) return;int mid = l + (r - l) / 2;split(arr, l, mid);split(arr, mid+1, r);// 归并merge(arr, l, mid, mid+1, r);}void merge(std::vector<int> &arr, int l1, int r1, int l2, int r2){std::vector<int> res;int i = l1, j = l2;while(i <= r1 && j <= r2){if (arr[i] < arr[j]){res.push_back(arr[i]);i++;}else{res.push_back(arr[j]);j++;}}while(i <= r1){res.push_back(arr[i]);i++;}while(j <= r2){res.push_back(arr[j]);j++;}for(int i = 0, j = l1; j <= r2; i++, j++){arr[j] = res[i];}}
};int main(){std::vector<int> input = {1, 3, 4, 2, 5};Solution S1;std::vector<int> res = S1.Merge_Sort(input);for(int num : res) std::cout << num << " ";return 0;
}

2--小和问题

        在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和，请编码实现求解一个数组的小和；

        实例，给定数组 [1, 3, 4, 2, 5]，1 左边比 1 小的数，没有；3 左边比 3 小的数， 为 1；4 左边比 4 小的数， 为 1 和 3；2 左边比 2 小的数，为 1；5 左边比 5 小的数，为 1, 3, 4 和 2；因此数组的小数和为：1 + (1+3) + (1) + (1+3+4+2) = 16；

主要思路：

        在归并排序两两比较两个数组的元素时，就确定对应的小数和；具体做法是，分析当前数是另一个数组中多少个数的小数，即当前数多少次被用于计算小数和；

#include <iostream>
#include <vector>class Solution{
public:int Merge_Sort(std::vector<int> arr){if(arr.size() <= 1) return 0;int sum = split(arr, 0, arr.size() - 1);return sum;}// 二分int split(std::vector<int> &arr, int l, int r){if(l == r) return 0;int mid = l + (r - l) / 2;int count1 = split(arr, l, mid);int count2 = split(arr, mid+1, r);int count3 = merge(arr, l, mid, mid+1, r);// 归并return count1 + count2 + count3;}int merge(std::vector<int> &arr, int l1, int r1, int l2, int r2){int sum = 0;std::vector<int> res;int i = l1, j = l2;while(i <= r1 && j <= r2){if (arr[i] < arr[j]){// 对于 arr[j, r2] 的数都会大于 arr[i],因此它们的小数和都包含arr[i]sum += (r2 - j + 1) * arr[i];res.push_back(arr[i]);i++;}else{res.push_back(arr[j]);j++;}}while(i <= r1){res.push_back(arr[i]);i++;}while(j <= r2){res.push_back(arr[j]);j++;}for(int i = 0, j = l1; j <= r2; i++, j++){arr[j] = res[i];}return sum;}
};int main(){std::vector<int> input = {1, 3, 4, 2, 5};Solution S1;int res = S1.Merge_Sort(input);std::cout << res << " " << std::endl;return 0;
}

3--逆序对问题

主要思路：

        在归并排序两两比较两个数组的元素时，就确定对应的逆序对；具体做法是，分析当前数（arr2）在另一个数组(arr1)中有多少个逆序数；

#include <iostream>
#include <vector>class Solution{
public:int Merge_Sort(std::vector<int> arr){if(arr.size() <= 1) return 0;int sum = split(arr, 0, arr.size() - 1);return sum;}// 二分int split(std::vector<int> &arr, int l, int r){if(l == r) return 0;int mid = l + (r - l) / 2;int count1 = split(arr, l, mid);int count2 = split(arr, mid+1, r);int count3 = merge(arr, l, mid, mid+1, r);// 归并return count1 + count2 + count3;}int merge(std::vector<int> &arr, int l1, int r1, int l2, int r2){int sum = 0;std::vector<int> res;int i = l1, j = l2;while(i <= r1 && j <= r2){if (arr[i] > arr[j]){// 对于 arr[j, r2] 的数都会大于 arr[i],因此它们的小数和都包含arr[i]sum += (r1 - i + 1);res.push_back(arr[j]);j++;}else{res.push_back(arr[i]);i++;}}while(i <= r1){res.push_back(arr[i]);i++;}while(j <= r2){res.push_back(arr[j]);j++;}for(int i = 0, j = l1; j <= r2; i++, j++){arr[j] = res[i];}return sum;}
};int main(){std::vector<int> input = {7, 5, 6, 4};Solution S1;int res = S1.Merge_Sort(input);std::cout << res << " " << std::endl;return 0;
}