【アルゴリズム】PHP実現経典並べ替えアルゴリズム一

一、泡立ちソート
原理の概要
バブルソート(Bubble Sort)は単純で一般的なソートアルゴリズムである.並べ替えが必要な数列を巡って、2つの数値の大きさを比較し、順序が間違っている2つの数を位置を交換し、並べ替えを完了します.上記の操作を繰り返し、交換可能な数がなくなるまで、数列全体のソートの目的を達成します.
コードの例

function bubbleSort(array $arr) : array
    {
        $len = count($arr);

        for ($i=0; $i $arr[$j+1]) {
                    $tmp = $arr[$j];
                    $arr[$j] = $arr[$j+1];
                    $arr[$j+1] = $tmp;
                }
            }
        }

        return $arr;
    }

二、ソートの選択
原理の概要
まず、ソートされていない数の列に最小要素を見つけ、ソートシーケンスの開始位置に保存します.
さらに、残りのソートされていない要素から最小要素を探し続け、ソートされたシーケンスの最後に配置します.
すべての要素がソートされるまで、手順2を繰り返します.
どの数列でも,選択ソートを用いて時間複雑度O(n²)
コード実装

function selectionSort(array $arr) : array
    {
        $len = count($arr);

        for ($i = 0; $i < $len - 1; $i++) {
            $min_index = $i;
            for ($j = $i + 1; $j < $len; $j++) {
                if ($arr[$j] < $arr[$min_index]) {
                    $min_index = $j;
                }
            }
            $temp = $arr[$i];
            $arr[$i] = $arr[$min_index];
            $arr[$min_index] = $temp;
        }

        return $arr;
    }

三、挿入順序
原理の概要
挿入ソートは、地主と戦うときに手札の順序を整理する操作と同様に、ソートされていない数列を後ろから前へ、ソートされた数列の中で適切な位置を見つけて挿入し、数列全体のソートが完了するまで挿入します.
コードの例

function insertSort(array $arr): array
    {
        $len = count($arr);

        for ($i = 1; $i < $len; $i++) {
            $pre_index = $i - 1;
            $current = $arr[$i];
            while ($pre_index >= 0 && $arr[$pre_index] > $current) {
                $arr[$pre_index + 1] = $arr[$pre_index];
                $pre_index--;
            }

            $arr[$pre_index + 1] = $current;
        }

        return $arr;
    }

四、ヒルソート
原理の概要
ヒルソートは、減算インクリメンタルソートアルゴリズムとも呼ばれ、挿入ソートに基づくより高速なソートアルゴリズムである.ヒルソートの考え方は,配列中の任意の間隔hの要素が秩序化されていることである.1つのh有序数配列は、h個の互いに独立した秩序配列が織り込まれ、構成された1つの配列である.これらのサブ配列に直接挿入ソートを行い、
コードの例

function shellSort(array $arr): array
    {
        $len = count($arr);
        $tmp = 0;
        $gap = 1;
        while ($gap < $len / 3) {
            $gap = $gap * 3 + 1;
        }
        for (; $gap > 0; $gap = floor($gap / 3)) {
            for ($i = $gap; $i < $len; $i++) {
                $tmp = $arr[$i];
                for ($j = $i - $gap; $j >= 0 && $arr[$j] > $tmp; $j -= $gap) {
                    $arr[$j+$gap] = $arr[$j];
                }
                $arr[$j+$gap] = $tmp;
            }
        }

        return $arr;
    }

五、集計ソート
原理の概要
集計ソートは、その名の通り1つの配列をソートし、まずそれを再帰的に2つの半分に分けてソートし、結果を集計することができます.時間の複雑さはNlogN
コードの例

function mergeSort(array $arr, $len = null): array
    {
        if ($len === null) {
            $len = count($arr);
        }

        if ($len <= 1) {
            return $arr;
        }

        //if len > 1 ,need cut into 2 part
        $mid = intdiv($len, 2); //php7   ,        intval($len/2)

        $left = array_slice($arr, 0, $mid);
        $right = array_slice($arr, $mid);

        $left = $this->mergeSort($left);
        $right = $this->mergeSort($right);

        $len_left = count($left);
        $len_right = count($right);
        $i = 0;
        $j = 0;
        $result = [];

        while ($i < $len_left || $j < $len_right) {
            if ($j == $len_right || ($left[$i] <= $right[$j] && $i < $len_left)) {
                $result[] = $left[$i];
                ++$i;
                continue;
            }

            if ($i == $len_left || $left[$i] > $right[$j]) {
                $result[] = $right[$j];
                ++$j;
                continue;
            }
        }

        return $result;
   }