使用冒泡排序对数组进行排序

Question

我正在尝试创建一种算法来显示冒泡排序的每个步骤，一次对一个数字进行排序。我能够在第一个索引处对数字进行排序，但我需要弄清楚如何对所有数字进行排序。

$x = array (9,7,5,3,0);

$count = count($x);
for($i = 0; $i < $count-1; $i++ ) {
    $temp = $x[$i+1];
    $x[$i+1] = $x[$i];
    $x[$i] = $temp;
    echo '<pre>';
    print_r($x);
}

我当前的输出是：

Array
(
    [0] => 7
    [1] => 9
    [2] => 5
    [3] => 3
    [4] => 0
)
Array
(
    [0] => 7
    [1] => 5
    [2] => 9
    [3] => 3
    [4] => 0
)
Array
(
    [0] => 7
    [1] => 5
    [2] => 3
    [3] => 9
    [4] => 0
)
Array
(
    [0] => 7
    [1] => 5
    [2] => 3
    [3] => 0
    [4] => 9
)

从这里我需要继续对剩余的数字进行排序。对于 7，输出应该是

然后是 3

然后对于 0，所有 4 行都应该相同，例如

[分配的问题。][1]

Answer 1

两期：

您应该仅在顺序不正确时交换值
您需要一个外循环来重复这个内循环，类似于正确的冒泡排序算法。

您的代码可以像下面这样修改，以便生成所需的输出：

$x = array (9,7,5,3,0);

$count = count($x) - 1;
for($times = 0; $times < $count; $times++) {
    for($i = 0; $i < $count; $i++ ) {
        $temp = $x[$i+1];
        if ($temp < $x[$i]) {
            $x[$i+1] = $x[$i];
            $x[$i] = $temp;
        }
        echo implode(" ", $x) . "\n";
    }
    echo "\n";
}

请注意，正确的冒泡排序算法会执行更少的迭代。

Answer 2

冒泡排序基本上被简化为 min() + shift（或有时 swap）发生 N 次的操作。所以这是一个 O(n^2) 算法。

由于这是出于学习目的，我将尽可能详细。

function getMin(Array &$array): Int {
    $min = reset($array);
    $minKey = null;

    // Find the minimum value
    foreach($array as $k => $n) {
        if ($n < $min) {
            $min = $n;
            $minKey = $k;
        }
    }

    // remove the minimum value from the array
    $array[$k] = null;
    $array = array_filter($array, function ($v) { return $v !== null; });

    return $min;
}

$array = [9,7,5,3,0];

foreach ($array as $n => $value) {
    // Find the min value in the array from Nth index onward
    $min = getMin($array); // get the smallest value in the array and remove it.
    $sorted[] = $min; // push it on to the new array
}

var_dump($sorted);

这给了你预期的结果：

array(5) {
  [0]=>
  int(0)
  [1]=>
  int(3)
  [2]=>
  int(5)
  [3]=>
  int(7)
  [4]=>
  int(9)
}

当然，这不是您想要实现冒泡排序的方式，因为它有点迂回。同样，这是出于教育目的。您可以在每一步修改 $array 时检查它，在构建新的 $sorted 时检查它。通常，您只需交换 min/max 值并使用相同的数组（跟踪键以重新扫描数组）。

像这样...

// Unsorted $array
$array = [9,7,5,3,0];

// Sort the array
for ($lastKey = $i = 0, $len = count($array); $i < $len; $i++) {
    // Scan for minimum value
    for ($minKey = $j = $lastKey, $min = $array[$minKey]; $j < $len; $j++) {
        if ($array[$j] < $min) {
            $minKey = $j;
            $min = $array[$j];
        }
    }
    // Swap the values
    $swap = $array[$lastKey];
    $array[$lastKey] = $min;
    $array[$minKey] = $swap;

    // Update the scan position
    $lastKey++;
}

var_dump($array); // Gives you [0,3,5,7,9]

Answer 3

您正在执行无条件换仓，但您实际上需要检查是否需要移动。

php 中不乏演示冒泡排序的教程。一个快速好的引导我到这个：https://www.w3resource.com/php-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-6.php 可以根据您的目的进行修改。

PHP 现在提供“array destructuring”，这意味着您在交换时不再需要使用临时保持变量。

代码：(Demo)

$x = [9,7,5,3,0];
$count = count($x) - 1;
for ($pass = 0; $pass < $count; ++$pass) {
    for ($i = 0; $i < $count; ++$i) {
        if ($x[$i] > $x[$i + 1]) {
            [$x[$i + 1], $x[$i]] = [$x[$i], $x[$i + 1]];
        }
        $results[] = implode($x);
    }
    $results[] = "\n";
}
echo implode("\n", $results);

使用冒泡排序对数组进行排序

Sorting an array with bubble sort

php

sorting

algorithm

bubble-sort