【算法練習】歸并排序和歸并分治

文章目錄

    • 1.歸并排序
      • 1.1 遞歸版本
      • 1.2 非遞歸版本
    • 2.歸并分治
      • 2.1 計算數組的小和
      • 2.2 計算翻轉對

1.歸并排序

歸并排序的核心步驟是:

拆分:將無序數組不斷對半拆分成小塊,直到每個小塊只剩一個元素(自然有序)。
合并:將相鄰的有序小塊合并,逐步形成更大的有序塊,直到整個數組有序。

1.1 遞歸版本

遞歸天然避免越界,代碼簡潔,但遞歸深度受限。

#include <vector>
using namespace std;// 合并兩個有序子數組
void merge(int arr[], int left, int mid, int right) 
{vector<int> temp(right - left + 1);  // 臨時數組int i = left, j = mid + 1, k = 0;// 雙指針合并有序區間while (i <= mid && j <= right) {temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];}// 處理剩余元素while (i <= mid) temp[k++] = arr[i++];while (j <= right) temp[k++] = arr[j++];// 拷貝回原數組for (int p = 0; p < k; p++) {arr[left + p] = temp[p];}
}// 遞歸歸并排序
void mergeSort(int arr[], int left, int right) {if (left >= right) return;int mid = left + (right - left) / 2;mergeSort(arr, left, mid);//分解左半區mergeSort(arr, mid + 1, right);//分解右半區merge(arr, left, mid, right);//合并有序區間
}int main() 
{int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr)/sizeof(arr[0]);mergeSort(arr, 0, n-1);return 0;
}

1.2 非遞歸版本

非遞歸版本通過步長控制,把數組看作由多個有序子數組組成,逐步擴大子數組長度,直到整個數組有序。
非遞歸循環效率更高,適合大數據量,但是需要控制越界。

與遞歸版本不同的是遞歸是自頂向下(通過遞歸函數先拆分再合并),非遞歸是自底向上(通過數組下標直接從小塊開始合并)

假設原始數組為 [3,1,4,2,7,5]
執行步驟如下:
步長=1:把每個元素視為獨立的有序數組,兩兩合并→ 合并后 [1,3] [2,4] [5,7]
步長=2:合并相鄰的兩個長度為2的子數組→ 合并后 [1,2,3,4] [5,7]
步長=4:繼續合并更大的子數組→ 最終得到 [1,2,3,4,5,7]
?

void mergeSort(int arr[], int n) 
{// 預分配臨時空間vector<int> temp(n);  // 按步長分組(1,2,4,8...)for (int gap = 1; gap < n; gap *= 2) {// 每兩組進行比較 //[left, left+gap-1] [left+gap,left+2*gap-1]//[left,mid][mid+1, right]for (int left = 0; left < n; left += 2*gap) {// 計算子數組邊界 (按l,m,r)int mid = min(left + gap - 1, n-1);int right = min(left + 2*gap - 1, n-1);// 合并相鄰子數組int i = left, j = mid + 1, k = left;while (i <= mid && j <= right) {temp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];}// 處理剩余元素while (i <= mid) temp[k++] = arr[i++];while (j <= right) temp[k++] = arr[j++];// 拷貝回原數組for (int p = left; p <= right; p++) {arr[p] = temp[p];}}}
}int main() 
{int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr)/sizeof(arr[0]);mergeSort(arr, n);return 0;
}

2.歸并分治

實施原理:

  1. 思考問題在大范圍的答案,是否等于左部分的答案+右部分的答案+跨越左右部分的答案。
  2. 計算跨越左右部分的答案時,如果左右部分各自有序,是否能讓計算跨越左右部分答案時更加便利。

分治法的基本步驟:

  1. 分解:將原始數組通過遞歸的方式拆分成兩個長度相近的子數組,一直拆分到單個元素為止(因為單個元素天生有序)
  2. 統計:根據題意進行相關的統計。
  3. 排序:根據題意思考,在將小部分合并成大部分之前,如果將小部分進行排序,是否能便于大部分進行統計。

?

2.1 計算數組的小和

計算數組的小和

首先讓我們看一組示例 [1,3,5,2,4,6],這個小和答案為27,其暴力解法很好想,就是每個數和其他的數進行比較進行累加,但時間復雜度是O(n^2)所以不考慮。
?
下面看看這題歸并分治的解法。

