php版冒泡排序是如何實現(xiàn)的？

你好， 我是程序猿零壹。

無論學習哪一種編程語言，進行算法方面的訓練時都繞不開“排序”。排序在進階編程中有非常廣泛的應用，要想成為編程高手，排序算法是必須要掌握的。而冒泡排序算法作為一種交換排序算法，可以說是最簡單的排序算法之一，比較容易理解和實現(xiàn)。今天我們就一起來了解一下如何使用php來實現(xiàn)冒泡排序算法吧。

冒泡排序算法

冒泡排序算法，是一種計算機科學領域里比較簡單的排序算法。它需要重復的走訪過要排序的數(shù)列，依次比較兩個相鄰的元素，如果順序錯誤就進行交換，一直到?jīng)]有相鄰元素需要交換，即排序完成。

這個算法的名字由來是因為越小的元素經(jīng)過交換之后，會慢慢的浮到數(shù)列的頂端，就像碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。

原理

1. 比較相鄰的兩個元素，如果第一個比第二個大，就交換他們兩個；
2. 對每一對相鄰的元素做同樣的動作，從開始的第一對到隊尾的最后一對。在這一點，最后的元素應該是最大的數(shù)；
3. 針對所有元素重復以上的動作，除了最后一個；
4. 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要交換；

排序過程

假如需要對給定的無序數(shù)組進行排序。

第一輪排序

第一次排序，將指針放在隊首位置，即9的位置，并與7進行比較，9比7大，所以9跟7交換位置。

第二次排序，將指針往后移動，置于9的位置，并與1進行比較，9比1大，所以9跟1交換位置。

第三次排序，將指針往后移動，置于9的位置，并與3進行比較，9比3大，所以9跟3交換位置。

第四次排序，將指針往后移動，置于9的位置，并與2進行比較，9比2大，所以9跟2交換位置。

到此，9已經(jīng)處于隊尾的位置，不需要再繼續(xù)參與排序了，第一輪排序結束。

第二輪排序

第一次排序，將指針置于隊首的位置，即7的位置，并與1進行比較，7比1大，所以7跟1交換位置。

第二次排序，將指針往后移動，置于7的位置，并與3進行比較，7比3大，所以7跟3交換位置。

第三次排序，將指針往后移動，置于7的位置，并與2進行比較，7比2大，所以7跟2交換位置。

到此，7已經(jīng)排好序，不需要再參與排序了，第二輪排序結束。

第三輪排序

第一次排序，將指針置于隊首的位置，即1的位置，并與3進行比較，1比3小，所以1跟3不用交換位置。

第二次排序，將指針往后移動，置于3的位置，并與2進行比較，3比2大，所以3跟2交換位置。

到此，3已經(jīng)排好序，不需要再參與排序了，第三輪排序結束。

第四輪排序

第一次排序，將指針置于隊首的位置，即1的位置，并與2進行比較，1比2小，所以1跟2不用交換位置。

到此，1跟2已經(jīng)排好序，排序結束。

代碼實現(xiàn)

function bubbleSort($array){
    $count = count($array);
    for ($i=0;$i<$count - 1;$i++){
        $isChange = false;
        for ($j=0;$j<$count-$i-1;$j++) {
            if($array[$j] > $array[$j+1]) {
                $t = $array[$j];
                $array[$j] = $array[$j+1];
                $array[$j+1] = $t;
                $isChange = true;
            }
        }
        if(!$isChange) {
            break;
        }
    }
    return $array;
}

上面代碼利用了雙循環(huán)來實現(xiàn)排序。外循環(huán)用來控制所有輪次，內循環(huán)用來控制每一輪的排序。那上面的代碼有沒有可以優(yōu)化的地方呢？我們來思考一個問題，假如所有數(shù)列都是有序的，那么第一輪第一次排序之后所有數(shù)列沒有發(fā)生一次交換，這時候其實已經(jīng)可以不用再繼續(xù)后面的循環(huán)了，這樣可以減少循環(huán)的次數(shù)。

我們可以做個小小的改動，在一輪排序之后，如果沒有發(fā)生任何交換，即表明整個數(shù)列有序。

改動后的代碼如下：

function bubbleSort($array){
    $count = count($array);
    for ($i=0;$i<$count - 1;$i++){
        $isChange = false;
        for ($j=0;$j<$count-$i-1;$j++) {
            if($array[$j] > $array[$j+1]) {
                $t = $array[$j];
                $array[$j] = $array[$j+1];
                $array[$j+1] = $t;
                $isChange = true;
            }
        }
        if(!$isChange) {
            break;
        }
    }
    return $array;
}

以上就是今天所有的內容了。