PHP實作堆排序演算法(程式碼範例)
在電腦科學中,heapsort(1964年由J. W. J. Williams發明)是一種基於比較的排序演算法。 Heapsort(堆排序)可以看作是一種改進的選擇排序:與該演算法類似,它將輸入分為已排序區域和未排序區域,並透過提取最大的元素並將其移動到已排序區域來互動式地縮小未排序區域。改進包括使用堆疊資料結構,而不是線性時間搜尋來找到最大值。
儘管在大多數機器上,它的實際運行速度比實現良好的快速排序要慢一些,但它的優勢是在最壞情況下O(n log n)運行時更有利。堆排序是一種就地排序演算法,但它不是一種穩定排序。
heapsort演算法對一組隨機排列的值進行排序。在演算法的第一階段,數組元素被重新排序以滿足堆屬性。在進行實際排序之前,將簡要展示堆樹結構以供說明。
PHP堆排序演算法想法示意圖:
#PHP堆排序實作程式碼如下:
<?php class Node { private $_i; public function __construct($key) { $this->_i = $key; } public function getKey() { return $this->_i; } } class Heap { private $heap_Array; private $_current_Size; public function __construct() { $heap_Array = array(); $this->_current_Size = 0; } public function remove() { $root = $this->heap_Array[0]; $this->heap_Array[0] = $this->heap_Array[--$this->_current_Size]; $this->bubbleDown(0); return $root; } public function bubbleDown($index) { $larger_Child = null; $top = $this->heap_Array[$index]; while ($index < (int)($this->_current_Size/2)) { $leftChild = 2 * $index + 1; $rightChild = $leftChild + 1; if ($rightChild < $this->_current_Size && $this->heap_Array[$leftChild] < $this->heap_Array[$rightChild]) { $larger_Child = $rightChild; } else { $larger_Child = $leftChild; } if ($top->getKey() >= $this->heap_Array[$larger_Child]->getKey()) { break; } $this->heap_Array[$index] = $this->heap_Array[$larger_Child]; $index = $larger_Child; } $this->heap_Array[$index] = $top; } public function insertAt($index, Node $newNode) { $this->heap_Array[$index] = $newNode; } public function incrementSize() { $this->_current_Size++; } public function getSize() { return $this->_current_Size; } public function asArray() { $arr = array(); for ($j = 0; $j < sizeof($this->heap_Array); $j++) { $arr[] = $this->heap_Array[$j]->getKey(); } return $arr; } } function heapsort(Heap $Heap) { $size = $Heap->getSize(); for ($j = (int)($size/2) - 1; $j >= 0; $j--) { $Heap->bubbleDown($j); } for ($j = $size-1; $j >= 0; $j--) { $BiggestNode = $Heap->remove(); $Heap->insertAt($j, $BiggestNode); } return $Heap->asArray(); } $arr = array(3, 0, 2, 5, -1, 4, 1); echo "原始数组 : "; echo implode(', ',$arr ); $Heap = new Heap(); foreach ($arr as $key => $val) { $Node = new Node($val); $Heap->insertAt($key, $Node); $Heap->incrementSize(); } $result = heapsort($Heap); echo "\n排序后数组 : "; echo implode(', ',$result)."\n";
輸出:
原始数组 : 3, 0, 2, 5, -1, 4, 1 排序后数组 : -1, 0, 1, 2, 3, 4, 5
這篇文章就是關於PHP堆排序的介紹,希望對需要的朋友有幫助!
以上是PHP實作堆排序演算法(程式碼範例)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

JWT是一種基於JSON的開放標準,用於在各方之間安全地傳輸信息,主要用於身份驗證和信息交換。 1.JWT由Header、Payload和Signature三部分組成。 2.JWT的工作原理包括生成JWT、驗證JWT和解析Payload三個步驟。 3.在PHP中使用JWT進行身份驗證時,可以生成和驗證JWT,並在高級用法中包含用戶角色和權限信息。 4.常見錯誤包括簽名驗證失敗、令牌過期和Payload過大,調試技巧包括使用調試工具和日誌記錄。 5.性能優化和最佳實踐包括使用合適的簽名算法、合理設置有效期、

會話劫持可以通過以下步驟實現:1.獲取會話ID,2.使用會話ID,3.保持會話活躍。在PHP中防範會話劫持的方法包括:1.使用session_regenerate_id()函數重新生成會話ID,2.通過數據庫存儲會話數據,3.確保所有會話數據通過HTTPS傳輸。

SOLID原則在PHP開發中的應用包括:1.單一職責原則(SRP):每個類只負責一個功能。 2.開閉原則(OCP):通過擴展而非修改實現變化。 3.里氏替換原則(LSP):子類可替換基類而不影響程序正確性。 4.接口隔離原則(ISP):使用細粒度接口避免依賴不使用的方法。 5.依賴倒置原則(DIP):高低層次模塊都依賴於抽象,通過依賴注入實現。

在PHPStorm中如何進行CLI模式的調試?在使用PHPStorm進行開發時,有時我們需要在命令行界面(CLI)模式下調試PHP�...

如何在系統重啟後自動設置unixsocket的權限每次系統重啟後,我們都需要執行以下命令來修改unixsocket的權限:sudo...

靜態綁定(static::)在PHP中實現晚期靜態綁定(LSB),允許在靜態上下文中引用調用類而非定義類。 1)解析過程在運行時進行,2)在繼承關係中向上查找調用類,3)可能帶來性能開銷。
