PHP: Алгоритм быстрая сортировка
Сортировка массива с помощью алгоритма «Быстрая сортировка».
В каждой итерации выбираем опорное значение и разделяем массив на значения больше и меньше опорного значения.
Сложность: O(n log n)
// тестовый массив $data = [ 8, 99, 1, 3, 10, 199, 2, 8, 3, 99, 3 ];
Решение с удалением повторяющихся значений:
function qsort( $arr ) { if( sizeof( $arr ) < 2 ) { return $arr; } else { $baseIndex = 0; // в качестве опорного значения можно взять любое из массива // $baseIndex = rand( 0, sizeof( $arr ) - 1 ); $base = $arr[ $baseIndex ]; $lt = []; $gt = []; $mid = [ $base ]; foreach( $arr as $index => $value ) { if( $value > $base ) { array_push( $gt, $value ); } else if( $value < $base ) { array_push( $lt, $value ); } } return array_merge( qsort( $lt ), $mid, qsort( $gt ) ); } } echo '<pre>', var_dump( qsort( $data ) ) ,'</pre>'; // > array(7) { // > [0]=> // > int(1) // > [1]=> // > int(2) // > [2]=> // > int(3) // > [3]=> // > int(8) // > [4]=> // > int(10) // > [5]=> // > int(99) // > [6]=> // > int(199) // > }}
Решение с сохранением повторяющихся значений:
function qsortWithRepeats( $arr ) { if( sizeof( $arr ) < 2 ) { return $arr; } else { $baseIndex = 0; $base = $arr[ $baseIndex ]; $lt = []; $gt = []; $mid = [ $base ]; foreach( $arr as $index => $value ) { if( $value > $base ) { array_push( $gt, $value ); } else if( $value < $base ) { array_push( $lt, $value ); } else if( $index != $baseIndex AND $value == $base ) { array_push( $mid, $value ); } } return array_merge( qsortWithRepeats( $lt ), $mid, qsortWithRepeats( $gt ) ); } } echo '<pre>', var_dump( qsortWithRepeats( $data ) ) ,'</pre>'; // > array(11) { // > [0]=> // > int(1) // > [1]=> // > int(2) // > [2]=> // > int(3) // > [3]=> // > int(3) // > [4]=> // > int(3) // > [5]=> // > int(8) // > [6]=> // > int(8) // > [7]=> // > int(10) // > [8]=> // > int(99) // > [9]=> // > int(99) // > [10]=> // > int(199) // > }
Комментарии