数据结构与算法(php版)排序之冒泡排序

yang-pig| 阅读:617 发表时间:2018-07-25 22:32:43 算法

 冒泡排序算法的运作如下:

  1. 比较相邻的元素,如果前一个比后一个大,就把它们两个调换位置。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

先来一起看一下经典排序算法冒泡排序,冒泡排序(Bubble Sort),首先看实现过程:

20170521215800188.gif


<?php
/**
 * 冒泡排序
 * ------------------------------------------------
 * 分析:想冒泡一样,每次从数组当中,冒一个最大的数出来
 * -------------------------------------------------
 * (从小到大排序)存在10个不同大小的气泡,有底到上把较小的气泡逐步的向上升,
 * 这样经过遍历一次最小气泡就会被上升到顶部(下表为0)。
 * 然后再从底至上地这样升,循环直至十个气泡大小有序。
 * 在冒泡排序中,最重要的思想是两两比较,将两者较少的升上去
 */
/**
 * BubbleSort
 * @param array $container
 * @return array
 */
function BubbleSort(array $container) {
    $count = count($container);
    for ($i = 1; $i < $count; $i++) {
        for ($j = 0;$j < $count - $i; $j++) {
            if ($container[$j] > $container[$j + 1]) {
                $temp = $container[$j];
                $container[$j] = $container[$j + 1];
                $container[$j + 1] = $temp;
            }
        }
    }
    return $container;
}
var_dump(BubbleSort([4, 21, 41, 2, 53, 1, 213, 31, 21, 423]));

//array (size=10)
//  0 => int 1
//  1 => int 2
//  2 => int 4
//  3 => int 21
//  4 => int 21
//  5 => int 31
//  6 => int 41
//  7 => int 53
//  8 => int 213
//  9 => int 423

1.png

2.png