目录
归并排序
归并排序（ MERGE-SORT ）是建立在归并操作上的一种有效的排序算法 ,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子 序列段间有序。若 将两个有序表合并成一个有序表 ，称为二路归并。 时间复杂度：O(N*logn)
⼤体过程分为两步：
- 分：将数组⼀分为⼆为两部分，⼀直分解到数组的⻓度为 1 ，使整个数组的排序过程被分为 「左半部分排序」 + 「右半部分排序」；
- 治：将两个较短的「有序数组合并成⼀个⻓的有序数组」，⼀直合并到最初的⻓度。
代码实现
class Solution {
int[] tmp;
public int[] sortArray(int[] nums) {
tmp = new int[nums.length];
mergeSort(nums,0,nums.length-1);
return nums;
}
public void mergeSort(int[] nums,int left,int right) {
if(left >= right) {
return;
}
//1.根据中间点拆分数据.左、右两部分
int mid = (left + right) / 2;
mergeSort(nums,left,mid);
mergeSort(nums,mid+1,right);
//2.合并两个有序数组
// int[] tmp = new int[right - left + 1];
int cur1 = left,cur2 = mid + 1,i = 0;
while(cur1 <= mid && cur2 <= right) {
tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
}
while(cur1 <= mid) {
tmp[i++] = nums[cur1++];
}
while(cur2 <= right) {
tmp[i++] = nums[cur2++];
}
// 3.还原到原数组
for(int j = left; j <= right; j++) {
nums[j] = tmp[j - left];
}
}
}交易逆序对的总数
题目描述
题解
因此，我们可以利⽤归并排序的过程，先求出左半数组中逆序对的数量，再求出右半数组中逆序对的 数量，最后求出⼀个选择左边，另⼀个选择右边情况下逆序对的数量，三者相加即可。 （利⽤数组的有序性，快速统计 出逆序对的数量，⽽不是将所有情况都枚举出来）最核心的问题，如何在合并两个有序数组的过程中，统计出逆序对的数量？
- 找出该数之前，有多少个数比它大
- 找出该数之后，有多少个数比它小.
代码实现
int[] tmp;
public int reversePairs(int[] nums) {
tmp = new int[nums.length];
return mergerSort(nums,0,nums.length - 1);
}
public int mergerSort(int[] nums,int left,int right) {
//1.递归出口
if(left >= right) {
return 0;
}
// 2.分成左右两部分
int ret = 0;
int mid = (left + right) >> 1;
ret += mergerSort(nums,left,mid);
ret += mergerSort(nums,mid + 1,right);
//3.合并
// int[] tmp = new int[right - left + 1];
int cur1 = left, cur2 = mid + 1, i = 0;//数组下标
while(cur1 <= mid && cur2 <= right) {
if(nums[cur1] <= nums[cur2]) {
tmp[i++] = nums[cur1++];
}else {
//计数
ret += mid - cur1 + 1;
tmp[i++] = nums[cur2++];
}
}
while(cur1 <= mid) {
tmp[i++] = nums[cur1++];
}
while(cur2 <= right) {
tmp[i++] = nums[cur2++];
}
// 还原数组
for(int j = left; j <= right; j++) {
nums[j] = tmp[j - left];
}
return ret;
}计算右侧小于当前元素的个数
题目描述
题解
解法：归并排序.
代码实现
int[] ret; // 结果数组
int[] index; // 存放原始数据的下标
int[] tmpNums; // 辅助数组
int[] tmpIndex;
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
ret = new int[n];
index = new int[n];
tmpIndex = new int[n];
tmpNums = new int[n];
// 初始化原始数据的下标
for (int i = 0; i < n; i++) {
index[i] = i;
}
// 归并排序
mergerSort(nums, 0, n - 1);
//
List<Integer> list = new ArrayList<>();
for (int x : ret) {
list.add(x);
}
return list;
}
public void mergerSort(int[] nums, int left, int right) {
// 1.递归出口
if (left >= right) {
return ;
}
// 2.拆分成左右两部分
int mid = (left + right) >> 1;
mergerSort(nums, left, mid);
mergerSort(nums, mid + 1, right);
// 合并
int cur1 = left, cur2 = mid + 1, i = 0;
while (cur1 <= mid && cur2 <= right) {
// 降序排 => 谁大动谁
if (nums[cur1] <= nums[cur2]) {
tmpNums[i] = nums[cur2];
// 绑定移动
tmpIndex[i++] = index[cur2++];
} else {
ret[index[cur1]] += right - cur2 + 1;
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
}
while (cur1 <= mid) {
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
while (cur2 <= right) {
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
for(int j = left; j <= right; j++) {
nums[j] = tmpNums[j - left];
index[j] = tmpIndex[j - left];
}
}翻转对
题目描述
题解
翻转对和逆序对的定义⼤同⼩异，逆序对是前⾯的数要⼤于后⾯的数。⽽翻转对是前⾯的⼀个数要 ⼤于 后⾯某个数的两倍 。因此，我们依旧可以⽤归并排序的思想来解决这个问题。但是，归并排序，要求的是左边元素大于右边元素；而这道题的条件是，左边元素大于右边元素的两倍，所以， 我们需要在归并之前完成翻转对的统计。
代码实现
int[] tmp;
public int reversePairs(int[] nums) {
int n = nums.length;
tmp = new int[n];
return mergerSort(nums,0,n - 1);
}
public int mergerSort(int[] nums,int left,int right) {
//1.递归结束条件
if(left >= right) {
return 0;
}
//2.拆分数组分为左右两部分
int ret = 0;
int mid = (left + right) >> 1;
ret += mergerSort(nums,left,mid);
ret += mergerSort(nums,mid + 1,right);
//3.计算翻转对(降序)
int cur1 = left,cur2 = mid + 1,i = 0;
while(cur1 <= mid) {
// while(cur2 <= right && nums[cur2] < nums[cur1] / 2.0 ) {
// ret += right - cur2 + 1;
// cur1++;
// }
// if(cur2 > right) {
// break;
// }
// cur2++;
while(cur2 <= right && nums[cur2] >= nums[cur1] / 2.0) {
cur2++;
}
if(cur2 > right) {
break;
}
ret += right - cur2 + 1;
cur1++;
}
//4.合并两个有序数组
cur1 = left;
cur2 = mid + 1;
while(cur1 <= mid && cur2 <= right) {
if(nums[cur1] <= nums[cur2]) {
tmp[i++] = nums[cur2++];
}else{
tmp[i++] = nums[cur1++];
}
}
while(cur1 <= mid) {
tmp[i++] = nums[cur1++];
}
while(cur2 <= right) {
tmp[i++] = nums[cur2++];
}
for(int j = left; j <= right; j++) {
nums[j] = tmp[j - left];
}
return ret;
}
