冒泡排序

普通方法

$arr=[8,9,1,2,4,6,3,5,7];
for ($j=count($arr)-1;$j>0;$j--)
{
    for ($i=0;$i<$j;$i++)
    {
        if ($arr[$i]>$arr[$i+1])
        {
            $temp=$arr[$i];
            $arr[$i]=$arr[$i+1];
            $arr[$i+1]=$temp;
        }

    }

}

优化一：设置标志位

可以设置一个标志位，记录上一次排序是否有交换，没有交换就可以提前结束了。

$arr=[8,9,1,2,4,6,3,5,7];
$flag=true; //初始
for ($j=count($arr)-1;$j>0;$j--)
{
    if(!$flag)
    {
        break;
    }
    $flag=false; //初始
    for ($i=0;$i<$j;$i++)
    {
        if ($arr[$i]>$arr[$i+1])
        {
            $temp=$arr[$i];
            $arr[$i]=$arr[$i+1];
            $arr[$i+1]=$temp;
            $flag=true; //交换了
        }

    }

}

优化二：设置标志位

记录上一次最后交换的位置，作为下一次循环的结束边界。最后一次比较说明在那之后的元素都已经排好序，无需再比较，可以避免一些无意义的比较。

$arr=[8,9,1,2,4,6,3,5,7];
$flag=true; //初始
$lastPos=count($arr)-1;//最后一次交换的位置，初始时设为“数组长度 - 1”
for ($j=count($arr)-1;$j>0;$j--)
{
    if(!$flag)
    {
        break;
    }
    $flag=false; //初始
    $k=$lastPos;  // 上一次的最后交换位置作为这次循环的边界
    for ($i=0;$i<$k;$i++)
    {
        if ($arr[$i]>$arr[$i+1])
        {
            $temp=$arr[$i];
            $arr[$i]=$arr[$i+1];
            $arr[$i+1]=$temp;
            $flag=true; //交换了
            $lastPos=$i; // 更新最后交换位置
        }

    }

}

优化三：双向冒泡排序

双向冒泡排序，又叫鸡尾酒排序（Cocktail Sort）。

它的过程是：先从左往右比较一次，再从右往左比较一次，然后又从左往右比较一次，以此类推。

它是为了优化前面的大部分元素都已经排好序的数组的排序，例如对于数组 [2,3,4,5,6,7,8,1]，如果使用普通的冒泡排序，需要比较七次；而换成双向冒泡排序，只需比较三次。

$arr=[8,9,1,2,4,6,3,5,7];
$left = 0; //左边位置
$right =count($arr) - 1; //右边位置
$lastSwapIndex = 0;      // 记录最后一次交换的位置
$hasSwap = false;    // 标志位
while ($left < $right) {
    for ($i = $left; $i < $right; $i++) { // 保证 a[right] 是最大的
              if ($arr[$i] > $arr[$i+1]) {
                    $temp=$arr[$i];
                    $arr[$i]=$arr[$i+1];
                    $arr[$i+1]=$temp;
                    $hasSwap = true;
                    $lastSwapIndex = $i;
                }
            }
            $right = $lastSwapIndex;  // 将最后一次交换的位置作为右边界
            if (!$hasSwap) { // 上一轮没有交换，提前结束
                break;
            }
            $hasSwap = false;
            for ($i = $right; $i > $left; $i--) { // 保证 a[left] 是最小的
                if ($arr[$i] < $arr[$i-1]) {
                    $temp=$arr[$i];
                    $arr[$i]=$arr[$i-1];
                    $arr[$i-1]=$temp;
                    $hasSwap = true;
                    $lastSwapIndex = $i;
                }
            }
            $left = $lastSwapIndex;  // 将最后一次交换的位置作为左边界
            if (!$hasSwap) { // 上一轮没有交换，提前结束
                break;
            }
            $hasSwap = false;

        }
    print_r($arr);