本文用php代码实例实现最常见的4种排序算法，冒泡排序算法及其改进、选择排序、插入排序、快速排序，并详解其复杂度。废话少说，直接上代码。

<?php
/*
 * 升序排列
 */
class Sort
{
    //冒泡排序, 稳定，时间复杂度O(n^2)
    public static function bubbleSort($src_arr)
    {
        $n = count($src_arr);
        for($i=0;$i<$n-1;$i++)
        {
            for($j=0;$j<$n-$i-1;$j++)
            {
                if ($src_arr[$j] < $src_arr[$j+1])
                {
                    $tmp = $src_arr[$j];
                    $src_arr[$j] = $src_arr[$j+1];
                    $src_arr[$j+1] = $tmp;
                }
            }
        }
        return $src_arr;
    }

    /*
     * 优化冒泡排序, 不稳定，最好时间O(n)
     * 如果没到最后一轮比较已经排好，则终止排序
     */
    public static function bubbleSortBetter($src_arr)
    {
        $n = count($src_arr);
        $flag = false;
        for($i=0;$i<$n-1;$i++)
        {
            for($j=0;$j<$n-$i-1;$j++)
            {
                if ($src_arr[$j] < $src_arr[$j+1])
                {
                    $tmp = $src_arr[$j];
                    $src_arr[$j] = $src_arr[$j+1];
                    $src_arr[$j+1] = $tmp;
                    $flag = true;
                }
            }
            if (!$flag) break;
        }
        return $src_arr;
    }

    /*
     * 选择排序, 不稳定，时间复杂度O(n^2)
     */
    public static function selectSort($src_arr)
    {
        for($i=0;$i<count($src_arr)-1;$i++)
        {
            for($j=$i+1;$j<count($src_arr);$j++)
            {
                if ($src_arr[$j] < $src_arr[$i])
                {
                    $tmp = $src_arr[$j];
                    $src_arr[$j] = $src_arr[$i];
                    $src_arr[$i] = $tmp;
                }
            }
        }
        return $src_arr;
    }

    /*
     * 插入排序, 稳定，时间复杂度O(n^2)
     */
    public static function insertSort($src_arr)
    {
        for($i=1;$i<count($src_arr);$i++)
        {
            $insertVal = $src_arr[$i];
            $insertIndex = $i - 1;
            while($insertIndex >= 0 && $insertVal < $src_arr[$insertIndex])
            {
                $src_arr[$insertIndex + 1] = $src_arr[$insertIndex];
                $insertIndex--;
            }
            $src_ar[$insertIndex] = $insertVal;
        }
        return $src_arr;
    }

    /*
     * 快速排序, 不稳定，时间复杂度：O(nlongn) ~ O(n^2)
     */
    public static function quickSort($src_arr)
    {
        if (count($src_arr) < 1)
        {
            return $src_arr;
        }
        $key = $src_arr[0];
        $left_arr = array();
        $right_arr = array();
        for($i=1;$i<count($src_arr);$i++)
        {
            if ($src_arr[$i] <= $key)
            {
                $left_arr[] = $src_arr[$i];
            }
            else
            {
                $right_arr[] = $src_arr[$i];
            }

            $left_arr = self::quickSort($left_arr);
            $right_arr = self::quickSort($right_arr);
            return array_merge($left_arr, $right_arr);
        }
    }

}

$source = array('5', '9', '13', '20', '36', '38', '48', '51', '59', '63', '65', '71', '73', '75', '76', '85', '89', '93', '100', '106', '108', '108', '109', '109', '13', '25', '21', '33', '55', '6', '5', '9', '3', '20', '36', '8', '8', '1', '9', '13', '25', '21', '33', '55', '6', '5', '9', '3', '20', '36', '8', '8', '1', '9', '13', '25', '21', '33', '55', '6', '5', '9', '3', '20', '36', '8', '8', '1', '9', '13', '25', '21', '33', '55', '6', '5', '9', '3', '20', '36', '8', '8', '1', '9', '13', '25', '21', '33', '55', '6', '5', '9', '3', '20', '36', '8', '8', '1', '9', '13', '25', '21', '33', '55', '6');
$time1 = microtime();
$sort = Sort::bubbleSort($source);
$time2 =  microtime();
$timeuse = $time2 - $time1;
echo '冒泡共使用时间:'.$timeuse."\n";

$time1 = microtime();
$sort = Sort::bubbleSortBetter($source);
$time2 =  microtime();
$timeuse = $time2 - $time1;
echo '优化冒泡共使用时间:'.$timeuse."\n";

$time1 = microtime();
$sort = Sort::selectSort($source);
$time2 =  microtime();
$timeuse = $time2 - $time1;
echo '选择排序共使用时间:'.$timeuse."\n";

$time1 = microtime();
$sort = Sort::insertSort($source);
$time2 =  microtime();
$timeuse = $time2 - $time1;
echo '插入排序共使用时间:'.$timeuse."\n";

$time1 = microtime();
$sort = Sort::quickSort($source);
$time2 =  microtime();
$timeuse = $time2 - $time1;
echo '快速排序共使用时间:'.$timeuse."\n";
?> 

---

nginx公众号也会推送好文，主要聊聊后端技术，扫描或者搜索nginx即可添加。