排序算法（一）冒泡排序

      从事PHP工作已经有二年多了，在从事PHP工作中发现要自己去使用基础算法的情况很少，大多数是使用别人已经做好的类库，但是作为一名码农，算法是应该熟练掌握的基础功力之一，所以从今天起，开始复习数据结构和算法，重新拾起大学时代的计算机基础课。今天就开始排序算法-冒泡排序开始。

      在开始冒泡排序算法之前，先了解几个概念：

      1、算法复杂度：算法复杂度分为时间复杂度和空间复杂度。

       （1）时间复杂度：是度量算法执行的时间长短；

　　　　　　1）时间频度：一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)

　　　　　　一般情况下，算法的基本操作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））

　　　　　　分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。

　　　　　　在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以　　　　　　　　　　下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数　　　　　　  c，则时间复杂度T（n）=O（f（n））

       （2）空间复杂度：是度量算法所需存储空间的大小。

　　　　一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度，可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存储本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。

         1）固定部分

　　　　这部分空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间。这部分属于静态空间。

         2）可变空间

　　　　这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。

　　　　  一个算法所需的存储空间用f(n)表示。

　　　　 S(n)=O(f(n))

　　　　 其中n为问题的规模，S(n)表示空间复杂度。

 

     2、稳定性：这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列。

 

     几个算法相关概念了解到此，我们开始冒泡排序算法的学习：

        

     冒泡排序：冒泡排序是经过n-1趟子排序完成的，第 i 趟子排序从第1个数至第 n-i 个数，若第i个数比后一个数大（则升序，小则降序）则交换两数

                    

　　　　1、编程复杂度很低，很容易写出代码；

           2、具有稳定性

           3、速度不及堆排序、快速排序

 

     PHP实现的代码：

function bubbleSort( $arr = array())
{
    if(empty($arr))
    {
        return FALSE;
    }

    $length = count($arr);
    
    for($i = 0; $i < $length -1; $i++)
    {
        for($j = 0; $j < $length - 1 - $i; $j++)
        {
            if($arr[$j] < $arr[$j+1])
            {
                $tmp       = $arr[$j];
                $arr[$j]   = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }        
        print_r($arr);
        echo "<br>";
    }
    return $arr;
}

$arr = array(8,10,1,9,7,5,6,2,4,3);
$sort_arr = bubbleSort($arr);

经过N-1趟排序，各趟排序结果如下：