力扣912題（排序數(shù)組）新手歸并排序教程

力扣912題（排序數(shù)組）新手教程題目要求：力扣912題要求對(duì)給定數(shù)組進(jìn)行排序，并返回排序后的結(jié)果。題目沒(méi)有限制使用哪種排序算法，因此可以選擇任意一種高效的方法（如快速排序、歸并排序等）。關(guān)鍵點(diǎn)在于理解排序算法的核心邏輯，尤其是分治思想和合并過(guò)程。-難點(diǎn)解析：分治思想：將大問(wèn)題分解為小問(wèn)題，遞歸解決后再合并。例如，將數(shù)組分為左右兩部分，分別排序后再合并。合并過(guò)程：如何確保合并后的數(shù)組有序？需要比較左右子數(shù)組的元素，依次取較小值放入臨時(shí)數(shù)組。邊界條件：遞歸終止條件（當(dāng)子數(shù)組長(zhǎng)度為1時(shí)停止遞歸）和合并時(shí)的邊界處理（如左右子數(shù)組的索引是否越界）。想象一下：想象你有一堆雜亂的書需要整理。你可以先將書分成兩堆（左堆和右堆），分別整理兩堆書，然后再將兩堆有序的書合并成一摞。具體步驟如下：分堆：不斷將書對(duì)半分，直到每堆只有一本書（自然有序）。整理小堆：因?yàn)閱伪緯呀?jīng)有序，無(wú)需處理。合并堆：從兩堆最頂上各拿一本書，比較封面序號(hào)，將序號(hào)較小的書放在新摞的頂部，重復(fù)此過(guò)程直到兩堆書全部合并完畢。這個(gè)場(chǎng)景對(duì)應(yīng)算法中的“歸并排序”，核心是“分治+合并”。解題步驟步驟1：分治排序-使用遞歸將原數(shù)組不斷二分，直到每個(gè)子數(shù)組長(zhǎng)度為1（即無(wú)法再分）。-遞歸終止條件：當(dāng)左邊界`l`等于右邊界`r`時(shí)，子數(shù)組僅有一個(gè)元素，無(wú)需排序。步驟2：合并子數(shù)組-假設(shè)左右子數(shù)組`nums[l...mid]`和`nums[mid+1...r]`已有序。-創(chuàng)建臨時(shí)數(shù)組`tmp`，用于存儲(chǔ)合并后的結(jié)果。-使用雙指針`lnow`（左子數(shù)組指針）和`rnow`（右子數(shù)組指針），從`l`到`r`依次比較兩子數(shù)組元素：-若左子數(shù)組元素較小，將`nums[lnow]`放入`tmp`，移動(dòng)`lnow`指針。-若右子數(shù)組元素較小，將`nums[rnow]`放入`tmp`，移動(dòng)`rnow`指針。-若兩元素相等，可任意選擇，此處優(yōu)先取左子數(shù)組元素。-當(dāng)某子數(shù)組遍歷完后，將剩余元素直接復(fù)制到`tmp`末尾。-最后將`tmp`中的結(jié)果復(fù)制回原數(shù)組`nums`的`l`到`r`區(qū)間。注意事項(xiàng)遞歸深度：歸并排序遞歸調(diào)用層數(shù)為`logn`，需注意?？臻g消耗。臨時(shí)空間：合并時(shí)需額外`O(n)`的臨時(shí)數(shù)組，確保不超出內(nèi)存限制。邊界處理：合并時(shí)判斷`lnow`和`rnow`是否越界，避免數(shù)組訪問(wèn)錯(cuò)誤。代碼+注釋classSolution{public://臨時(shí)數(shù)組用于存儲(chǔ)合并結(jié)果inttmp[50000];//遞歸排序函數(shù)，參數(shù)為待排序數(shù)組的區(qū)間[l,r]voidmysort(vector<int>&nums,intl,intr){if(l==r){//遞歸終止條件：子數(shù)組長(zhǎng)度為1return;}intmid=(l+r)/2;//中間索引//遞歸排序左右子數(shù)組mysort(nums,l,mid);mysort(nums,mid+1,r);intindex=l;//臨時(shí)數(shù)組當(dāng)前索引intlnow=l,rnow=mid+1;//左右子數(shù)組的起始指針//合并過(guò)程while(lnow<=mid||rnow<=r){if(rnow>r){//右子數(shù)組遍歷完畢tmp[index]=nums[lnow];lnow++;index++;}elseif(lnow>mid){//左子數(shù)組遍歷完畢tmp[index]=nums[rnow];rnow++;index++;}else{//兩子數(shù)組均未遍歷完tmp[index]=min(nums[lnow],nums[rnow]);//取較小值if(nums[lnow]<nums[rnow]){//若左元素小，移動(dòng)左指針lnow++;}else{//右元素?。ɑ蛳嗟龋苿?dòng)右指針rnow++;}index++;}}//將合并結(jié)果復(fù)制回原數(shù)組for(inti=l;i<=r;i++){nums[i]=tmp[i];}}vector<int>sortArray(vector<int>&nums){//調(diào)用遞歸排序函數(shù)，區(qū)間為整個(gè)數(shù)組[0,nums.size()-1]mysort(nums,0,nums.size()-1);returnnums;//排序后的結(jié)果已存儲(chǔ)在nums中，直接返回}};分析算法思路：采用經(jīng)典的歸并排序，利用分治思想將問(wèn)題分解為子問(wèn)題，再通過(guò)合并子結(jié)果得到最終答案。時(shí)間復(fù)雜度：O(nlogn)。每次遞歸將數(shù)組分為兩半，遞歸深度為logn，每層合并需要O(n)時(shí)間?？臻g復(fù)雜度：O(n)。臨時(shí)數(shù)組`tmp`需要