歸并排序遞歸法和非遞歸法的簡單簡單介紹

基本思想: 歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有 序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為二路歸并。

歸并排序核心步驟:先將數組分組,往下分直到分為1個數據,然后開始合并,兩兩合并,合并的時候先比較兩組數據中的數據的大小,按順序依次合并到臨時數組temp中,然后再將合并到temp數組中有序的數據覆蓋到原數組中。

#include <stdio.h>
// 歸并排序
// 時間復雜度O(N*logN)
// 空間復雜度O(N)
void _MergeSort(int* arr, int left, int right, int* temp)
{if (left >= right)return;// 遞歸劃分區間,直到區間內只有一個數據后開始歸并int mid = (left + right) / 2;// [left,mid] [mid+1,right]_MergeSort(arr, left, mid, temp);_MergeSort(arr, mid+1, right, temp);// 歸并[left,mid] [mid+1,right]有序,歸并到temp了int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])temp[index++] = arr[begin1++];elsetemp[index++] = arr[begin2++];}// 可能有一段沒結束,具體那一段不知道,只有一個循環可以進入while(begin1<=end1)temp[index++] = arr[begin1++];while (begin2 <= end2)temp[index++] = arr[begin2++];// 將歸并后在temp的數據拷貝回原數組for (int i = left;i <= right; i++){arr[i] = temp[i];}
}// 歸并排序
void MergeSort(int* arr, int n)
{assert(arr);int* temp = malloc(sizeof(int) * n);// 傳入閉區間【0,n-1】_MergeSort(arr, 0, n - 1, temp);free(temp);
}void TestMergeSort()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };MergeSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}void TestMergeSortNonR()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };MergeSortNonR(arr,sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}int main()
{//TestInsertSort();//TestShellSort();//TestSelectSort();//TestBubbleSort();//TestHeapSort();//TestQuickSort();TestMergeSort();TestMergeSortNonR();return 0;
}

函數的遞歸實現圖:

非遞歸法

從上面的遞歸圖可以看出,合并的時候是2個數據開始合并,也就是區間【0,0】和【1,1】合并,【2,2】和【3,3】合并;然后【0,1】和【2,3】合并到這里時是兩個數據兩個數據之間合并,依次類推。那么非遞歸方法,需要控制好合并的下標即可。

// 歸并排序--非遞歸方法
void MergeArry(int* arr, int begin1, int end1, int begin2, int end2, int* temp)
{int left = begin1, right = end2;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2])temp[index++] = arr[begin1++];elsetemp[index++] = arr[begin2++];}// 可能有一段沒結束,具體那一段不知道while (begin1 <= end1)temp[index++] = arr[begin1++];while (begin2 <= end2)temp[index++] = arr[begin2++];// 將歸并后在temp的數據拷貝回原數組for (int i = left;i <= right; i++){arr[i] = temp[i];}
}void MergeSortNonR(int* arr, int n)
{assert(arr);int* temp = malloc(sizeof(int) * n);int gap = 1;  // 控制幾個數據的合并排序while (gap < n){for (int i = 0;i < n;i += 2 * gap){// 歸并+排序的區間(數組長度不是2的次方數時第二組可能會越界訪問)// [i,i+gap-1] [i+gap,i+2*gap-1]int begin1 = i, end1 = i + gap - 1;    // 第一組int begin2 = i + gap, end2 = i + 2 * gap - 1;  // 第二組// 1、合并時只有第一組if (begin2 >= n)break;// 2、合并時第二組只有部分數據,需要修正邊界if (end2 >= n)end2 = n - 1; // 只有一個數值的時候,直接讓end2=最后一個數值就行了MergeArry(arr, begin1, end1, begin2, end2, temp);}Printarry(arr, n);gap *= 2;}free(temp);
}

實現圖:

結論:

歸并排序是一種基于分治思想的有效排序算法,其核心是通過遞歸將數組不斷二分直至單個元素,然后按順序合并有序子序列。算法分為遞歸和非遞歸兩種實現方式:遞歸法通過_MergeSort函數劃分區間并調用自身,然后將有序子序列合并到臨時數組后回寫;非遞歸法使用MergeSortNonR函數,通過gap變量控制合并步長,逐步擴大有序區間。兩種方法都使用MergeArry函數進行具體合并操作,時間復雜度均為O(N*logN),空間復雜度為O(N)。代碼示例展示了完整的實現過程,包括邊界處理和數據拷貝等關鍵步驟。

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

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