1. 根據上面說的原理,我們先看整個大范圍部分[1,3,5,2,4,6]的答案,是否可以通過左部分[1,3,5]加上右部分[2,4,6],再加上跨越左右的答案。
首先,我們直接計算[1,3,5]小和是5,[2,4,6]小和是8。接下來計算跨越左右的答案[1,3,5] | [2,4,6],可以看到兩邊內部的已經各種計算好了,那么跨越的先看2對應的2>1再2<3,那么對應2的小和就只有1。再看4對應的4>1,4>3,4<5那么4對應的小和就是4,6類推就是9,那么跨越的小和加起來就是14,再和前面相加14+5+8就是27答案對應上了。
2. 那么如果再把大范圍縮小到計算[1,3,5]的答案,可以看出,其左部分[1,3]小和為1,右部分[5]小和為0,跨越左右為4,相加后也對應上了小和為5。那么就可以看出小部分的解和大部分的解都是一樣的,那么就可以考慮歸并分治。
3.接下來考慮在計算跨越左右的答案時,如果左、右部分各自有序這個條件,計算會不會更簡單。
我們看[1,3,5] | [2,4,6],如果其未排序[3,1,5] [6,2,4],那么對于未排序的計算,需要每個數和其他數進行比較累加,就是暴力解法。肯定是更復雜的!。
4.那么這道題,保持左右各有序后計算便利在哪?
比如這個例子[3,6,7] [5,6,9]在計算跨越左右的答案時,有兩種算法。
(1)從右部分開始對左部分的數進行比對,對應5大于3,對應6>3,6>=6,對應9>3,9>6,9>7,我們可以發現,右部分下一個數的計算(如5之后的6,6之后的9)可以在上一個數的基礎上繼續計算并且加上上一個數的和。
??具體什么意思?就是比如右部分的5在和左部分3比較后再和左部分6比較,由于5<6那么左部分就到6停,下一個右部分的6直接和左部分的6進行比較,再和7比較然后停。右部分6的小和就直接加上5的小和和比較的6。右部分的9就直接加上6的小和以及比較的7。(這樣就不用右部分每一個數都和左邊的比了,因為有序)
(2)從左部分開始對右部分的數進行比對,如果5大于3,那么5后面所有的數都大于3,就直接3乘以5以及右邊的個數就行了。

兩個方法時間復雜度都是O(N),相當于把每個數都走了一遍。
?
對應從右部分開始對左部分的數進行比對

//代表整個跨左右的答案
long long ans = 0; 
//先固定右部分的數,sum代表每個數自己的小和
for(int j = m+1, i = l, sum = 0; j <= r; ++j)
{//每個數的小和 = 這一回的比較 + 上一個數的小和while(i <= m && s[i] <= s[j]) sum+=s[i++];ans += sum;
}

對應從左部分開始對右部分的數進行比對

//代表整個跨左右的答案
long long ans = 0; 
for(int j = m+1, i = l; j <= r; ++j)
{while(i <= m && s[i] <= s[j]){ans+=(r-j+1)*s[i];++i;}
}

完整代碼

