不败君

前端萌新&初级后端攻城狮

PHP实现冒泡与快速排序算法

PHP实现冒泡与快速排序算法

2020-10-22 10:53:00

围观(614)

冒泡排序算法:

function bubbleSort(array $lst_number)
{
	// 获取数组长度
	$length = count($lst_number);

	if ($length <= 1) return $lst_number;

	// 本层循环控制需要冒泡排序的次数
	for ($i = 1; $i < $length; $i++) {
		// 本层控制每次冒泡当前和后面数字大小比较的次数
		for ($j = 0; $j < $length - $i; $j++) {
			if ($lst_number[$j] > $lst_number[$j + 1]) {
				// 当前数字比下一个数字大 则调换位置
				$temp = $lst_number[$j + 1];
	            $lst_number[$j + 1] = $lst_number[$j];
	            $lst_number[$j] = $temp;
			}
		}
	}

	return $lst_number;
}

实现原理:依次获取数组里面的值,与后面相邻的数字进行比较,数字大的往后一位排序,数字小的向前移(即数字位置互换)。


快速排序算法:

function quickSort(array $lst_number)
{
	// 获取数组长度
	$length = count($lst_number);

	if ($length <= 1) return $lst_number;

	// 选择第一个元素作为基准
    $base_number = $lst_number[0];

    $lst_left = [];  	// 小于基准的
    $lst_right = [];  	// 大于基准的

    // 遍历除了基准外的数字,按照大小关系放入两个数组
    for ($i = 1; $i < $length; $i++) { 
    	// 此处判断基准数小于当前循环的数 改变小于号为大于号即可将处理结果改为大到小排序
    	if ($base_number < $lst_number[$i]) {
    		// 小于基准数 放入右数组
    		$lst_right[] = $lst_number[$i];
    	} else {
    		// 大于基准数 放入左数组
    		$lst_left[] = $lst_number[$i];
    	}
    }

    // 分别对左数组和右数组进行相同的排序处理并递归调用这个函数
    $lst_left = quickSort($lst_left);
    $lst_right = quickSort($lst_right);

    // 合并数组
    return array_merge($lst_left, [$base_number], $lst_right);
}

实现原理:选择数组第一个数字作为基准数,通过循环将数字分为小于基准与大于基准的,再递归重复将数组第一个数字作为基准再次比较并存入数组,依次重复操作后即可获取到比较完成后的数组。


运行方法:

// 先定义一个数组
$lst_number = [1, 100, 8, 9, 5, 3, 22, 10, 19, 14, 2, 33, 56];

// 冒泡算法结果:
var_dump(bubbleSort($lst_number));

// 快速排序结果:
var_dump(quickSort($lst_number));

关于数字比较的算法还有比较常见的选择排序 / 插入排序。 博主比较喜欢快速排序,因为只循环了一次数组(虽然有递归)比较容易理解。

本文地址 : www.bubaijun.com/page.php?id=214

版权声明 : 未经允许禁止转载!

评论:我要评论
发布评论:
Copyright © 不败君 粤ICP备18102917号-1

不败君

首 页 作 品 微 语