Реализация Bubble-сортировки в PHP?

Мне нужно сделать алгоритм сортировки пузырьков в PHP.

Я хочу знать, есть ли у кого-нибудь хорошие примеры, которые я могу использовать, или библиотеку с открытым исходным кодом, которая может это сделать.

У меня есть несколько пробелов в наборе (массиве), я хочу заполнить эти пробелы объектом (человеком), поэтому никакое пространство не может иметь мужчину и женщину, поэтому я пытаюсь выяснить тип пузыря алгоритм.

Мой план состоит в том, чтобы заполнить любое из доступных пространств независимо от пола, и после этого сортировать их отдельно.

Спасибо.

Ответ 1

Использование сортировки пузырьков - очень плохая идея. Он имеет сложность 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');

Ответ 2

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);

Ответ 3


$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";

Ответ 4

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;
}

Ответ 5

Может быть, кто-то найдет полезной мою версию 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]);         
}

Я получил идею свопа (используя список) из комментария.

Ответ 6

    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);

Ответ 7

Улучшена сортировка пузырьков:

$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;
    }