后端技术 · Develop

算法菜鸟的烂笔头

•̀.̫•́✧ · 7月13日 · 2020年本文772字 · 阅读2分钟260
算法菜鸟的烂笔头

排序算法

冒泡排序

冒泡排序平均最好最坏辅助空间稳定性
时间复杂度O(n^2)O(n)O(n^2)O(1)稳定
<?php
$arr = [5, 2, 9, 21, 2, 56, 34, 12, 90, 45];
$len = count($arr);
for($i = 0; $i < $len; $i++) {
	for($j = 0; $j < $len - 1 - $i; $j++) {
		if($arr[$j] > $arr[$j+1]) {
			list($arr[$j+1], $arr[$j]) = [$arr[$j], $arr[$j+1]];
		}
	}
}
print_r($arr);

简单选择排序

简单选择排序平均最好最坏辅助空间稳定性
时间复杂度O(n^2)O(n^2)O(n^2)O(1)不稳定
<?php
$arr = [5, 2, 9, 21, 2, 56, 34, 12, 90, 45];
$len = count($arr);
for($i = 0; $i < $len - 1; $i++) {
	$min = $i;
	for($j = $i + 1; $j < $len; $j++) {
		if($arr[$j] < $arr[$min]) {
			$min = $j;
		}
	}
	if($min !== $i) {
		list($arr[$min], $arr[$i]) = [$arr[$i], $arr[$min]];
	}
}
print_r($arr);

直接插入排序

直接插入排序平均最好最坏辅助空间稳定性
时间复杂度O(n^2)O(n)O(n^2)O(1)稳定
<?php
$arr = [5, 2, 9, 21, 2, 56, 34, 12, 90, 45];
$len = count($arr);
for($i = 0; $i < $len - 1; $i++) {
	for($j = $i + 1; $j > 0; $j--) {
		if($arr[$j] < $arr[$j - 1]) {
			list($arr[$j], $arr[$j - 1]) = [$arr[$j - 1], $arr[$j]];
		}
	}
}
print_r($arr);
0 条回应