PHP - Bubble Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

<?php
function bubble(array &$A, int $lo, int $hi) {
  $last = $lo; // 记录最后一组逆序对位置

  while (++$lo < $hi) { // 遍历 [$lo, $hi) 内所有元素

    if ($A[$lo - 1] > $A[$lo]) { // 若逆序

      $last = $lo; // 记录逆序对位置

      // 交换位置
      $temp = $A[$lo - 1];
      $A[$lo - 1] = $A[$lo];
      $A[$lo] = $temp;

    }

  }

  // 返回最后一组逆序对位置，[$lo, $last) 不一定有序，[$last, $hi) 必然有序
  return $last;
}

function bubbleSort(array &$A, int $lo, int $hi) {
    // 将 $last 赋值给 $hi，则接下来只排序 [$lo, $last) 内的元素
    while ($lo < ($hi = bubble($A, $lo, $hi)));
}

$A = [100, 5, 25, 29, 11, 65, 33, 22, 68, 19];

bubbleSort($A, 0, count($A));

for ($i = 0; $i < count($A); $i++) {
  echo "{$A[$i]} ";
}