搜尋
首頁後端開發php教程PHP冒泡排序使用詳解

PHP冒泡排序使用詳解

May 16, 2018 pm 03:20 PM
php使用詳解

這次帶給大家PHP冒泡排序使用詳解,PHP冒泡排序使用的注意事項有哪些,下面就是實戰案例,一起來看一下。

基本概念:

冒泡排序是一種交換排序,它的基本想法是:兩兩比較相鄰記錄的關鍵字,如果反序則交換,直到沒有反序的記錄為止。

最簡單排序實作:

我們先來看看在沒有學習各種排序方法前經常使用的排序方法(至少我是這樣。。。):

//这里使用了类型提示(type hint) array,不熟悉或者不习惯的同学大可去掉,不影响运算结果
function MySort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    for($j = $i + 1;$j < $length;$j ++){
      //将小的关键字放前面
      if($arr[$i] > $arr[$j]){
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
      }
    }
  }
}
$arr = array(9,1,5,8,3,7,4,6,2);
MySort($arr);
print_r($arr);

上面的這段程式碼嚴格意義上說,不算是標準的冒泡排序,因為它不滿足「兩兩比較相鄰記錄」的冒泡排序思想,它只是一個簡單的交換排序。想法不過是:從第一個關鍵字開始,將每位關鍵字與它後面的所有關鍵字比較,並交換得到其中的最小值。但這個演算法是非常低效的。

冒泡排序演算法:

它重複地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換,也就是說該數列已經排序完成。

這個演算法的名字由來是因為陣列中越大的元素會因為一次次排序後逐漸「沉」到陣列的後面,而越小的元素會逐漸「浮」到陣列的前面,故名。

冒泡排序演算法的運作如下:(從後往前)

1.比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。
2.對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。在這一點,最後的元素應該會是最大的數字。
3.針對所有的元素重複以上的步驟,除了最後一個。
4.持續每次對越來越少的元素重複上面的步驟,直到沒有任何一對數字需要比較。

看文字描述不一定看得懂,看程式碼吧:

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
//冒泡排序
function BubbleSort(array &$arr){
  $length = count($arr);
  for($i = 0;$i < $length - 1;$i ++){
    //从后往前逐层上浮小的元素
    for($j = $length - 2;$j >= $i;$j --){
      //两两比较相邻记录
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
      }
    }
  }
}

#冒泡排序演算法改進:

上面的冒泡排序演算法是否還可以最佳化呢?答案是肯定的。試想一下,如果我們待排序的序列是{2,1,3,4,5,6,7,8,9},也就是說,除了第一和第二個關鍵字需要交換外,別的都已經是正常的順序了。當i = 0 時,交換了2 和1 ,此時的序列已經是有序的了,但是演算法仍然不依不撓地將i = 2 到9 以及每個循環中的j 循環都執行了一遍,儘管並沒有交換數據,但是之後的大量比較還是大大地多餘了。
當i = 2 時,我們已經對9 與8,8 與7,·······,3 與2 做了比較,沒有任何數據交換,這就說明此序列已經有序,不需要再繼續後面的循判斷工作了(後面的工作也是不會發生任何資料交換,再做也是沒有意義了)。為了實現這個想法,我們需要改進程式碼,增加一個標記變數flag 來實現這個演算法的改進:

//交换方法
function swap(array &$arr,$a,$b){
  $temp = $arr[$a];
  $arr[$a] = $arr[$b];
  $arr[$b] = $temp;
}
/冒泡排序的优化(如果某一次循环的时候没有发生元素的交换,则整个数组已经是有序的了)
function BubbleSort1(array &$arr){
  $length = count($arr);
  $flag = TRUE;
  for($i = 0;($i < $length - 1) && $flag;$i ++){
    $flag = FALSE;
    for($j = $length - 2;$j >= $i;$j --){
      if($arr[$j] > $arr[$j + 1]){
        swap($arr,$j,$j+1);
        $flag = TRUE;
      }
    }
  }
}

