PHP面试题(一)


冒泡排序

题目描述:写一个冒泡排序算法

 

冒泡排序是经典的排序方式之一,算法复杂度为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
本文链接:https://upwqy.com/details/39.html
vue中tinymce设置字体大小、字体选择 微信小程序支付(三)退款