算法系列--分治排序|歸并排序|逆序對的求解

一.基本概念與實現

歸并排序(mergeSort)也是基于分治思想的一種排序方式,思路如下:

分解:根據中間下標mid將數組分解為兩部分
解決:不斷執行上述分解過程,當分解到只有一個元素時,停止分解,此時就是有序的
合并:合并兩個有序的子區間,所有子區間合并的結果就是原問題的解

歸并排序和快速排序的區別在于排序的時機不同,歸并排序是等到分解完畢之后在進行排序,快速排序是先進行分解,再排序;更形象的說,歸并排序更像二叉樹的后序遍歷,遍歷完左右子樹再打印根節點;快速排序反之
在這里插入圖片描述

代碼:

class Solution {int[] tmp;public int[] sortArray(int[] nums) {tmp = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return nums;}private void mergeSort(int[] nums, int start, int end) {if(start >= end) return;// 遞歸出口int mid = (start + end) >> 1;// 分解左右子樹mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);// 合并兩個有序序列merge(nums, start, mid, end);}private void merge(int[] nums, int l, int mid, int r) {// 合并兩個有序列表int i = 0, i1 = l, i2 = mid + 1;while(i1 <= mid && i2 <= r)tmp[i++] = nums[i1] < nums[i2] ? nums[i1++] : nums[i2++];while(i1 <= mid) tmp[i++] = nums[i1++];while(i2 <= r) tmp[i++] = nums[i2++];// 重新賦值for(int j = l; j <= r; j++) nums[j] = tmp[j - l];}
}

將tmp設置為全局減少每次合并兩個有序列表都要new所消耗的時間

2.利用歸并排序求解逆序對

逆序對
鏈接:https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/
在這里插入圖片描述
分析

最容易想到的思路就是暴力解法,每遍歷到一個數字就統計后面有多少個小于當前數字的數字,只要小于就滿足逆序對的條件,時間復雜度為O(N^2),顯而易見這種做法的時間復雜度過高,無法通過所有樣例
可以這么想,每遍歷到一個數字,我就想"如果我知道我前面有多少個比我大的數字該多好",就不需要再去一個一個遍歷了,或者是每遍歷到一個數字,“如果我知道后面有多少個比我小的數字該多好”
但是實際上不容易解決,不容易統計,比如9,7,8這樣的一個序列,你無法通過記錄最值的方式統計有多少個大的數字,這是行不通的,好像唯一的解法就是從開頭一直遍歷到當前數字?可這就是暴力解法啊,如果能對前面的區間進行排序,得到大于當前數字的所有數字中的最小值,就能根據下標快速得到有多少個比我大的數字.那難道每遍歷到一個數字就對前面的區間排一下序再找最小值嗎?時間復雜度好像更高了,且不穩定
但是這個想法是好的,在遍歷的過程中如果前面的元素是有序的,那么就能降低時間復雜度,關于逆序對的求解,排序是一個很好的思路
排序一般都是從小到大排序,無論哪種排序方式,對于一個亂序的數組,如果想讓他變成有序的,就必須要進行元素的移動,就會將較小的數字放到較大的數字之前,可見排序就是消除逆序對的過程,以下是幾種基于排序的求解逆序對的方法

01.冒泡排序

對于冒泡排序,每次元素交換就可以看做一次消除逆序對;使用全局變量ret記錄元素交換的次數
冒泡排序的本質是"每次移動,都通過元素比較和元素交換讓當前區間的最大值移動到區間末尾"

代碼:

class Solution {// 冒泡排序法int ret;public int reversePairs(int[] nums) {bubbleSort(nums);return ret;}private void bubbleSort(int[] nums) {int n = nums.length;for (int i = 0; i < n; i++) {boolean flg = false;for (int j = 0; j < n - 1 - i; j++) {if (nums[j] > nums[j + 1]) {swap(nums, j, j + 1);flg = true;}}if (!flg)return;}}private void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;++ret;}
}

時間復雜度:O(N^2)

02.插入排序

對于插入排序,每次元素的移動都可以看做一次消除逆序對,使用一個全局變量ret記錄元素移動的次數即可,時間比冒泡排序略快
插入排序就像是往你的已有的有序的撲克牌中插入一個新牌,每次都是從后往前進行比較,進行插入

代碼:

class Solution {// 插入排序法int ret;public int reversePairs(int[] nums) {for(int i = 1; i < nums.length; i++) {int tmp = nums[i], j = i - 1;while(j >= 0) {if(nums[j] > tmp) {nums[j + 1] = nums[j];++ret;}else break;--j;}nums[j + 1] = tmp;}return ret;}
}

時間復雜度:O(N^2)

03.歸并排序(最快的解法)

代碼:

class Solution {int[] tmp;// 用于合并兩個有序數組的臨時數組int ret;// 記錄遞歸過程中的逆序對的個數public int reversePairs(int[] nums) {tmp = new int[nums.length];mergeSort(nums, 0, nums.length - 1);// 歸并排序return ret;}private void mergeSort(int[] nums, int start, int end) {if(start >= end) return;int mid = (start + end) >> 1;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);merge(nums, start, mid, end);}private void merge(int[] nums, int l, int mid, int r) {// 在合并的過程中統計逆序對的個數// 關鍵步驟  合并兩個有序數組// 在合并的過程中統計逆序對的個數！！！// 此處采用 的邏輯是：固定cur2，找cur1中比當前cur2大的數// 在排序的過程中應該使用升序排序int i = 0, i1 = l, i2 = mid + 1;while(i1 <= mid && i2 <= r) {if(nums[i1] > nums[i2]) {// 如果大  則i1后面的數字都比當前數字大  都能構成逆序對ret += mid - i1 + 1;tmp[i++] = nums[i2++];}else {tmp[i++] = nums[i1++];}}while(i1 <= mid) tmp[i++] = nums[i1++];while(i2 <= r) tmp[i++] = nums[i2++];for(int j = l; j <= r; j++) nums[j] = tmp[j - l];}
}

時間復雜度:O(N*logN)

圖解:
在這里插入圖片描述

3.計算右側小于當前數的個數

鏈接:https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/
分析

是上一題逆序對的拓展版本
利用上面快速求解逆序對的思想,能夠快速得到小于當前數字的數字的個數,需要注意的是,在歸并排序的過程中原數組的元素會發生移動,但是只有歸并完整個數組才能得到最終的結果,這個過程中我們要將數組元素和數組下標進行綁定,可以考慮使用index數組
當元素發生移動時,下標也跟著移動;

代碼:

class Solution {int[] tmpNum;int[] tmpIndex;int[] index;int[] cnt;public List<Integer> countSmaller(int[] nums) {int n = nums.length;tmpNum = new int[n];tmpIndex = new int[n];index = new int[n];cnt = new int[n];for(int i = 0; i < n; i++) index[i] = i;// 綁定索引mergeSort(nums, 0, n - 1);List<Integer> ret = new ArrayList<>();for(int x : cnt) ret.add(x);return ret;}private void mergeSort(int[] nums, int start, int end) {if(start >= end) return;int mid = (start + end) >> 1;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);merge(nums, start, mid, end);}private void merge(int[] nums, int l, int mid, int r) {// 合并兩個有序列表(降序排序)// 可以快速得到有多少個數字小于當前數字int i = 0, i1 = l, i2 = mid + 1;while(i1 <= mid && i2 <= r) {if(nums[i1] > nums[i2]) {cnt[index[i1]] += r - i2 + 1;tmpIndex[i] = index[i1];tmpNum[i++] = nums[i1++];}else  {tmpIndex[i] = index[i2];tmpNum[i++] = nums[i2++];}}// 處理未解決的元素while(i1 <= mid) {tmpIndex[i] = index[i1];tmpNum[i++] = nums[i1++];}while(i2 <= r) {tmpIndex[i] = index[i2];tmpNum[i++] = nums[i2++];}// 重新賦值  原數組和下標數組都要更改for(int j = l; j <= r; j++) {nums[j] = tmpNum[j - l];index[j] = tmpIndex[j - l];}}
}

4.反轉對的個數

鏈接:

代碼:

class Solution {int[] tmp;int ret;public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];mergeSort(nums, 0, n - 1);return ret;}private void mergeSort(int[] nums, int start, int end) {if(start >= end) return;int mid = (start + end) >> 1;mergeSort(nums, start, mid);mergeSort(nums, mid + 1, end);merge(nums, start, mid, end);}private void merge(int[] nums, int l, int mid, int r) {// 先統計當前有多少個翻轉對int i = 0, i1 = l, i2 = mid + 1;while(i1 <= mid) {while(i2 <= r && nums[i2] >= nums[i1] / 2.0) i2++;// 注意此處的除法需要存在小數位if(i2 > r) break;ret += r - i2 + 1;i1++;}i1 = l; i2 = mid + 1;while(i1 <= mid && i2 <= r) {if(nums[i1] > nums[i2]) tmp[i++] = nums[i1++];else tmp[i++] = nums[i2++];}while(i1 <= mid) tmp[i++] = nums[i1++];while(i2 <= r) tmp[i++] = nums[i2++];for(int j = l; j <= r; j++) nums[j] = tmp[j - l];}
}