PHP – 选择排序 – 老迟笔记

一、概述

1、基本原理

　　对于给定的一组记录，经过第一轮比较后，得到最小的记录，然后将该记录与第一个记录位置进行交换。

　　接着对不包括第一个记录以外的其他记录进行第二轮比较，得到最小的记录并与第二个记录进行位置交换。

重复该过程，直到进行比较的记录只有一个为止。

二、PHP 代码实现

<?php
declare(strict_types = 1);

class TestCase
{
    /**
     * 选择排序
     *
     * @param array $array
     * @return array
     */
    public function sortArray(array $array) : array
    {
        $arrayLen = count($array);
        for ($i = 0; $i < $arrayLen - 1; $i++) {
            // 先假设最小值的键为$i
            $tmpMinKey = $i;
            for ($k = $i + 1; $k < $arrayLen; $k++) {
                if ($array[$tmpMinKey] > $array[$k]) {
                    $tmpMinKey = $k;
                }
            }
            // 如果最小值的位置与当前假设的位置不同，则互换位置
            if ($tmpMinKey != $i) {
                $tmp = $array[$tmpMinKey];
                $array[$tmpMinKey] = $array[$i];
                $array[$i] = $tmp;
            }
        }
        return $array;
    }

}

// 需要排序数组
$arr = [20, 19, 15, 36, 22, 3, 77, 95, 64, 15, 24, 36];
$arrObject = new TestCase();
// 执行排序
$arr = $arrObject->sortArray($arr);
// 输出结果
foreach ($arr as $v) {
    echo $v . ' ';
}

// 结果
3 15 15 19 20 22 24 36 36 64 77 95

三、算法性能分析

最好情况：T(n) = O(n²)

最差情况：T(n) = O(n²)

平均情况：T(n) = O(n²)

打赏赞