冒泡排序

冒泡排序（Bubble Sort）是一种简单直观的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

1. 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素进行同样的操作，从开始第一对到结尾的最后一对。完成一遍操作后，最大的数就移到了最后一位。
重复以上的步骤，除了最后一位元素。
对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
说明：
冒泡排序第1次遍历后会将最大值放到最右边，这个最大值也是全局最大值。
标准冒泡排序的每一次遍历都会比较全部的元素，尽管最右侧的值已经是最大值了。
优化之后，每次遍历的元素数量减一，最大值，次大值等等会固定在右侧，避免了重复比较。

2. 代码实现

PHP代码实现

<?php

function mySort($arr)
{
    # code...
    $len = count($arr);
    for($i = 0;$i < $len - 1;$i++){
        for($j = 0;$j < $len - 1 - i;$j++){
            if($arr[$j] > $arr[$j+1]){
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp;
            }
        }
    }
    return $arr;
}

$data = [9,7,4,1,6,5];
var_dump(mySort($data));

JavaScript 代码实现

function mySort(arr) {
    var len = arr.length;
    for(var i = 0;i < len - 1;i++){
        for(var j = 0; j < len - 1 - i;j++){
            if(arr[j] > arr[j+1]){
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}
var data = [2,9,4,8,1,7,3];
console.log(mySort(data))

3. 小结

1. 时间复杂度：O(n²)，其中n为数组的长度。
2. 空间复杂度：O(1)