1.歸并排序

merge合并

2.歸并排序的擴展

–小和問題

任何一個數(shù)右邊有多少個數(shù)比它大

歸并排序比較之后就有序，

可直接通過下標(biāo)計算的方式確定大小關(guān)系，

有序范圍不斷擴大，更加快速高效

–逆序?qū)栴}

左邊數(shù)比右邊數(shù)大構(gòu)成逆序?qū)?/p>

任何一個數(shù)右邊有多少個數(shù)比它小

《筆試必出現(xiàn)》

3.優(yōu)點：任何比較都會變成有序的部分

使O(N^2)變成O(N*log2 N）

4.遞歸形式變成非遞歸形式

最多變幾回O(N*log2 N）

3.堆排序

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-N1LlWsiz-1656476490842)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_7835\Image.png)]

首先理解堆結(jié)構(gòu)

—>某一個黑盒結(jié)構(gòu)，用戶要求提供兩個方法

第一個add(num)添加數(shù)字到黑盒中

第二個popmax()返回int，把最大值返回并從黑盒中拿掉

用戶要求該兩個方法時間復(fù)雜度盡量低

堆，分為實際結(jié)構(gòu)和腦海中結(jié)構(gòu)，實際上是數(shù)組結(jié)構(gòu)，腦海中是完全二叉樹結(jié)構(gòu)

完全二叉樹是指：：滿足從左到右依次變滿的過程，例如：[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-PAqaS00w-1656476490844)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_27645\Image.png)]

反例，（不是）：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-vu0ieLsJ-1656476490844)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_2152\Image.png)]

即：必須在每一層滿足從左到右變滿（這是腦海中的堆結(jié)構(gòu)，而實際上是數(shù)組形式）

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-PNAJ6V3c-1656476490845)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_27167\Image.png)]

對應(yīng)規(guī)則：任意一個位置i，左孩子2i+1,右孩子2i+2,父（i-1）/2.（注意：-1/2在計算機中是0）

（補充：默認(rèn)完全二叉樹都是從0開始的）

例如從1開始：左孩子2i,右孩子2i+1,父i/2.

往數(shù)據(jù)中不斷填值即為二叉樹在不斷增長

堆分大根堆和小根堆，大根堆：頭節(jié)點是最大值

例如：

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-1vl9gdrN-1656476490845)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_11731\Image.png)]

用戶每輸入一個i都和自己的父（i-1）/2比較，比父大即交換，保證每一步都是大根堆，在一個連續(xù)的范圍內(nèi)都是有序的，保證每加上一個數(shù)都是大根堆（heapinsert）

代碼：

//arr[0...index-1]已經(jīng)是大根堆了，某個數(shù)現(xiàn)在處在index位置上，往上繼續(xù)移動 //arr[0...index]都是大根堆 public static void heapinsert(int[] arr,int index){ //1 2 while(arr[index]>arr[(index-1)/2]){ swap(arr,index,(index-1)/2); index = (index-1)/2; } }

add()方法的時間復(fù)雜度是O(logN)

下面介紹popmax()方法

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Snx0IctM-1656476490846)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_24081\Image.png)]

找到最大值并返回，并把這個數(shù)刪掉

大根堆的值就是最大值，令t=8保存最大值，通過有效區(qū)長度6找到最后一個數(shù)，填到0位置，把有效區(qū)長度改為5，然后從頭部開始，做heapify 操作，找最大的孩子，和自己交換，不斷向下直到?jīng)]有孩子（超過有效區(qū)大小，即越不越界），此時整個結(jié)構(gòu)依然是大根堆。heapify和popmax都是logN水平的。

解釋：擴容一次要復(fù)制原數(shù)組，時間復(fù)雜度是O(N），總擴容次數(shù)是logN，總時間復(fù)雜度是logNO(N),所以平均單次擴容的時間復(fù)雜度是（logNO(N)）/N，得logN（總添加次數(shù)是N，并非每次添加都擴容）

優(yōu)先級序列的底層就是堆，

實際工程中不使用鏈表，因為無法使用公式，在數(shù)組中尋址很快，能迅速找到一個數(shù)的左孩子和右孩子。

//某個數(shù)再index位置，看看是否往下沉 //不斷和左右兩個孩子比較 //較大的孩子如果大于了當(dāng)前的父，父節(jié)點往下沉，較大孩子上來 public static void heapify(int[] arr,int index,int heapSize){ int left = index*2+1;//左孩子的下標(biāo) while(left<heaoSize){//下方還有孩子的時候 //兩個孩子中，誰的值大，就把下標(biāo)給largest int largest = left +1<heapSize&&arr[left+1]>arr[left] ?left+1:left; //父和比較大的孩子之間，誰的值大，把下標(biāo)給largest largest = arr[largest]>arr[index]?lardest:index; if(largest==index){//最大值就是自己 break; } swap(arr,largest,index);//最大值不是自己則交換 index=largest;//index來到下方 left=index*2+1;//重新找孩子 } }

堆排序舉例：先使有效區(qū)=0，使整個數(shù)組變成大根堆

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-6OwB5chx-1656476490846)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_21674\Image.png)]

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-Gun5BgsA-1656476490846)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_9735\Image.png)]

第一步目標(biāo)達(dá)成。

現(xiàn)在有效區(qū)=5，

等同于做popmax()操作，尾和頭交換，有效區(qū)-1

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-1zXsdAeO-1656476490848)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_2737\Image.png)]

然后從頭節(jié)點做heapify操作

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-bMhz2qNg-1656476490849)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_5838\Image.png)]

再把有效區(qū)-1，使4斷聯(lián)

再從0開始做heapify。。。一直到有效區(qū)減成0，排序完成

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-56jkZmZS-1656476490849)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_1299\Image.png)]

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-k8XUTgXV-1656476490850)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_23057\Image.png)]

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-6pAT5MEU-1656476490851)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_11852\Image.png)]

這就是堆排序。

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-dsmWTzqT-1656476490851)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_743\Image.png)]

估計總時間復(fù)雜度

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-XEfisJlT-1656476490852)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_24370\Image.png)]

O(N)

總結(jié)：用戶一股腦給全部數(shù)據(jù)比一步一步heapinsert要快

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-KX4HPXVX-1656476490852)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_14274\Image.png)]

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-09mXQEwW-1656476490852)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_30248\Image.png)]

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-aqypyZyx-1656476490853)(C:\Users\Ulrica\AppData\Local\Temp\chrome_drag24592_1676\Image.png)]

假設(shè)k=7，申請一個大小為8的小根堆，把數(shù)組的前8個數(shù)扔到小根堆里，然后彈出一個最小值，放在0位置，完畢。

總結(jié)

以上是生活随笔為你收集整理的牛客算法笔记【second week】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。