首頁 > php教程 > php手册 > 主體

冒泡排序以及遇到一個關於陣列一大一小的問題

WBOY
發布: 2016-08-08 08:49:49
原創
1557 人瀏覽過

冒泡排序

冒泡排序(Bubble Sort),是一種電腦科學領域的較簡單的排序演算法。

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

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

 

l  依序比較相鄰的兩個元素,消除逆序(逆序是數學上的概念,是成對出現的,例如50,30就是一對逆序,所謂的消除逆序,就是大的放後面,小的放前面)

l  這樣,一輪比較下來,最大的那個數一對是在最後面!

l  然後,再繼續新的一輪的比較,注意,剛才一輪後的最大值不再參與比較,這樣,這一輪參與比較的數值就比上一輪少一個如此反复,直到最後只剩下兩個數值比較為止

 

所以是一個雙重循環,外層控制輪數,內層控制每輪比較的次數。  

如果數組有n個元素,一共需要比較n-1輪,也就是外循環的次數!

 

補充一個其他知識點:

list — 把陣列中的值賦給一些變數 ,從小到大,反過來賦值從大到小

 

 

下面說一下我寫的冒泡排序,以及註解我自己對它的理解:

<span style="color: #008000;">//</span><span style="color: #008000;">冒泡排序,让数组从小到大依次排序</span>
<span style="color: #000000;">function maopao($arr){
    </span><span style="color: #008000;">//</span><span style="color: #008000;">双层循环,外层控制,$i代表循环的轮数,比较轮数等于数组的个数减1,$i<$len相当于数组个数-1,例如8个,当$i=7是最后的比较,符合8-1=7;</span>
    <span style="color: #0000ff;">for</span>($i=<span style="color: #800080;">1</span>,$len=count($arr);$i<$len;$i++<span style="color: #000000;">){
        </span><span style="color: #008000;">//</span><span style="color: #008000;">内层控制每一轮比较的次数,$k=下标,每一轮比较完最后一个将不再参与比较,下标从0开始</span>
        <span style="color: #0000ff;">for</span>($k=<span style="color: #800080;">0</span>;$k<$len-$i;$k++<span style="color: #000000;">){
            </span><span style="color: #008000;">//</span><span style="color: #008000;">比较相邻的两个数,如果前面的数值比后面的大就调换下位置,通过中间数,如果不比它大,则不用调换</span>
            <span style="color: #0000ff;">if</span>($arr[$k]>$arr[$k+<span style="color: #800080;">1</span><span style="color: #000000;">]){
                </span><span style="color: #008000;">//</span><span style="color: #008000;">调换位置</span>
                $tem=<span style="color: #000000;">$arr[$k];
                $arr[$k]</span>=$arr[$k+<span style="color: #800080;">1</span><span style="color: #000000;">];
                $arr[$k</span>+<span style="color: #800080;">1</span>]=<span style="color: #000000;">$tem;
            }
        }
    }
    </span><span style="color: #0000ff;">return</span><span style="color: #000000;"> $arr;
}
$arr1</span>=array(<span style="color: #800080;">45</span>,<span style="color: #800080;">85</span>,<span style="color: #800080;">12</span>,<span style="color: #800080;">22</span>,<span style="color: #800080;">36</span>,<span style="color: #800080;">7</span>,<span style="color: #800080;">75</span>,<span style="color: #800080;">15</span>,<span style="color: #800080;">40</span>,<span style="color: #800080;">64</span><span style="color: #000000;">);
</span><span style="color: #008000;">//</span><span style="color: #008000;"> echo count($arr1);</span>
echo <span style="color: #800000;">'</span><span style="color: #800000;"><pre class="brush:php;toolbar:false"></span><span style="color: #800000;">'</span><span style="color: #000000;">;
print_r(maopao($arr1));</span></span>
登入後複製

效果:實現了數組從小到大的排序

如果要實現從大到小,也是一樣的演算法,都是透過中間數的比較來交換。

 

接下來說一說我在面試曾經遇到的一個問題:取一個數組,讓這個數組按第一個最大,第二個最小,第三個第二大,第四個第二小…這樣進行排序。

當時我只想到好像有個

array_pop:將陣列的最後一個資料彈出

array_shift:從陣列的前面彈出資料

那讓數組從大到小排序後,彈出第一個就拿到最大的,彈出最後一個就拿到最小的,把這兩個放一起就一個最大一個最小,再繼續進行這樣的取出,直到取完所有。

回去我就去嘗試我這個可不可行,下面我就說下我自己試的這個方法

 

舉例:

 

 

所以第一步:我是先讓數組進行透過冒泡進行從大到小的排序

 

第二步,我是透過遞歸把彈出來的第一個(最大)和最後一個(最小)放一起,再進行取出,直到取完為止。

 

效果:

這個有更好的方法,我這裡說的是我當時剛好想到的那個方法,哈,莫見怪,望吐槽。

來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門推薦
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!