關於冒泡,二分法插入,快速排序演算法的介紹

jacklove
發布: 2023-03-31 12:28:01
原創
2192 人瀏覽過

1.冒泡排序演算法
#過程:

#1.遍歷整個數組,每兩兩相鄰的元素進行比較,如$ a[$i]>$a[$i 1]則互換位置,每次比較消除一個逆序。
2.每一次循環後,下次再需要循環的次數減少1。

<?php
// 冒泡排序
$arr = createarr(20);
printarr($arr);
popsort($arr);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,999));
    }
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function popsort(&$arr){
    for($i=0,$length=count($arr)-1; $i<$length; $i++){
        for($j=0; $j<$length-$i; $j++){
            if($arr[$j]>$arr[$j+1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }
    }    
}
?>
登入後複製

2.二分法插入排序

過程:
#1.首先,原始數組是一個有序序列,$low=0 $high=count($arr)-1。
2.將要插入的數與數組中間位置的元素進行比較,
如果比中間元素大,則$low=$mid 1作為下一次判斷的數組開頭。
如果比中間元素小,則$high=$mid-1作為下一次判斷的陣列結尾。
3.直到$low>$high結束,$low就是新元素插入的位置。
4.將陣列中從$low開始的元素全部向後移動一位,之後在$low位置插入新元素。

<?php
// 二分法插入排序
$arr = createarr(20);
$key = mt_rand(0,99);
printarr($arr);
echo &#39;key=&#39;.$key.&#39;<br>&#39;;
binsort($arr, $key);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,99));
    }
    sort($arr); // 有序序列
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function binsort(&$arr, $key){
    $low = 0;
    $high = count($arr)-1;
    while($low<=$high){
        $m = $low + (int)(($high-$low)/2);
        $mkey = $arr[$m];
        if($key>=$mkey){
            $low = $m + 1;
        }else{
            $high = $m - 1;
        }
    }
    // 移动插入位置之后的元素,插入新元素
    for($i=count($arr)-1; $i>=$low; $i--){
        $arr[$i+1] = $arr[$i];
    }
    $arr[$low] = $key;
}
?>
登入後複製

3.快速排序
過程:

1. 在陣列中找一個元素當key,一般取數組第一個元素作為key 
2. i=0, j=數組長度-1 
3. j-- 當arr[j]4. i 當arr[i]>key, arr[i]與arr[j]交換位置 
5. 重複3,4 直到i==j 完成。 
6. 將key分隔的左右兩組元素再分別執行 1,2,3,4,5 (遞歸)。

<?php
// 快速排序
$arr = createarr(20);
printarr($arr);
quicksort($arr, 0, count($arr)-1);
printarr($arr);
function createarr($num=10){
    $arr = array();
    for($i=0; $i<$num; $i++){
        array_push($arr, mt_rand(0,999));
    }
    return $arr;
}
function printarr($arr){
    echo &#39;arr:&#39;.implode(&#39;,&#39;, $arr).&#39;<br>&#39;;
}
function quicksort(&$arr, $low, $high){
    if($low>=$high){
        return ;
    }
    $key = $arr[$low];
    $i = $low;
    $j = $high;
    $flag = 1;
    while($i!=$j){
        switch($flag){
            case 0:
                if($arr[$i]>$key){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flag = 1;
                }else{
                    $i++;
                }
                break;
            case 1:
                if($arr[$j]<$key){
                    $tmp = $arr[$i];
                    $arr[$i] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flag = 0;
                }else{
                    $j--;
                }
                break;
        }
    }
    quicksort($arr, $low, $i-1);
    quicksort($arr, $i+1, $high);
}
?>
登入後複製

  本篇文章解說了於冒泡,二分法插入,快速排序演算法,更多相關內容請關注php中文網。

相關推薦:

如何透過php 過濾html標記屬性類別

如何使用php 取代敏感字串的相關動作

關於PHP 遍歷資料夾及檔案類別及處理類別

#

以上是關於冒泡,二分法插入,快速排序演算法的介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章!

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