henryspace

记录精彩的程序人生 开始使用

PHP 排序算法

冒泡排序

//循环进行相邻两数比较,大的放后边
$arr = [2,44,56,23,11,46,69,35];
function pop_sort($arr){
    $len = count($arr);
    for($i=1; $i<$len; $i++){
    	for($j=0; $j<$len-$i; $j++){
    		if($arr[$j] > $arr[$j+1]){
    			$tmp = $arr[$j+1];
    			$arr[$j+1] = $arr[$j];
    			$arr[$j] = $tmp;
    		}
    	}
    }
    return $arr;
}

选择排序

//假设每次循环找到最小值依次放进数组
$arr = [2,44,56,23,11,46,69,35];
function select_sort($arr)
{
	$len = count($arr);
	for($i=0; $i<$len-1; $i++){
		$min = $i;
		for($j=$min+1; $j<$len; $j++){
			if($arr[$min] > $arr[$j]){
				$min = $j;
			}
		}
		if($min <> $i){
			$tmp = $arr[$min];
			$arr[$min] = $arr[$i];
			$arr[$i] = $tmp;
		}
	}
	return $arr;
}

插入排序

//将要排序的元素插到假定已经排好序的数组里
$arr = [2,44,56,23,11,46,69,35];
function insert_sort($arr)
{
	$len = count($arr);
	for($i=1; $i<$len; $i++){
		$tmp = $arr[$i];
		for($j=$i-1; $j>=0; $j--){
			if($tmp < $arr[$j]){
				$arr[$j+1] = $arr[$j];
				$arr[$j] = $tmp;
			}else{
				break;
			}
		}
	}
	return $arr;
}

快速排序

//从数组取一个数作为标尺,遍历数组小于标尺的放数组a, 大于标尺的放数组b, 递归,最后合并a-标尺-b即可
function quick_sort($arr)
{
	$len = count($arr);
	if($len <= 1){
		return $arr;
	}
	$base_num = $arr[0];

	$left =[];
	$right =[];
	for($i=1; $i<$len; $i++){
		if($arr[$i] < $base_num){
			$left[] = $arr[$i];
		}else{
			$right[] = $arr[$i];
		}
	}
	$left = quick_sort($left);
	$right = quick_sort($right);

	$arr = array_merge($left, [$base_num], $right);
	return $arr;
}

时间复杂度

|排序方式 |最差时间分析 |平均时间复杂度 |稳定度 |空间复杂度
|:--- |:--- |:--- |:--- |:---
|冒泡排序 |O(n2) |O(n2) |稳定 |O(1)
|快速排序 |O(n2) | O(nlog2n) |不稳定 |O(log2n)~O(n)
|选择排序 |O(n2) |O(n2) |稳定 |O(1)
|二叉树排序 |O(n2) |O(n
log2n) |不稳定 |O(n)
|插入排序 |O(n2) |O(n2) |稳定 |O(1)
|堆排序 |O(nlog2n) |O(nlog2n) |不稳定 |O(1)
|希尔排序 |O |O |不稳定 |O(1)

空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。

对于一个算法来说,空间复杂度和时间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。

有时我们可以用空间来换取时间以达到目的。

请成为永远疯狂永远浪漫永远清澈的存在。

评论
留下你的脚步
推荐阅读