【面试题】冒泡排序

文笔有限，介绍是从别人那里直接抄的。

冒泡排序它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序的原则：是比较相邻的元素，如果违反最后的顺序准则，则交换。
可以简化理解为：
第一次找到所有元素中最大的放在最后一个位置上，不再变动；
第二次找到剩余所有元素中最大的放在倒数第二个位置上，不再变动；
以此类推，直到排序完成。

代码自己实现

/**
 * 冒泡排序
 * @param array $arr 要排序的数组
 * @param boolean $flag true 从大到小 false 从小到大
 * @return array 排序完成的数组
 */
function BubbleSort ($arr, $flag = true) {
    // 定义返回数据
    $ret = [];
    do{
        // 取出一个数据给临时变量
        $tmp = array_shift($arr);
        foreach ($arr as $key => $value) {
            // 根据标志判断 小的交换还是大的交换
            if($flag){
                // 从大到小
                if($tmp < $value){
                    // 交换位置
                    $arr[$key] = $tmp;
                    $tmp = $value;
                }
            } else {
                // 从小到大
                if($value < $tmp){
                    // 交换位置
                    $arr[$key] = $tmp;
                    $tmp = $value;
                }
            }
        }
        // 将冒泡出来的数据放置到返回数据中
        $ret [] = $tmp;
        // 是否进行下一次循环
    } while (count($arr));
    return $ret;
}

上面定义好了函数，接下来我们测试一下吧

$arr = [89,8, 53, 5, 78, 783, -7, -85];
print_r(BubbleSort($arr));
print_r(BubbleSort($arr, false));
// 结果

Array
(
    [0] => 783
    [1] => 89
    [2] => 78
    [3] => 53
    [4] => 8
    [5] => 5
    [6] => -7
    [7] => -85
)
Array
(
    [0] => -85
    [1] => -7
    [2] => 5
    [3] => 8
    [4] => 53
    [5] => 78
    [6] => 89
    [7] => 783
)

结果像我们想的一样这样就排好了。