程式碼改變的關鍵就是在i 變數的for迴圈中,增加了對flag是否為true 的判斷,經過這樣的改進,冒泡排序在性能上就有了一些提升,可以避免因已經有序的情況下的無意義循環判斷。

冒泡演算法總的時間複雜度是 O(n^2)

冒泡排序是穩定排序。

相信看了本文案例你已經掌握了方法,更多精彩請關注php中文網其它相關文章!

推薦閱讀:

PHP希爾排序案例分析

PHP堆排序演算法實例分析

以上是PHP冒泡排序使用詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
超越炒作:評估當今PHP的角色超越炒作:評估當今PHP的角色Apr 12, 2025 am 12:17 AM

PHP在現代編程中仍然是一個強大且廣泛使用的工具,尤其在web開發領域。 1)PHP易用且與數據庫集成無縫,是許多開發者的首選。 2)它支持動態內容生成和麵向對象編程,適合快速創建和維護網站。 3)PHP的性能可以通過緩存和優化數據庫查詢來提升,其廣泛的社區和豐富生態系統使其在當今技術棧中仍具重要地位。

PHP中的弱參考是什麼?什麼時候有用?PHP中的弱參考是什麼?什麼時候有用?Apr 12, 2025 am 12:13 AM

在PHP中,弱引用是通過WeakReference類實現的,不會阻止垃圾回收器回收對象。弱引用適用於緩存系統和事件監聽器等場景,需注意其不能保證對象存活,且垃圾回收可能延遲。

解釋PHP中的__ Invoke Magic方法。解釋PHP中的__ Invoke Magic方法。Apr 12, 2025 am 12:07 AM

\_\_invoke方法允許對象像函數一樣被調用。 1.定義\_\_invoke方法使對象可被調用。 2.使用$obj(...)語法時,PHP會執行\_\_invoke方法。 3.適用於日誌記錄和計算器等場景,提高代碼靈活性和可讀性。

解釋PHP 8.1中的纖維以進行並發。解釋PHP 8.1中的纖維以進行並發。Apr 12, 2025 am 12:05 AM

Fibers在PHP8.1中引入,提升了並發處理能力。 1)Fibers是一種輕量級的並發模型,類似於協程。 2)它們允許開發者手動控制任務的執行流,適合處理I/O密集型任務。 3)使用Fibers可以編寫更高效、響應性更強的代碼。

PHP社區:資源,支持和發展PHP社區:資源,支持和發展Apr 12, 2025 am 12:04 AM

PHP社區提供了豐富的資源和支持,幫助開發者成長。 1)資源包括官方文檔、教程、博客和開源項目如Laravel和Symfony。 2)支持可以通過StackOverflow、Reddit和Slack頻道獲得。 3)開發動態可以通過關注RFC了解。 4)融入社區可以通過積極參與、貢獻代碼和學習分享來實現。

PHP與Python:了解差異PHP與Python:了解差異Apr 11, 2025 am 12:15 AM

PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

php:死亡還是簡單地適應?php:死亡還是簡單地適應?Apr 11, 2025 am 12:13 AM

PHP不是在消亡,而是在不斷適應和進化。 1)PHP從1994年起經歷多次版本迭代,適應新技術趨勢。 2)目前廣泛應用於電子商務、內容管理系統等領域。 3)PHP8引入JIT編譯器等功能,提升性能和現代化。 4)使用OPcache和遵循PSR-12標準可優化性能和代碼質量。

PHP的未來:改編和創新PHP的未來:改編和創新Apr 11, 2025 am 12:01 AM

PHP的未來將通過適應新技術趨勢和引入創新特性來實現:1)適應云計算、容器化和微服務架構,支持Docker和Kubernetes;2)引入JIT編譯器和枚舉類型,提升性能和數據處理效率;3)持續優化性能和推廣最佳實踐。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳圖形設置
3 週前By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您聽不到任何人,如何修復音頻
3 週前By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25:如何解鎖Myrise中的所有內容
4 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

WebStorm Mac版

WebStorm Mac版

好用的JavaScript開發工具

MantisBT

MantisBT

Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

SublimeText3 Linux新版

SublimeText3 Linux新版

SublimeText3 Linux最新版

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器