PHP排序算法详解：冒泡、选择、插入、希尔与堆排序

$arr = [3, 4, 6, 1, 7, 8, 9, 5, 10, 2];

// 冒泡排序：通过两两比较相邻元素，较大的元素向后移动，较小的元素向前移动。

$max = count($arr) - 1;

$flag = true;

for ($i = 0; $i <$max && $flag; $i++) {

$flag = false;

for ($j = $max - $i; $j > 0; $j--) {

if ($arr[$j] <$arr[$j - 1]) {

$tmp = $arr[$j - 1];

$arr[$j - 1] = $arr[$j];

$arr[$j] = $tmp;

$flag = true;

}

echo $i . '次' . PHP_EOL;

var_dump($arr) . PHP_EOL;

sleep(1);

}

}

// 选择排序：遍历数组，选择最小的元素并将其放置在当前遍历位置的开头。

for ($i = 0; $i <$max; $i++) {

$min = $arr[$i];

for ($j = $i + 1; $j <$max; $j++) {

if ($arr[$j] <$min) {

$min = $arr[$j];

$arr[$j] = $arr[$i];

$arr[$i] = $min;

}

var_dump($arr) . PHP_EOL;

}

sleep(1);

}

// 插入排序：从第二个元素开始，与前面的元素比较，如果当前元素小于前面的元素，则将前面的所有元素向后移动，为当前元素腾出空间。

$max = count($arr);

for ($i = 1; $i <$max; $i++) {

if ($arr[$i - 1] > $arr[$i]) {

$tmp = $arr[$i];

for ($j = $i - 1; $j >= 0 && $arr[$j] > $tmp; $j--) {

$arr[$j + 1] = $arr[$j];

$arr[$j] = $tmp;

}

var_dump($arr) . PHP_EOL;

sleep(1);

}

}

// 希尔排序：通过设定一定的增量，对数组进行分组，然后对每个小组进行插入排序。

public function shellSort($arr) {

$total = count($arr);

$inc = $total;

do {

$inc = ceil($inc / 2);

for ($i = $inc; $i <$total; $i++) {

if ($arr[$i - $inc] > $arr[$i]) {

$tmp = $arr[$i];

for ($j = $i - $inc; $j >= 0 && $arr[$j] > $tmp; $j -= $inc) {

$arr[$j + $inc] = $arr[$j];

$arr[$j] = $tmp;

}

var_dump($arr) . PHP_EOL;

sleep(1);

}

}

} while ($inc > 1);

return $arr;

}

// 堆排序：通过构建最大堆，将最大值移到数组末尾，再调整堆，重复此过程直到排序完成。

public function heapSort() {

$arr = [3, 4, 6, 1, 7, 8, 9, 5, 10, 2];

$total = count($arr);

// 构建初始最大堆

for ($i = $total / 2 - 1; $i >= 0; $i--) {

$this->adjustHeap($arr, $i, $total);

}

// 将最大值移到数组末尾，并调整堆

for ($j = $total - 1; $j > 0; $j--) {

$this->swap($arr, 0, $j);

$this->adjustHeap($arr, 0, $j);

}

}

public function adjustHeap(&$arr, $i, $total) {

$tmp = $arr[$i];

for ($k = $i * 2 + 1; $k <$total; $k = $k * 2 + 1) {

if ($k + 1 <$total && $arr[$k] <$arr[$k + 1]) {

$k++;

}

if ($arr[$k] > $tmp) {

$arr[$i] = $arr[$k];

$i = $k;

}

}

$arr[$i] = $tmp;

}

public function swap(&$arr, $a, $b) {

$tmp = $arr[$a];

$arr[$a] = $arr[$b];

$arr[$b] = $tmp;

var_dump($arr) . PHP_EOL;

}