【PHP面接】面接で必ず聞かれる2つの簡単なソートアルゴリズム「バブルソート」と「クイックソート」について解説

little bottle

リリース： 2023-04-05 22:08:01

転載

2444 人が閲覧しました

通常、面接に臨むとき、面接の質問に答えるのに問題はありません。 PHP 開発者は、行っているプロジェクトに精通していることに加えて、基本的なアルゴリズムを理解する必要もあります。 PHP の面接でよく聞かれるアルゴリズム、バブルソートとクイックソートについて共有しましょう。

バブルソート: 1 対 1 比較ソート

基本的な考え方:

対象となる要素シーケンスを繰り返し訪問します。 sorted では、隣接する 2 つの要素を順番に比較し、順序 (大きいものから小さいものへなど) が間違っている場合はそれらを入れ替えます。要素を訪問する作業は、隣接する要素を交換する必要がなくなるまで繰り返されます。これは、要素がソートされたことを意味します。

イラスト:

1. 初回: 配列の最初の要素を保持して、開始します。 2 番目の要素からそれぞれ比較します。前の要素が後の要素より大きい場合は、2 つの要素を交換して、より大きい値を取得します。配列要素の最後まで後方比較を続けてバブリングを実現します (バブル 1 回、最大値)現在の「残りの」配列の値が取得され、配列の「最後」に配置されます)

2. 2 回目以降、比較は引き続き最初の要素から開始されますが、配列のみが比較されます。長さは -1 桁で、毎回の比較数は -1

3 です。最終的に比較する数値がなくなるまで比較を繰り返します

コード:

$arr = array(3,2,6,0,1,4,7);
        //因为排序需要每次将一个元素与数组的其他元素进行比较，所以需要两层循环来控制
        //外层循环控制冒泡次数
        //内存循环比较每次的大小，得到每次的最大值（泡）
 
        for($i = 0,$length = count($arr);$i < $length;$i++){
        
                 //内存循环
                 for($j = 0;$j < ($length - $i - 1);$j++){
                         //拿着j变量所对应的数组元素，与后面的元素进行比较
                         if($arr[$j] > $arr[$j + 1]){
                                  //交换位置
                                  $temp              = $arr[$j];
                                  $arr[$j]           = $arr[$j+1];
                                  $arr[$j+1]         = $temp;
                         }
                 }
        }

ログイン後にコピー

概要:

バブルソートの最適な時間計算量は O(n) です。これは最適なアルゴリズムではありませんが、よく遭遇するものであり、面接でも質問されます。したがって、私たちは基本原則を理解し、それを理解し、書くことができる必要があります。

#クイックソート: スペースを時間と交換します

基本的な考え方 :

ソート対象のデータを 1 回のソートで 2 つの独立した部分に分割し、一方の部分のすべてのデータがもう一方の部分のすべてのデータよりも小さい場合、この方法を使用して 2 つの部分を分離します。クイックソートでは、ソートプロセス全体を再帰的に実行できるため、データ全体が順序付けられたシーケンスになります。

図:

標準として、現在の配列内の任意の要素を検索し、2 つの新しい空の配列を作成し、全体を走査します。配列要素の場合、トラバースされた要素が現在の要素より小さい場合は、左側の配列に入れます。大きい場合は、別の配列に入れます。

再帰的アイデア

1. 再帰ポイント: 2 つの場合配列の要素が 1 より大きい場合、再度分解する必要があります

2. 再帰的終了: 配列要素が 1

コード:

//待排序数组
        $arr = array(5,3,8,2,6,4,7);
        //函数实现快速排序
        function quick_sort($arr){
                 //判断参数是否是一个数组
                 if(!is_array($arr)) return false;
 
                 //递归出口：数组长度为1就直接返回数组
                 $length = count($arr);
                 if($length <= 1) return $arr;

                 //数组元素有多个
                 $left = $right = array();
                 //使用for循环进行遍历，把第一个元素当做比较的对象
                 for($i = 1;$i < $length;$i++){
                         //判断当前元素值的大小
                         if($arr[$i] < $arr[0]){
                                  //当前元素小于标准元素，放到左边数组
                                  $left[] = $arr[$i];
                         }else{
                                  $right[] = $arr[$i];
                         }
                 }
                 //递归调用
                 $left = quick_sort($left);
                 $right = quick_sort($right);
 
                 //将所有的结果合并
                 return array_merge($left,array($arr[0]),$right);
        }

ログイン後にコピー

になったとき

概要:

クイックソートは、一般的な並べ替え方法の中で最も高速な並べ替え方法であり、再帰に基づいており、時間に対してスペースを使用します。一般的な面接では、基本原則を知ることが求められます。

[関連チュートリアル:

PHP ビデオチュートリアル ]

以上が【PHP面接】面接で必ず聞かれる2つの簡単なソートアルゴリズム「バブルソート」と「クイックソート」について解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。