冒泡排序的PHP写法

function bubbleSort($numbers) {
    $cnt = count($numbers);
    for ($i = 0; $i < $cnt; $i++) {
        for ($j = 0; $j < $cnt - $i - 1; $j++) {
            if ($numbers[$j] > $numbers[$j + 1]) {
                $temp = $numbers[$j];
                $numbers[$j] = $numbers[$j + 1];
                $numbers[$j + 1] = $temp;
            }
        }
    }
    return $numbers;
}

$num = array(20, 40, 60, 80, 30, 70, 90, 10, 50, 0);
var_dump(bubbleSort($num));

yangshaoyang.cnyangshaoyang.cn

冒泡排序算法:(从后往前)

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

  3. 针对所有的元素重复以上的步骤,除了最后一个。

  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。


  若序列初始状态为正序,则一趟扫描即可完成排序,最好的时间复杂度为 yangshaoyang.cn

  若初始状态为反序,则需要进行n-1趟排序。每趟排序要进行n-1次关键字的比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:

     yangshaoyang.cn

    yangshaoyang.cn

冒泡排序的最坏时间复杂度为O(n2)


  因此,平均时间复杂度为O(n2)


橙色时光
请先登录后发表评论
  • 最新评论
  • 总共0条评论