Мне нужно сделать алгоритм сортировки пузырьков в PHP.
Я хочу знать, есть ли у кого-нибудь хорошие примеры, которые я могу использовать, или библиотеку с открытым исходным кодом, которая может это сделать.
У меня есть несколько пробелов в наборе (массиве), я хочу заполнить эти пространства объектом (человеком), поэтому никакое пространство не может иметь мужчину и женщину, поэтому я пытаюсь найти алгоритм сортировки пузырьков.
Мой план состоит в том, чтобы заполнить любое из доступных мест независимо от пола, и после этого сортировать их отдельно.
Благодарю.
Использование пузырьковой сортировки – очень плохая идея. Он имеет сложность O(n^2) .
Вы должны использовать php usort , что на самом деле является реализацией сортировки слиянием и гарантированной сложностью O(n*log(n)) .
Пример кода из руководства PHP –
function cmp( $a, $b ) { if( $a->weight == $b->weight ){ return 0 ; } return ($a->weight < $b->weight) ? -1 : 1; } usort($unsortedObjectArray,'cmp');
function bubble_sort($arr) { $size = count($arr)-1; for ($i=0; $i<$size; $i++) { for ($j=0; $j<$size-$i; $j++) { $k = $j+1; if ($arr[$k] < $arr[$j]) { // Swap elements at indices: $j, $k list($arr[$j], $arr[$k]) = array($arr[$k], $arr[$j]); } } } return $arr; }
Например:
$arr = array(1,3,2,8,5,7,4,0); print("Before sorting"); print_r($arr); $arr = bubble_sort($arr); print("After sorting by using bubble sort"); print_r($arr);
$numbers = array(1,3,2,5,2); $array_size = count($numbers); echo "Numbers before sort: "; for ( $i = 0; $i < $array_size; $i++ ) echo $numbers[$i]; echo "n"; for ( $i = 0; $i < $array_size; $i++ ) { for ($j = 0; $j < $array_size; $j++ ) { if ($numbers[$i] < $numbers[$j]) { $temp = $numbers[$i]; $numbers[$i] = $numbers[$j]; $numbers[$j] = $temp; } } } echo "Numbers after sort: "; for( $i = 0; $i < $array_size; $i++ ) echo $numbers[$i]; echo "n";$numbers = array(1,3,2,5,2); $array_size = count($numbers); echo "Numbers before sort: "; for ( $i = 0; $i < $array_size; $i++ ) echo $numbers[$i]; echo "n"; for ( $i = 0; $i < $array_size; $i++ ) { for ($j = 0; $j < $array_size; $j++ ) { if ($numbers[$i] < $numbers[$j]) { $temp = $numbers[$i]; $numbers[$i] = $numbers[$j]; $numbers[$j] = $temp; } } } echo "Numbers after sort: "; for( $i = 0; $i < $array_size; $i++ ) echo $numbers[$i]; echo "n";
function bubble_sort($arr) { $n = count($arr); do { $swapped = false; for ($i = 0; $i < $n - 1; $i++) { // swap when out of order if ($arr[$i] > $arr[$i + 1]) { $temp = $arr[$i]; $arr[$i] = $arr[$i + 1]; $arr[$i + 1] = $temp; $swapped = true; } } $n--; } while ($swapped); return $arr; },function bubble_sort($arr) { $n = count($arr); do { $swapped = false; for ($i = 0; $i < $n - 1; $i++) { // swap when out of order if ($arr[$i] > $arr[$i + 1]) { $temp = $arr[$i]; $arr[$i] = $arr[$i + 1]; $arr[$i + 1] = $temp; $swapped = true; } } $n--; } while ($swapped); return $arr; }
Может быть, кто-то найдет полезной мою версию Bubble Sort:
function BubbleSort(&$L) { $rm_key = count($L); while( --$rm_key > -1 )#after this the very first time it will point to the last element for($i=0; $i<$rm_key; $i++) if( $L[$i] > $L[$i+1] ) list($L[$i],$L[$i+1]) = array($L[$i+1],$L[$i]); }
Я получил идею свопа (используя список) из комментария.
function bubbleSort(array $arr) { $n = sizeof($arr); for ($i = 1; $i < $n; $i++) { for ($j = $n - 1; $j >= $i; $j--) { if($arr[$j-1] > $arr[$j]) { $tmp = $arr[$j - 1]; $arr[$j - 1] = $arr[$j]; $arr[$j] = $tmp; } } } return $arr; } // Example: $arr = array(255,1,22,3,45,5); $result = bubbleSort($arr); print_r($result); //==================================================== //------- improved version---------------------------- //==================================================== function bubbleSortImproved(array $arr) { $n = sizeof($arr); for ($i = 1; $i < $n; $i++) { $flag = false; for ($j = $n - 1; $j >= $i; $j--) { if($arr[$j-1] > $arr[$j]) { $tmp = $arr[$j - 1]; $arr[$j - 1] = $arr[$j]; $arr[$j] = $tmp; $flag = true; } } if (!$flag) { break; } } return $arr; } // Example: $arr = array(255,1,22,3,45,5); $result = bubbleSortImproved($arr); print_r($result);
Улучшена сортировка пузырьков 🙂
$sortarr = array(3,5,15,3,2,6,7,50,1,4,5,2,100,9,3,2,6,7,13,18); echo "<pre>"; // Array to be sorted print_r($sortarr); // Sorted Array print_r(bubble_sort($sortarr)); echo "<pre>"; function bubble_sort($sortarr){ // Bubble sorting $array_count = count($sortarr); for($x = 0; $x < $array_count; $x++){ for($a = 0 ; $a < $array_count - 1 ; $a++){ if($a < $array_count ){ if($sortarr[$a] > $sortarr[$a + 1] ){ swap($sortarr, $a, $a+1); } } } } return $sortarr; } function swap(&$arr, $a, $b) { $tmp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $tmp; }