算法思想
冒泡排序?qū)儆谝环N典型的交換排序懊蒸。就是通過元素的兩兩比較测秸，判斷是否符合要求计维，如過不符合就交換位置來達(dá)到排序的目的袜香。冒泡排序名字的由來就是因?yàn)樵诮粨Q過程中，類似水冒泡鲫惶，序谑住（大）的元素經(jīng)過不斷的交換由水底慢慢的浮到水的頂端。
冒泡排序原理
- 比較相鄰的元素欠母。如果第一個(gè)比第二個(gè)大欢策，就交換他們兩個(gè)
- 對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對赏淌。在這一點(diǎn)踩寇，最后的元素應(yīng)該會(huì)是最大的數(shù)
- 針對所有的元素重復(fù)以上的步驟，除了最后一個(gè)
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟六水，直到?jīng)]有任何一對數(shù)字需要比較
冒泡排序示例說明
將數(shù)組 10,1,35,61,89,36,55 進(jìn)行排序
第一趟排序(找出最大值)：
- 第一次排序：10和1比較俺孙，10大于1，交換位置 [1,10,35,61,89,36,55]
- 第二趟排序：10和35比較掷贾，10小于35睛榄，不交換位置 [1,10,35,61,89,36,55]
- 第三趟排序：35和61比較，35小于61想帅，不交換位置 [1,10,35,61,89,36,55]
- 第四趟排序：61和89比較场靴，61小于89，不交換位置 [1,10,35,61,89,36,55]
- 第五趟排序：89和36比較，89大于36旨剥，交換位置 [1,10,35,61,36,89,55]
- 第六趟排序：89和55比較咧欣，89大于55，交換位置 [1,10,35,61,36,55,89]
- 第一趟總共進(jìn)行了六次比較轨帜，排序結(jié)果：[1,10,35,61,36,55,89]
第二趟排序(循環(huán)處理第一次處理的結(jié)果找出第二大的值)：
- 第一次排序：1和10比較魄咕，1小于10，不交換位置 1,10,35,61,36,55,89
- 第二次排序：10和35比較蚌父，10小于35蚕礼，不交換位置 1,10,35,61,36,55,89
- 第三次排序：35和61比較，35小于61梢什，不交換位置 1,10,35,61,36,55,89
- 第四次排序：61和36比較，61大于36朝聋，交換位置 1,10,35,36,61,55,89
- 第五次排序：61和55比較嗡午，61大于55，交換位置 1,10,35,36,55,61,89
- 第二趟總共進(jìn)行了5次比較冀痕，排序結(jié)果：1,10,35,36,55,61,89
第三趟排序：
- 第一次排序：1和10比較荔睹，1小于10，不交換位置 1,10,35,36,55,61,89
- 第二次排序：10和35比較言蛇，10小于35僻他，不交換位置 1,10,35,36,55,61,89
- 第三次排序：35和36比較，35小于36腊尚，不交換位置 1,10,35,36,55,61,89
- 第四次排序：36和61比較吨拗，36小于61，不交換位置 1,10,35,36,55,61,89
- 第三趟總共進(jìn)行了4次比較婿斥，排序結(jié)果：1,10,35,36,55,61,89
- 到目前位置已經(jīng)為有序的情形了劝篷。
冒泡排序分析
N個(gè)數(shù)字要排序完成，總共進(jìn)行N-1趟排序民宿，每i趟的排序次數(shù)為(N-i)次娇妓，所以可以用雙重循環(huán)語句，外層控制循環(huán)多少趟活鹰，內(nèi)層控制每一趟的循環(huán)次數(shù)
冒泡排序的優(yōu)點(diǎn)：每進(jìn)行一趟排序哈恰，就會(huì)少比較一次，因?yàn)槊窟M(jìn)行一趟排序都會(huì)找出一個(gè)較大值志群。如上例：第一趟比較之后着绷，排在最后的一個(gè)數(shù)一定是最大的一個(gè)數(shù)，第二趟排序的時(shí)候赖舟，只需要比較除了最后一個(gè)數(shù)以外的其他的數(shù)蓬戚，同樣也能找出一個(gè)最大的數(shù)排在參與第二趟比較的數(shù)后面，第三趟比較的時(shí)候宾抓，只需要比較除了最后兩個(gè)數(shù)以外的其他的數(shù)子漩，以此類推……也就是說豫喧，沒進(jìn)行一趟比較，每一趟少比較一次幢泼，一定程度上減少了算法的量紧显。
php代碼實(shí)現(xiàn)
<?php
$arr = [10,1,35,61,89,36,55];
/**
* [bubbleSort 冒泡排序]
* @url示例:
* @DateTime:2020-03-29
* @邏輯:
* @param [type] $arr [排序的數(shù)組]
* @return [type] [排序完成的數(shù)組]
*/
function bubbleSort($arr)
{
$len=count($arr);
for ($i = 1; $i < $len; $i++) {
for ($k = 0; $k < $len - $i; $k++) {
if ($arr[$k] > $arr[$k + 1]) {
$tmp = $arr[$k+1];
$arr[$k+1] = $arr[$k];
$arr[$k] = $tmp;
}
}
}
return $arr;
}
echo '<pre>';
$result = bubbleSort($arr);
var_dump($result);
冒泡排序優(yōu)化
針對問題
數(shù)據(jù)的順序排好之后，冒泡算法仍然會(huì)繼續(xù)進(jìn)行下一輪的比較缕棵，直到arr.length-1次孵班，后面的比較沒有意義的
方案
設(shè)置標(biāo)志位flag，如果發(fā)生了交換flag設(shè)置為true招驴；如果沒有交換就設(shè)置為false篙程。這樣當(dāng)一輪比較結(jié)束后如果flag仍為false，即：這一輪沒有發(fā)生交換别厘，說明數(shù)據(jù)的順序已經(jīng)排好虱饿，沒有必要繼續(xù)進(jìn)行下去
php優(yōu)化之后
<?php
$arr = [10,1,35,61,89,36,55];
/**
* [bubbleSort 冒泡排序]
* @url示例:
* @DateTime:2020-03-29
* @邏輯:
* @param [type] $arr [排序的數(shù)組]
* @return [type] [排序完成的數(shù)組]
*/
function bubbleSort($arr)
{
$len=count($arr);
$flag=null; //設(shè)置交換標(biāo)識(shí)
for ($i = 1; $i < $len; $i++) {
$flag = false;
for ($k = 0; $k < $len - $i; $k++) {
if ($arr[$k] > $arr[$k + 1]) {
$tmp = $arr[$k+1];
$arr[$k+1] = $arr[$k];
$arr[$k] = $tmp;
$flag = true;
}
}
if(!$flag) break;
}
return $arr;
}
echo '<pre>';
$result = bubbleSort($arr);
var_dump($result);
