题目描述:写一个冒泡排序算法
冒泡排序是经典的排序方式之一,算法复杂度为O(n2)其算法的核心是,对一个n个元素数组,需要进行n-1轮的循环比较。每一轮的循环中,将相邻的元素进行比较,如果左边的元素值大于右边的元素,则将两者的位置交换;每一轮结束后,最大值的元素就会放置在最右的位置,这样循环结束后,所有的元素都会按从小到大的顺序排列完
例如对数组[6,5,4,1,2.3]用冒泡方法进行排序:
原始数组:[6,5,4,1,2,3]
第一次循环:[5,4,1,2,3,6]
第二次循环:[4,1,2,3,5,6]
第三次循环:[1,2,3,4,5,6]
第四次循环:[1,2,3,4,5,6]
第五次循环:[1,2,3,4,5,6]
大家注意到第四、五次循环时,并没有发生位置交换
这时可以设置一个FLAG,如果一个循环中没有位置交换则说明排序已完成,退出循环即可。这样一个FLAG变量的设置,减少了一次循环的时间。
在其他的场合,也可以设置合适的FLAG,当满足条件时更改FLAG的值,然后检测FLAG的值决定是否退出循环可以减少循环的次数,提高程序的效率
程序代码如下
<?php
/**
* 冒泡排序.
*
* @return mixed
*/
function bubble_sort($array)
{
for ($i = count($array) - 1; $i >= 1; --$i) {
$flag = false; // flag 用来记录以下循环中是否发生了交换,没有则代表排序完成
for ($j = 0; $j <= $i - 1; ++$j) {
if ($array[$i] > $array[$i + 1]) {
// 若左边的元素大于右边的元素,则交换,flag 设置为 1
$temp = $array[$j];
$array[$j] = $array[$j + 1];
$array[$j + 1] = $temp;
$flag = true;
}
}
if (!$flag) {
// 如果没有交换 ,则已经排序完成,退出循环
break;
}
}
return $array;
}
发布时间 : 2023-02-28,阅读量:949
, 分类:
PHP