时间复杂度为O(n^2)的排序
发布网友
发布时间：2023-03-29 03:06
共1个回答
热心网友
时间：2023-10-30 22:11
* Created by PhpStorm.
* User: shinho01
* Date: 2019/9/11
* Time: 16:11
*/
/**
* 冒泡排序只涉及相邻数据的交互操作，只需要常量集的临时空间，所以空间复杂度为1，是原地排序算法
* 相同大小的元素可以不做交换
* 最坏的时间复杂度是O（n^2),最好情况的复杂度是O(1)
* @param $arr
* @return mixed
*/
function bubbleSort(&$arr)
{
$n = count($arr);
if ($n <= 1) {
return;
}
for ($i = 0; $i < $n; $i++) {
$flag = false;
for ($j=0; $j < $n-$i-1; $j++) {
if ($arr[$j] > $arr[$j+1]) {
$tmp = $arr[$j];
$arr[$j] = $arr[$j+1];
$arr[$j+1] = $tmp;
$flag = true;
}
}
if (!$flag) {
break;
}
}
}
/**
* 插入排序（左右两部分（已排序和未排序））
* 插入排序的空间复杂度是O(1)
* 是稳定的排序算法
* 最好的时间复杂度是O(N），最坏情况时间复杂度是O（n^2）
* @param $arr
*/
function insertSort(&$arr)
{
$n = count($arr);
if ($n <= 1) {
return;
}
for ($i=1; $i< $n; $i++) {
$value = $arr[$i];
$j = $i-1;
for (;$j >= 0; --$j) {
if ($arr[$j] > $value) {
$arr[$j+1] = $arr[$j];
} else {
break;
}
}
$arr[$j+1] = $value;
}
}
/**
* 空间复杂度O(1),是一种原地排序
* 最好情况和最坏情况的时间复杂度都是O(n^2)
* 非稳定排序算法
* 选择排序
* @param $arr
*/
function selectSort(&$arr)
{
$n = count($arr);
if ($n <= 1) {
return;
}
for ($i=0; $i<$n-1; $i++) {
$p = $i;
for ($j=$i+1; $j < $n; $j++) {
if ($arr[$p] > $arr[$j]) {
$p = $j;
}
}
if ($p = $i) {
continue;
}
$tmp = $arr[$i];
$arr[$i] = $arr[$p];
$arr[$p] = $tmp;
}
}
$arr = [9,2,4,6,2,5,9,1,4,6];
bubbleSort($arr);
insertSort($arr);
print_r($arr);