相關文章

webrtc之子帶分割下——SplittingFilter源碼分析

文章目錄前言一、頻帶分割過程1.SplittingFilter的創建2.頻帶分割整體流程1&#xff09;分割時機2&#xff09;分割規則3&#xff09;分割核心代碼3.頻帶合并二、算法實現1.實現原理介紹2.All pass QMF系統源碼1&#xff09;提高精度2&#xff09;經過串聯全通濾波器3&#xff…

Java運維之Tomcat升級

Tomcat升級準備工作 下述所有過程中,包含了兩種升級方式,一種是備份舊版本的 bin 和 lib,將新版本的 bin 和 lib 對舊版本進行覆蓋;另一種是直接備份舊版本的Tomcat包,運行新版本,將舊版本的配置文件(conf/ * )和應用(webapps/ * )等同步到新版本。 1. 到官網下載指…

MySQL的可重復讀隔離級別實現原理分析

MySQL 的 可重復讀&#xff08;Repeatable Read, RR&#xff09; 隔離級別主要通過 多版本并發控制&#xff08;Multi-Version Concurrency Control, MVCC&#xff09; 和 鎖機制&#xff08;特別是間隙鎖&#xff09; 來實現的。其核心目標是&#xff1a;在一個事務內&#xf…

利用Java自定義格式,循環導出數據、圖片到excel

利用Java自定義格式&#xff0c;循環導出數據、圖片到excel1、自定義格式循環導出數據1.1.設置格式1.1.1、居中樣式1.1.2、應用樣式到合并區域1.1.3、合并單元格1.1.4、設置列寬1.2、寫入數據1.2.1、創建標簽頭部1.2.2、寫入標簽內容2、自定義格式循環導出圖片2.1、設置格式并插…

SAP學習筆記 - 開發45 - RAP開發 Managed App New Service Definition,Metadata Extension

上一章講了在 Data Model View ( CDS View for BO Structure )基礎上創建 Projection View ( CDS View for BO Projection )。 SAP學習筆記 - 開發44 - RAP開發 Managed App 建 Projection View&#xff0c;Provider Contract&#xff0c;用 redirected to 設定父子關系-CSDN博…

React強大且靈活hooks庫——ahooks入門實踐之高級類hook(advanced)詳解

什么是 ahooks&#xff1f; ahooks 是一個 React Hooks 庫&#xff0c;提供了大量實用的自定義 hooks&#xff0c;幫助開發者更高效地構建 React 應用。其中高級類 hooks 是 ahooks 的一個重要分類&#xff0c;專門用于處理一些高級場景&#xff0c;如受控值、事件發射器、性能…

計算機網絡——數據鏈路層(25王道最新版)

數據鏈路層前言數據鏈路層的功能封裝成幀&#xff08;組幀&#xff09;字符計數法字節填充法零比特填充法違規編碼法小節差錯控制檢錯編碼奇偶校驗碼CRC校驗碼&#xff08;循環冗余校驗碼&#xff09;基本思想如何構造如何檢錯糾錯糾錯編碼海明校驗碼設計思路求解步驟&#xff…

【PTA數據結構 | C語言版】字符串替換算法

本專欄持續輸出數據結構題目集&#xff0c;歡迎訂閱。 文章目錄題目代碼題目 請編寫程序&#xff0c;將給定主串 s 中的子串 sub_s 替換成另一個給定字符串 t&#xff0c;再輸出替換后的主串 s。 輸入格式&#xff1a; 輸入給出 3 個非空字符串&#xff0c;依次為&#xff1a…

事物生效,訂單類內部更新訂單

代碼如下以下代碼1不生效&#xff0c;2生效解決方案1&#xff0c;外層方法加注解&#xff0c;內層不加2&#xff0c;不要拆分方法&#xff0c;把更新訂單操作放在帶事物的大方法中3&#xff0c;拆方法&#xff08;內部&#xff09;&#xff0c;注入自己&#xff0c;用代理對象調…

非對稱加密:RSA

文章目錄 非對稱加密:RSA 1、RSA 加解密 2、RSA 生成密鑰對(公鑰、私鑰)、加解密 參考資料 非對稱加密:RSA 1、RSA 加解密 <!-- RSA --><!-- 引入jsencrypt庫 --><script src="https://cdn.bootcdn.net/ajax/libs/jsencrypt/3.3.2/jsencrypt.min.js&q…

