ホームページ  >  記事  >  バックエンド開発  >  PHPソートアルゴリズム選択ソート

PHPソートアルゴリズム選択ソート

藏色散人
藏色散人転載
2019-12-09 14:32:472877ブラウズ

選択ソート

● 選択ソートも内部ソートです

#● ソートのアイデア:

まずランダムに数字を選択します。並べ替える配列内の要素を選択し、それを配列の他の要素と比較します。次に、位置を比較して交換して最小値または最大値を取得し、残りの配列内の数値を選択して配列の残りの要素と比較し、最後に 2 番目の最小値または最大値の要素を取得します。など

# 概略図:

選択ソートには配列の合計サイズがあります - ソートの 1 ラウンド。ソートの各ラウンドは別のサイクルです。最初に現在の配列を想定します。は最小数です, 次にそれを次の要素と順番に比較します. 現在の数よりも小さい数があることが判明した場合, 最小数を再決定し, 添え字を取得します. 配列の最後まで走査すると,このラウンドの最小数と添字を取得し、交換

1. ソートする配列 [3, 1, 15, 5, 20]

2 があるとします。要素をランダムに選択し、最初の要素が最小の要素であると仮定し、3 を配列の残りの要素と比較します。最初の並べ替えラウンドの後、最小の要素 1

<?php
$arr = [3, 1, 15, 5, 20];
$count = count($arr);
//假设最小的元素就是第一个元素
$minIndex = 0;
$min = $arr[0];
for ($j = $minIndex + 1; $j < $count; $j++) {
    if ($min > $arr[$j]) { //假定的最小值大于后面的值,重置最小值
        $min = $arr[$j];
        $minIndex = $j;
    }
}
$arr[$minIndex] = $arr[0];
$arr[0] = $min;

3 が得られます。仮説の最小値をもう一度計算し、次の要素と比較して 2 番目の最小値を取得します


<?php
$arr = [1, 3, 15, 5, 20];
$count = count($arr);
//假设最小的元素就是第二个元素
$minIndex = 1;//假设的最小元素的下表
$min = $arr[1];//假定最小元素的值
for ($j = $minIndex + 1; $j < $count; $j++) {
    if ($min > $arr[$j]) { //假定的最小值大于后面的值,重置最小值
        $min = $arr[$j];
        $minIndex = $j;
    }
}
if ($minIndex != 1) {
    $arr[$minIndex] = $arr[1];//假定的最小元素不是最小元素,那么把后面的最小元素和假定的最小元素做交换
    $arr[1] = $min;//元素下标交换
}

4。同様に、二重の for ループを使用して、次のように選択ソート アルゴリズムを取得できます:

  public static function sortSelect(array $arr) :array
    {
        if (!is_array($arr)) {
            return [&#39;message&#39; => &#39;$arr不是一个数组&#39;];
        }
        $count = count($arr);
        if ($count <= 1) {
            return $arr;
        }
        for ($i = 0; $i < $count; $i++) {
            $minIndex = $i;
            $min = $arr[$i];
            for ($j = $i + 1; $j < $count; $j++) {
                if ($min > $arr[$j]) {//选择的假定最小元素大于后面的元素
                    $min = $arr[$j];//把后面的最小元素赋值给假定的最小元素
                    $minIndex = $j;//把后面最小元素的坐标赋值给假定的最小元素
                }
            }
            if ($minIndex != $i) {//如果在这个位置,一开始的假定最小元素的坐标被替换了,说明假定最小元素不是最小元素,那么发生交换
                $arr[$minIndex] = $arr[$i];//交换最小元素,把最小元素和假定元素做交换
                $arr[$i] = $min;
            }
        }
        return $arr;
    }

# 完全なコードは次のとおりです:

<?php
class SelectSort
{
    public static function select(array $arr):array
    {
        $count = count($arr);
        //假设最小的元素就是第二个元素
        $minIndex = 0;//假设的最小元素的下表
        $min = $arr[0];//假定最小元素的值
        for ($j = $minIndex + 1; $j < $count; $j++) {
            if ($min > $arr[$j]) { //假定的最小值大于后面的值,重置最小值
                $min = $arr[$j];
                $minIndex = $j;
            }
        }
        if ($minIndex != 0) {
            $arr[$minIndex] = $arr[0];//假定的最小元素不是最小元素,那么把后面的最小元素和假定的最小元素做交换
            $arr[0] = $min;//元素下标交换
        }
        var_dump($arr);
        $minIndex = 1;//假设的最小元素的下表
        $min = $arr[1];//假定最小元素的值
        for ($j = $minIndex + 1; $j < $count; $j++) {
            if ($min > $arr[$j]) { //假定的最小值大于后面的值,重置最小值
                $min = $arr[$j];
                $minIndex = $j;
            }
        }
        if ($minIndex != 1) {
            $arr[$minIndex] = $arr[1];//假定的最小元素不是最小元素,那么把后面的最小元素和假定的最小元素做交换
            $arr[1] = $min;//元素下标交换
        }
        var_dump($arr);
        $minIndex = 2;//假设的最小元素的下表
        $min = $arr[2];//假定最小元素的值
        for ($j = $minIndex + 1; $j < $count; $j++) {
            if ($min > $arr[$j]) { //假定的最小值大于后面的值,重置最小值
                $min = $arr[$j];
                $minIndex = $j;
            }
        }
        if ($minIndex != 2) {
            $arr[$minIndex] = $arr[2];//假定的最小元素不是最小元素,那么把后面的最小元素和假定的最小元素做交换
            $arr[2] = $min;//元素下标交换
        }
        var_dump($arr);
        return $arr;
    }
    public static function sortSelect(array $arr) :array
    {
        if (!is_array($arr)) {
            return [&#39;message&#39; => &#39;$arr不是一个数组&#39;];
        }
        $count = count($arr);
        if ($count <= 1) {
            return $arr;
        }
        for ($i = 0; $i < $count - 1; $i++) {
            $minIndex = $i;
            $min = $arr[$i];
            for ($j = $i + 1; $j < $count; $j++) {
                if ($min > $arr[$j]) {//选择的假定最小元素大于后面的元素
                    $min = $arr[$j];//把后面的最小元素赋值给假定的最小元素
                    $minIndex = $j;//把后面最小元素的坐标赋值给假定的最小元素
                }
            }
            if ($minIndex != $i) {//如果在这个位置,一开始的假定最小元素的坐标被替换了,说明假定最小元素不是最小元素,那么发生交换
                $arr[$minIndex] = $arr[$i];//交换最小元素,把最小元素和假定元素做交换
                $arr[$i] = $min;
            }
        }
        return $arr;
    }
}
$arr = [3, 1, 15, 5, 20];
var_dump(SelectSort::sortSelect($arr));

以上がPHPソートアルゴリズム選択ソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事はlearnku.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。