常见的四种排序算法
对下面的数据进行排序
$arr = [3, 5, 2, 4, 6];
冒泡排序
- 比较相邻的两个元素。如果第一个比第二个大,就交换他们两个
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
优点:稳定
缺点:慢,每次只能移动相邻两个数据
实现:
function bubbleSort(array &$arr): void
{
$num = count($arr);
if ($num <= 1) {
return;
}
for ($i = 0; $i < $num; $i++) {
for ($j = 0; $j < $num - $i - 1; $j++) {
if ($arr[$j] < $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
}
}
}
}
/******************************/
print_r($arr);
bubbleSort($arr);
print_r($arr);
/*
输出:
Array
(
[0] => 3
[1] => 5
[2] => 2
[3] => 4
[4] => 6
)
Array
(
[0] => 6
[1] => 5
[2] => 4
[3] => 3
[4] => 2
)
*/
快速排序
- 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行
优点:极快,数据移动少.
缺点:不稳定
function quickSort(array $arr): array
{
$num = count($arr);
if ($num <= 1) {
return $arr;
}
$temp = $arr[0];
$leftArr = [];
$rightArr = [];
for ($i = 1; $i < $num; $i++) {
if ($temp < $arr[$i]) {
$leftArr[] = $arr[$i];
} else {
$rightArr[] = $arr[$i];
}
}
$leftArr = quickSort($leftArr);
$rightArr = quickSort($rightArr);
return array_merge($leftArr, [$temp], $rightArr);
}
var_dump($arr, quickSort($arr));
/*
输出:
Array
(
[0] => 3
[1] => 5
[2] => 2
[3] => 4
[4] => 6
)
Array
(
[0] => 6
[1] => 5
[2] => 4
[3] => 3
[4] => 2
)
*/
选择排序
- 在数组中,选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
优点:数据移动次数已知为(n-1)次
缺点:比较次数多
function selectSort(array &$arr): void
{
$num = count($arr);
if ($num <= 1) {
return;
}
for ($i = 0; $i < $num - 1; $i++) {
$index = $i;
for ($j = $i + 1; $j < $num; $j++) {
if ($arr[$index] > $arr[$j]) {
$index = $j;
}
if ($index != $i) {
$temp = $arr[$index];
$arr[$index] = $arr[$i];
$arr[$i] = $temp;
}
}
}
}
print_r($arr);
selectSort($arr);
print_r($arr);
/*
输出:
Array
(
[0] => 3
[1] => 5
[2] => 2
[3] => 4
[4] => 6
)
Array
(
[0] => 2
[1] => 3
[2] => 5
[3] => 4
[4] => 6
)
*/
插入排序
- 每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。
优点:稳定,快
缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候
function insertSort(array &$arr): void
{
$num = count($arr);
if ($num <= 1) {
return;
}
for ($i = 1; $i < $num; $i++) {
$temp = $arr[$i];
for ($j = $i - 1; $j >= 0; $j--) {
if ($temp < $arr[$j]) {
$arr[$j + 1] = $arr[$j];
$arr[$j] = $temp;
} else {
break;
}
}
}
}
print_r($arr);
insertSort($arr);
print_r($arr);
/*
输出:
Array
(
[0] => 3
[1] => 5
[2] => 2
[3] => 4
[4] => 6
)
Array
(
[0] => 2
[1] => 3
[2] => 5
[3] => 4
[4] => 6
)
*/