前言

本文為本小白🤯學習數據結構的筆記，將以算法題為導向，向大家更清晰的介紹數據結構相關知識（算法題都出自🙌B站馬士兵教育——左老師的課程，講的很好，對于想入門刷題的人很有幫助👍）

上面講了歸并排序，這個思想非常好??（用了遞歸來降低時間復雜度），這里我想再寫寫歸并排序的實質，以及用這個思想來解決一些問題。

??首先來看看歸并排序是怎么實現排序的

package DiGui;public class hhhguibing {public static void process(int[] arr,int L,int R){if (L==R) {return;}int mid=L + ((R-L)>>1);process(arr,L,mid);process(arr,mid+1,R);merge(arr,L,mid,R);}public static void merge(int[] arr,int L,int mid,int R){int[] help=new int[R-L+1];int i=0,p1=L,p2=mid+1;while(p1<=mid&&p2<=R){help[i++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];}while(p1<=mid){help[i++]=arr[p1++];}while(p2<=R){help[i++]=arr[p2++];}for (i=0; i < help.length; i++) {arr[L+i]=help[i];}}
}

1.🧩先來解析一下代碼結構

public static void process(int[] arr, int L, int R)

這是遞歸函數，負責“分”的過程。

• L 和 R 表示當前處理的區間 [L, R]。

  • 遞歸處理左半部分：process(arr, L, mid)
  • 遞歸處理右半部分：process(arr, mid+1, R)

最后調用 merge(arr, L, mid, R) 把左右兩部分合并成有序的

public static void merge(int[] arr, int L, int mid, int R)

• 合并兩個有序數組

  • 因為有前面的遞歸過程，到merge時， [L, mid] 是有序的，[mid+1, R] 也是有序的
  • 創建一個輔助數組 help，用來暫存合并后的結果
  • 用兩個指針 p1 和 p2 分別指向左右兩個有序區的開頭
  • 比較 arr[p1] 和 arr[p2]，把較小的放進 help，對應指針后移
  • 一方遍歷完后，把另一方剩下的元素全部復制過去
    最后把 help 中排好序的內容寫回原數組 arr[L…R]

💡三、舉個例子說明過程

假設數組是：[4, 1, 3, 2]

初始：[4, 1, 3, 2]↓ 分[4, 1]     [3, 2]↓           ↓[4] [1]     [3] [2]   ← 到底了，開始合并↓           ↓[1,4]       [2,3]   ← 合并兩個有序對↓ 合并[1,2,3,4]         ← 排序完成

🤔那為什么歸并排序比普通的排序時間復雜度更低呢？

🌟 核心思想：避免重復的無效比較

一、來看看傳統排序（O(n2)）的“時間浪費”在哪？
插入排序為例子：

數組: [5, 4, 3, 2, 1]插入 4：要和 5 比較一次，移動 5
插入 3：要和 4、5 比較，移動 4、5
插入 2：要和 3、4、5 比較，移動 3、4、5
插入 1：要和 2、3、4、5 比較，移動全部

👉 每個新元素都要從后往前逐個比較，平均要比較 O(n) 次，總共 n 個元素 → 總時間 O(n2)

• 插入排序…等：每一步只“推進”一個元素的位置，過程中做了大量重復且低效的比較和移動。
• 歸并排序：通過 分治 + 合并有序數組 的方式，讓每一次比較都“更有價值”。

🌏歸并排序擴展問題：

1.小和問題：
在一個數組中，每一個數左邊比當前數小的數累加起來，叫做這個數組的小和。求一個數組的小和。
例子：[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

為了更直觀的來看，用遞歸方法解小和問題更高效，我先寫（O(n2)）的暴力解法：

public static int smallSum (int[] arr) {int sum = 0;for (int i = 1; i < arr.length; i++) {for (int j = 0;j < i;j++) {if (arr[j] < arr[i]) {sum += arr[j];}}}return sum;
}        

🚀 高效解法：利用 歸并排序 → O(n log n)

先解釋一下 ：

這個是把小和問題先轉化了一下，將原問題（每一個數左邊比當前數小的數累加起來），轉化為每個數右邊有幾個比它大，就說明這個數本身，被累加了幾次。
例子：[1,3.4.2.5]1右邊比1大的數，有4個：3右邊比3大的數，有2個；4右邊比4大的數，有1個; 2右邊比2大的數，有1個；5右邊比5大的數，沒有；所以小和為1 * 4+3 * 2+4 * 1+2 * 1+5 * 0=16；

那么我們只需要統計每個數右邊有幾個比它大，就可以了

public static void process(int [] arr,int L,int R) {if (L ==R ) {return 0;}int mid = L + ((R-L)>>1);return process(arr , L,mid) + process(arr , mid+1, R) + merge(arr,L,mid,R);
}public static int merge(int[] arr,int L,int mid,int R){int help=new int [R-L+1];int i=0,p1=L,p2=mid+1;int res=0;//記錄小和數while(p1<=mid&&p2<=R){res+=arr[p1] <arr[p2] ? (r-p2+1) * arr[p1] : 0;help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while(p1<=mid) {help[i++] = arr[p1++];}while(p2<=r) {help[i++] = arr[p2++];}for( i=0;i<help.length;i++) {arr[L +i] = help[i];}return res;
}

逆序對問題：
逆序對問題在一個數組中，左邊的數如果比右邊的數大，則這兩個數構成一個逆序對，請打印所有逆序對數。

這道題一樣的，剛才小和問題是求每個數右邊有幾個比它大，這個是求每個數右邊有幾個比它小

public static void process(int [] arr,int L,int R) {if (L ==R ) {return 0;}int mid = L + ((R-L)>>1);return process(arr , L,mid) + process(arr , mid+1, R) + merge(arr,L,mid,R);
}public static int merge(int[] arr,int L,int mid,int R){int help=new int [R-L+1];int i=0,p1=L,p2=mid+1;int res=0;//記錄小和數while(p1<=mid&&p2<=R){res+=arr[p1] > arr[p2] ? (r-p2+1) * arr[p1] : 0;help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];}while(p1<=mid) {help[i++] = arr[p1++];}while(p2<=r) {help[i++] = arr[p2++];}for( i=0;i<help.length;i++) {arr[L +i] = help[i];}return res;
}

小白啊！！！寫的不好輕噴啊🤯如果覺得寫的不好，點個贊吧🤪（批評是我寫作的動力）

…。。。。。。。。。。。…

…。。。。。。。。。。。…