MongoDB 數據庫 啟用訪問控制

0. 最近服務器安裝了 MongoDB 被勒索了 測試服務器安裝了 MongoDB 等&#xff0c;開放了 27017 對所有 ip。 哈哈哈哈哈哈&#xff0c;問就是有點犯懶&#xff0c;之前都是只允許自己的 ip。 好家伙&#xff0c;然后沒過幾個小時&#xff0c;數據庫集合被清空&#xff0c;只留…

【Unity Sprite屬性拓展】

Unity Inspector 精靈圖預覽為 Unity 中的 Sprite 類型屬性提供了??增強版的 Inspector 顯示??&#xff0c;在保留標準精靈選擇功能的基礎上&#xff0c;添加了大型預覽圖和精靈名稱顯示功能代碼 using UnityEngine; using UnityEditor;// 1?? 告訴 Unity&#xff1a;所有…

細菌實驗入門:濃度測定與菌種鑒定技術詳解

在微生物實驗中&#xff0c;細菌濃度的精準測定和菌種的準確鑒定是兩項基礎且核心的操作。本文將詳細介紹相關技術的原理、操作步驟及注意事項&#xff0c;為新手提供系統性指導。一、細菌濃度測定方法1. 光密度法&#xff08;OD600&#xff09;&#xff1a;快速定量的首選原理…

GaussDB 數據庫架構師修煉(一)數據庫容量規劃

1、容量規劃的定義GaussDB容量規劃是指根據客戶業務系統的負載需求或歷史運行數據&#xff0c;進行合理規劃GaussDB的計算、存儲和網絡資源配置&#xff0c;以滿足業務系統正常使用和未來若干年負載增長訴求的過程。2、容量規劃活動主要步驟需求收集調研生產系統的業務特征&…

hashMap原理(一)

概念HashMap是java中一種非常常用的基于哈希表的數據結構&#xff0c;允許o(1)的時間復雜度進行元素插入&#xff0c;查找&#xff0c;和刪除。它通過”鍵-值“ 對的方式存儲數據。總的來說&#xff1a;HashMap的底層原理&#xff1a;數組鏈表紅黑樹&#xff08;jdk1.8之后還涉…

Ubuntu24 輔助系統-屏幕鍵盤的back按鍵在網頁文本框刪除不正常的問題解決方法

Ubuntu24 輔助系統-屏幕鍵盤的back按鍵異常 問題描述ubuntu24這個屏幕鍵盤&#xff0c;只有在網頁的搜索框或者文本框&#xff0c;比如百度首頁的搜索框&#xff0c;留言的文本框&#xff0c;才會出現點擊back按鈕的時候&#xff0c;出現了先選中當前這個字符&#xff0c;刪除此…

自然語言指令驅動的工業機器人協同學習系統:大語言模型如何重塑智能體協作范式

重磅推薦專欄: 《大模型AIGC》 《課程大綱》 《知識星球》 本專欄致力于探索和討論當今最前沿的技術趨勢和應用領域,包括但不限于ChatGPT和Stable Diffusion等。我們將深入研究大型模型的開發和應用,以及與之相關的人工智能生成內容(AIGC)技術。通過深入的技術解析和實踐經…

web:js的switch語句

在js中,switch語句是一種用于根據不同的條件執行不同代碼塊的控制流語句。它類似于多個if...else if...else語句,但結構更清晰,特別是在有多個條件分支的情況下。 基本語法 switch (expression) {case value1:// 當expression的值等于value1時執行這里的代碼break;case va…

為何說分布式 AI 推理已成為下一代計算方式

2024 年&#xff0c;我們見證了人工智能創新的空前爆發。AI 的快速發展令很多人驚嘆&#xff0c;為了訓練更先進的大語言模型&#xff08;LLM&#xff09;&#xff0c;科技巨頭爭相獲取強大的 GPU。如今&#xff0c;AI 正在無縫融入我們世界的每個角落。在眾多新興 AI 公司、模…

阿里云 RabbitMQ 可觀測性最佳實踐

阿里云 RabbitMQ 阿里云 RabbitMQ 是一款高性能、高可靠的消息中間件&#xff0c;支持多種消息協議和豐富的功能特性。它提供消息隊列功能&#xff0c;能夠實現應用間的消息解耦和異步通信&#xff0c;提升系統擴展性和穩定性。其支持多種消息持久化策略&#xff0c;確保消息不…