#include <iostream>using namespace std;const int MAXN = 100001;int s[MAXN];
int tmp[MAXN];long long Merge(int l, int m, int r)
{//1.先統計long long ans = 0;for(int j = m+1, i = l, sum = 0; j <= r; ++j){while(i <= m && s[i] <= s[j]) sum+=s[i++];ans += sum;}/*//計算方法二long long ans = 0; for(int j = m+1, i = l; j <= r; ++j){while(i <= m && s[i] <= s[j]){ans+=(r-j+1)*s[i++];}}*///2.再排序,方便后續部分的統計int i = l, k = l, j = m+1;while(i <= m && j <= r){tmp[k++] = (s[i] <= s[j] ? s[i++] : s[j++]);}while(i <= m) tmp[k++] = s[i++];while(j <= r) tmp[k++] = s[j++];for (int i = l; i <= r; ++i){s[i] = tmp[i];}return ans;
}long long Count(int l, int r)
{if(l == r) return 0;int m = (l+r) >> 1;//接下來進行細分,同時統計計算再排序return Count(l, m) + Count(m+1, r) + Merge(l, m, r);
}int main() {int n = 0;while(cin >> n){for(int i = 0; i < n; ++i) cin>>s[i];//首先對數組進行細分cout << Count(0, n-1) << endl;}return 0;
}

?

2.2 計算翻轉對

計算翻轉對

還是照著之前說的原理,拿[2,4,3,5,1],分成兩個部分[2,4,3] [5,1],在假設兩個部分分別計算好翻轉對數量以及排序后,[2,4,3] 有0個翻轉對,[5,1]是1個,統計完后因為各個內部翻轉對已經計算好了,然后想排序后對于兩邊跨越的計算是否更便利,答案是肯定的,各自排序后。那么計算跨越左右的[2,3,4][1,5],也是有兩種方法,簡單的法一:3大于1*2了,那么排序后3之后都是大于3的,也就是都能和1能組成翻轉對的。法二:3和1比完后,接著4和5比,然后再加上3對應的翻轉對數。因為3滿足的,4也滿足。

class Solution {
public:int tmp[50001] = {0};int Merge(vector<int>& nums, int l, int m, int r){//1.統計int ans = 0;//法一// for(int i = l, j = m+1, count = 0; i <= m; ++i)// {//     while(j <= r && nums[i] > (long)2*nums[j]) count++, ++j;//     ans += count;// }//法二for(int i = l, j = m+1; i <= m; ++i){while(j <= r && nums[i] > (long)2*nums[j]){ans += (m-i+1);j++;}}//2.排序int a = l, b = l, c = m+1;while(a <= m && c <= r){tmp[b++] = (nums[a] <= nums[c] ? nums[a++] : nums[c++]);} while(a <= m) tmp[b++] = nums[a++];while(c <= r) tmp[b++] = nums[c++];for(int i = l; i <= r; ++i) nums[i] = tmp[i];return ans;}int Count(vector<int>& nums, int l, int r){if(l == r) return 0;int m = (l+r) >> 1;return Count(nums, l, m) + Count(nums, m+1, r) + Merge(nums, l, m, r);}int reversePairs(vector<int>& nums) {int len = nums.size();return Count(nums, 0, len-1);}
};

?
算法中有很多精妙又美麗的思想傳統,請務必堅持下去!!

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/903452.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/903452.shtml
英文地址,請注明出處:http://en.pswp.cn/news/903452.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

域對齊是什么

域對齊&#xff08;Domain Alignment&#xff09;是在機器學習和計算機視覺等領域中常用的技術 定義 域對齊旨在將不同域&#xff08;Domain&#xff09;的數據映射到一個共同的特征空間中&#xff0c;使得來自不同域的數據在該空間中具有相似的分布。這里的“域”可以指代不…

【linux】git安裝、升級

git安裝、升級 一、快捷安裝版本2.18.0二、自定義版本安裝&#xff08;安裝、升級&#xff09;1、移除舊文件2、安裝所需依賴3、選擇指定版本4、解壓文件、編譯5、增加環境變量&#xff0c;驗證是否版本 三、升級 一、快捷安裝版本2.18.0 yum install git git --version二、自…

編程日志4.24

棧的鏈表基礎表示結構 #include<iostream> #include<stdexcept> using namespace std; //模板聲明&#xff0c;表明Stack類是一個通用的模板&#xff0c;可以用于存儲任何類型的元素T template<typename T> //棧的聲明 //Stack類的聲明&#xff0c;表示一…

《冰雪傳奇點卡版》:探索冰雪世界的傳奇旅程!

《冰雪傳奇點卡版》以“純凈打金”為核心&#xff0c;摒棄復雜付費坑&#xff0c;回歸經典傳奇玩法。以下從核心玩法、資源獲取、職業搭配、交易變現四維度展開&#xff0c;助你高效開啟冰雪傳奇之旅。 一、核玩法解析&#xff1a;如何高效獲取資源&#xff1f; 1. 職業定位與…

DeepClaude開源程序可以實現代碼生成、創作詩句以及內容創作等功能

一、軟件介紹 文末提供程序和源碼下載 DeepClaude開源程序是增強的 AI&#xff0c;可以實現代碼生成&#xff1a;DeepSeek r1 Claude 3.7 十四行詩 - 無與倫比的性能&#xff01;內容創作&#xff1a;DeepSeek r1 Gemini 2.5 Pro - 卓越的質量&#xff01;OpenAI 兼容。流媒…

Java常用注解通俗解釋

注解就像是給Java代碼貼的"便利貼"&#xff0c;它們不會改變代碼本身的邏輯&#xff0c;但能給編譯器、開發工具或運行時環境提供額外信息。下面我用最通俗的方式解釋Java中最常用的注解&#xff1a; 一、基礎篇&#xff1a;人人必知的注解 1. Override - "我…

vscode chrome調試怎么在所有瀏覽器都好使

chrome調試時只能在打開的瀏覽器里進行調試&#xff0c;其它打開的chrome瀏覽器就不能調試了&#xff0c;怎么解決。 右鍵點擊 Chrome 的快捷方式圖標&#xff0c;選擇屬性 在目標一欄&#xff0c;最后加上--remote-debugging-port9222 注意要用空格隔開 lanch.json 文件配置 …

Unity PBR基礎知識

PBR原理 基于物理的渲染&#xff08;Physically Based Rendering&#xff0c;PBR&#xff09;是指使用基于物理原理和微平面理論建模的著色/光照模型&#xff0c;以及使用從現實中測量的表面參數來準確表示真實世界材質的渲染理念。 PBR基礎理念 微平面理論&#xff08;Micr…

COM組件使用方法

普通COM組件&#xff08;如DLL&#xff09;僅暴露方法/屬性接口&#xff0c;而ActiveX控件&#xff08;如OCX&#xff09;需要可視化交互&#xff08;如按鈕、表格&#xff09;&#xff0c;需通過 ??AxInterop?? 包裝器實現宿主環境集成。 項目中引入ActiveX控件流程如下。…

在 Spring Boot 項目中如何使用索引來優化 SQL 查詢?

在 Spring Boot 項目中使用索引來優化 SQL 查詢是提升數據庫性能最常用的方法之一。下面是詳細的步驟和實踐指南&#xff1a; 核心目標&#xff1a;讓數據庫能夠通過掃描索引&#xff08;小范圍、有序的數據結構&#xff09;快速定位到所需數據行&#xff0c;而不是掃描整個表…

Vue3生產環境與Vue Devtools

在 Vue 3 的生產環境中&#xff0c;默認情況下 Vue Devtools 是無法正常使用 的&#xff0c;但開發者可以通過配置強制啟用。以下是關鍵信息總結&#xff1a; &#x1f4cc; 核心結論 默認不可用 Vue 3 生產構建會移除 Devtools 支持以優化性能和安全性。 可強制啟用 通過構建…

ARP滲透學習1

ARP協議工作原理 1. 什么是ARP ARP定義: 地址解析協議&#xff08;Address Resolution Protocol&#xff09;&#xff0c;是根據IP地址獲取物理地址的一個TCP/IP協議。 2. 工作原理 ARP表: 每臺計算機都需要一個ARP表&#xff0c;用來保存IP地址和MAC地址的映射關系。查詢過…

甲骨文云2025深度解析:AI驅動的云原生生態與全球化突圍

一、戰略轉型&#xff1a;從數據庫巨頭到AI云服務先鋒 1. 技術重心向AI與云深度遷移 甲骨文在2025年加速向AI原生云架構轉型&#xff0c;其核心戰略圍繞生成式AI與量子計算展開。通過推出Oracle 23ai自治數據庫&#xff0c;深度集成AI向量搜索功能&#xff0c;并重構云基礎設…

【網絡原理】TCP異常處理(二):連接異常

目錄 一. 由進程崩潰引起的連接斷開 二. 由關機引起的連接斷開 三. 由斷電引起的連接斷開 四. 由網線斷開引起的連接斷開 一. 由進程崩潰引起的連接斷開 在一般情況下&#xff0c;進程無論是正常結束&#xff0c;還是異常崩潰&#xff0c;都會觸發回收文件資源&#xff0c;…

想做博聞強記的自己

2025年4月29日&#xff0c;13~25℃&#xff0c;還好 待辦&#xff1a; 冶金《物理》期末測試 閱卷&#xff08;冶金《物理》期末測試試卷&#xff09; 重修《物理》《物理2》電子材料歸檔 規則變更&#xff0c;《高等數學2》期末試卷推倒重來 遇見&#xff1a;直播畫面。 感受…

IP屬地是實時位置還是自己設置

刷微博、抖音時&#xff0c;評論區總能看到“IP屬地”&#xff1f;這個突然冒出來的小標簽&#xff0c;讓不少網友摸不著頭腦&#xff1a;?IP屬地是實時位置&#xff0c;還是可以自己設置&#xff1f;?別急&#xff0c;今天咱們就來聊聊這個話題&#xff01; 1、什么是IP屬地…

水力壓裂多裂縫擴展誘發光纖應變演化試驗研究

1.概述 本文基于OFDR技術的光纖應變監測方法&#xff0c;監測了真三軸條件下人造巖石試樣與頁巖的水力壓裂試驗。結果表明&#xff0c;OFDR技術能以毫米級分辨率實時監測裂縫起裂、擴展及閉合全過程&#xff0c;并建立基于應變演化的裂縫判別準則&#xff0c;為光纖壓裂監測的…

4、RabbitMQ的七種工作模式介紹

目錄 一、Simple(簡單模式) 1.1 概念 1.2 代碼實現 消費者 運行結果 二、Work Queue&#xff08;工作隊列&#xff09; 2.1 概念 1.2 代碼實現 生產者 消費者 運行結果 三、Publish/Subscribe&#xff08;發布/訂閱模式&#xff09; 3.1 概念 3.2 代碼實現 生產者…

厚銅PCB鉆孔工藝全解析:從參數設置到孔壁質量的關鍵控制點

在現代電子設備中&#xff0c;厚銅PCB&#xff08;印刷電路板&#xff09;扮演著至關重要的角色。它們不僅為電子元件提供了支撐&#xff0c;還實現了電路之間的連接。然而&#xff0c;在生產厚銅PCB時&#xff0c;鉆孔是一個關鍵環節。本文將為您介紹厚銅PCB生產中鉆孔的科普知…

缺口拼圖,非線性坐標關聯

繼上一篇文章&#xff0c; 歡迎一起交流探討 https://t.zsxq.com/GEIze