PHP: Алгоритм сортировка выбором
Сортировка массива с помощью алгоритма «Сортировка выбором».
В каждой итерации минимальное значение массива извлекается и добавляется в новый массив.
Сложность: O(n log n)
function findMin( $list ) { $minIndex = 0; $min = $list[ $minIndex ]; $size = sizeof( $list ); for( $i = 1; $i < $size; $i++ ) { if( $list[ $i ] < $min ) { $minIndex = $i; $min = $list[ $minIndex ]; } } return $minIndex; } function selectionSort( $list ) { $result = []; foreach( $list as $val ) { $minIndex = findMin( $list ); array_push( $result, $list[ $minIndex ] ); array_splice( $list, $minIndex, 1 ); } return $result; } $sampleList = [ 23, 42, 8, 4, 15, 16 ]; echo '<pre>', var_dump( findMin( $sampleList ) ) ,'</pre>'; // > 3 echo '<pre>', var_dump( selectionSort( $sampleList ) ) ,'</pre>'; // > array(6) { // > [0]=> // > int(4) // > [1]=> // > int(8) // > [2]=> // > int(15) // > [3]=> // > int(16) // > [4]=> // > int(23) // > [5]=> // > int(42) // > }
Комментарии