常見十大算法 冒泡算法

它重複地走訪過要排序的數列，一次比較兩個元素，如果它們的順序錯誤就把它們交換過來。走訪數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。

1.冒泡算法-簡單傳統效率最低

• <1>.比較相鄰的元素。如果第一個比第二個大，就交換它們兩個；
• <2>.對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對，這樣在最後的元素應該會是最大的數；
• <3>.針對所有的元素重複以上的步驟，除了最後一個；
• <4>.重複步驟1~3，直到排序完成。
• 例如：以下是按順序排序，改變符号即倒序排序

php

function bubbleSort($arr){
    for ($i=0;$i<count($arr);$i++){
        for ($j=0;$j<count($arr)-1-$i;$j++){
            if ($arr[$j]>$arr[$j+1]){
                $temp = $arr[$j+1];
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $temp;
            }
        }
    }

    return $arr;

}

$arr = array(7,3,9,6,44,22,44,11,33,4);
$arr = bubbleSort($arr);
var_dump($arr);
           

JavaScript

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        //相鄰元素兩兩對比
                var temp = arr[j+1];        //元素交換
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
           

2.冒泡算法-改進-定位效率高

設定一标志性變量$pos,用于記錄每趟排序中最後一次進行交換的位置。由于pos位置之後的記錄均已交換到位,故在進行下一趟排序時隻要掃描到pos位置即可。

php

function bubbleSort2($arr) {
    $i = count($arr)-1;  //初始時,最後位置保持不變
    while ( $i> 0) {
        $pos= 0; //每趟開始時,無記錄交換
        for ($j= 0; $j< $i; $j++)
            if ($arr[$j]> $arr[$j+1]) {
                $pos= $j; //記錄交換的位置
                $tmp = $arr[$j]; $arr[$j]=$arr[$j+1];$arr[$j+1]=$tmp;
            }
        $i= $pos; //為下一趟排序作準備
     }

    return $arr;
}
           

js

function bubbleSort2(arr) {
    console.time('改進後冒泡排序耗時');
    var i = arr.length-1;  //初始時,最後位置保持不變
    while ( i> 0) {
        var pos= 0; //每趟開始時,無記錄交換
        for (var j= 0; j< i; j++)
            if (arr[j]> arr[j+1]) {
                pos= j; //記錄交換的位置
                var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
            }
        i= pos; //為下一趟排序作準備
     }
     console.timeEnd('改進後冒泡排序耗時');
     return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
           

3.冒泡算法-改進-前後一起提高效率

傳統冒泡排序中每一趟排序操作隻能找到一個最大值或最小值,我們考慮利用在每趟排序中進行正向和反向兩遍冒泡的方法一次可以得到兩個最終值(最大者和最小者) , 進而使排序趟數幾乎減少了一半。

php

function bubbleSort3($arr){
    $low = 0;
    $high = count($arr) - 1; //設定變量的初始值

    while ($low < $high) {
        for ($j = $low; $j < $high; ++$j) //正向冒泡,找到最大者
            if ($arr[$j] > $arr[$j + 1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
            }
        --$high;                 //修改high值, 前移一位
        for ($j = $high; $j > $low; --$j) //反向冒泡,找到最小者
            if ($arr[$j] > $arr[$j + 1]) {
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $tmp;
            }
    }
    return $arr;
}
           

js

function bubbleSort3(arr3) {
    var low = 0;
    var high= arr.length-1; //設定變量的初始值
    var tmp,j;
    console.time('2.改進後冒泡排序耗時');
    while (low < high) {
        for (j= low; j< high; ++j) //正向冒泡,找到最大者
            if (arr[j]> arr[j+1]) {
                tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
            }
        --high;                 //修改high值, 前移一位
        for (j=high; j>low; --j) //反向冒泡,找到最小者
            if (arr[j] arr[j+1]) {
                tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
            }
	}
}
           

若本文對大家了解算法有所幫助，點個贊或打個賞吧~謝謝您嘞~~