phpでいくつかの一般的なソートアルゴリズムを実現する

26947 ワード
php
一、泡立ちソート泡立ちソートは最も簡単に理解できるが、時間的複雑度(O(n^2))も最大の1つであり、実現コードは以下の通りである.
function bubbleSort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len; $i++) {
        //   i     ，           ，         
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$i] > $arr[$j]) {
                $t = $arr[$i];
                $arr[$i] = $arr[$j];
                $arr[$j] = $t;
            }
        }
    }
    return $arr;
}

$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(bubbleSort($arr));

二、選択ソート選択ソートも理解が簡単で、時間の複雑さもO(n^2)であり、実現コードは以下の通りである.
function selectSort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len; $i++) {
        $minIndex = $i;
        //   i              
        for ($j = $i + 1; $j < $len; $j++) {
            if ($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        if ($minIndex != $i) {
            $t = $arr[$i];
            $arr[$i] = $arr[$minIndex];
            $arr[$minIndex] = $t;
        }
    }
    return $arr;
}
$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(selectSort($arr));

三、挿入ソート感覚挿入ソートは泡ソートと少し似ており、時間の複雑さもO(n^2)であり、実現コードは以下の通りである.
function insertSort($arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        if ($arr[$i] < $arr[$i - 1]) {
            $t = $arr[$i];
            $j = $i - 1;
            //              ，    
            while ($j >= 0 && $t < $arr[$j]) {
                $arr[$j + 1] = $arr[$j];
                $j--;
            }
            $arr[$j + 1] = $t;
        }
    }
    return $arr;
}

$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(insertSort($arr));

四、ヒルソートヒルソートは実はソートを挿入する最適化版であることを理解することができ、その効率は増分に関係し、増分はいくら取るか、異なる配列によって異なるので、ヒルソートは不安定なソートアルゴリズムであり、その時間複雑度はO(nlogn)からO(n^2)の間であり、実現コードは以下の通りである.
function shellSort($arr) {
    $len = count($arr);
    $stepSize = floor($len / 2);
    while ($stepSize >= 1) {
        for ($i = $stepSize; $i < $len; $i++) {
            if ($arr[$i] < $arr[$i - $stepSize]) {
                $t = $arr[$i];
                $j = $i - $stepSize;
                while ($j >= 0 && $t < $arr[$j]) {
                    $arr[$j + $stepSize] = $arr[$j];
                    $j -= $stepSize;
                }
                $arr[$j + $stepSize] = $t;
            }
        }
        //     ，       
        $stepSize = floor($stepSize / 2);
    }
    return $arr;
}

$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(shellSort($arr));

五、スタック並べ替えスタック並べ替えは効率的な並べ替えアルゴリズムであり、その時間複雑度はO(nlogn)である.原理は、配列を最大スタックに変換し、最初の要素をi番目の要素と交換し、残りのi-1要素を最大スタックに変換し、最初の要素をi-1番目の要素と交換することです.実装コードは次のとおりです.
function heapSort($arr) {
    $len = count($arr);
    //       
    for ($i = floor(($len - 1) / 2); $i >= 0; $i--) {
        $s = $i;
        $childIndex = $s * 2 + 1;
        while ($childIndex < $len) {
            //   、  、    ，     
            if ($childIndex + 1 < $len && $arr[$childIndex] < $arr[$childIndex + 1]) $childIndex++;
            if ($arr[$s] < $arr[$childIndex]) {
                $t = $arr[$s];
                $arr[$s] = $arr[$childIndex];
                $arr[$childIndex] = $t;
                $s = $childIndex;
                $childIndex = $childIndex * 2 + 1;
            } else {
                break;
            }
        }
    }
    //            
    for ($i = $len - 1; $i > 0; $i--) {
        $t = $arr[$i];
        $arr[$i] = $arr[0];
        $arr[0] = $t;
        //        
        $s = 0;
        $childIndex = 1;
        while ($childIndex < $i) {
            //   、  、    ，     
            if ($childIndex + 1 < $i && $arr[$childIndex] < $arr[$childIndex + 1]) $childIndex++;
            if ($arr[$s] < $arr[$childIndex]) {
                $t = $arr[$s];
                $arr[$s] = $arr[$childIndex];
                $arr[$childIndex] = $t;
                $s = $childIndex;
                $childIndex = $childIndex * 2 + 1;
            } else {
                break;
            }
        }
    }
    return $arr;
}

$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(heapSort($arr));

六、高速並べ替え高速並べ替えも効率的な並べ替えアルゴリズムであり、その時間複雑度もO(nlogn)である.原理は、データム要素を選択し、配列内のこの要素より小さい要素をデータム要素の左側に、それより大きい要素をデータム要素の右側に配置することです.そしてこの両方に対して同じ操作を続けます.コードは次のとおりです.
function quickSort($arr) {
    $len = count($arr);
    quickSortRecursion($arr, 0, $len - 1);
    return $arr;
}

function quickSortRecursion(&$arr, $begin, $end) {
    if ($begin < $end) {
        $left = $begin;
        $right = $end;
        $temp = $arr[$begin];   // $temp     
        //    $temp     $temp  ，        
        while ($left < $right) {
            while ($left < $right && $arr[$right] >= $temp) $right--;
            if ($left < $right) {
                $arr[$left++] = $arr[$right];
            }
            while ($left < $right && $arr[$left] <= $temp) $left++;
            if ($left < $right) {
                $arr[$right--] = $arr[$left];
            }
        }
        $arr[$left] = $temp;
        //         ，       
        quickSortRecursion($arr, $begin, $left - 1);
        quickSortRecursion($arr, $left + 1, $end);
    }
    return $arr;
}

$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(quickSort($arr));

七、集計ソート集計ソートの時間的複雑度もO(nlogn)である.原理は:2つの並べ替えられた配列に対して、それぞれこの2つの配列を遍歴して、小さい要素を取得して新しい配列に挿入して、それでは、このように新しい配列も並べ替えられます.コードは次のとおりです.
function mergeSort($arr) {
    $len = count($arr);
    $arr = mergeSortRecursion($arr, 0, $len - 1);
    return $arr;
}

function mergeSortRecursion(&$arr, $begin, $end) {
    if ($begin < $end) {
        $mid = floor(($begin + $end) / 2);
        //        ，         ，         ，       
        mergeSortRecursion($arr, $begin, $mid);
        mergeSortRecursion($arr, $mid + 1, $end);
        $i = $begin;
        $j = $mid + 1;
        $k = 0;
        $temp = array();
        //       ，      ，                  
        while ($i <= $mid && $j <= $end) {
            if ($arr[$i] < $arr[$j]) {
                $temp[$k++] = $arr[$i++];
            } else {
                $temp[$k++] = $arr[$j++];
            }
        }
        while ($i <= $mid) {
            $temp[$k++] = $arr[$i++];
        }
        while ($j <= $end) {
            $temp[$k++] = $arr[$j++];
        }
        for ($i = 0; $i < $k; $i++) {
            $arr[$i + $begin] = $temp[$i];
        }
    }
    return $arr;
}

$arr = [3,1,13,5,7,11,2,4,14,9,15,6,12,10,8];
print_r(mergeSort($arr));
困った時に活躍してくれたコマンドプロンプトのコマンド
WeChatウィジェットでwatchを使用して傍受する