ホームページ > 記事 > バックエンド開発 > バブリング、バイナリ挿入、クイックソートアルゴリズムの概要

バブリング、バイナリ挿入、クイックソートアルゴリズムの概要

jackloveオリジナル: 2018-06-11 09:47:502186ブラウズ

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 から始まるすべての要素を 1 つ後ろに移動し、$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. 通常は配列内の要素を検索します。配列の最初の要素はキー
2 として使用されます。i=0、j=配列の長さ-1
3。 j-- arr[j]4. i arr[i]>key の場合、arr[i] と arr[j] の位置を交換します
5。i==j になるまで 3、4 を繰り返します。
6. キーで区切られた左右の要素セットに対して 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 中国語 Web サイトを参照してください。

バブリング、バイナリ挿入、クイック ソート アルゴリズムの概要

関連記事

バブリング、バイナリ挿入、クイックソートアルゴリズムの概要