PHP的四种基本排序整理

1. 冒泡排序

function bubbleSort ($arr) 
{
     if (!is_array($arr)) return false;
     $len = count($arr);
     if ($len <= 1) return $arr;
    //控制需要处理冒泡次数
    for ($i=1; $i<$len; $i++) {
        //控制数组需要比较冒泡次数
        for ($k=0; $k < $len-$i; $k++)  {
            if ($arr[$k] > $arr[$k+1]) {
                $tmp = $arr[$k];
                $arr[$k] = $arr[$k+1];
                $arr[$k+1] = $tmp;
            }
        }
    }
    return $arr;
}

2. 选择排序

function selectSort($arr)
{
        if (!is_array($arr)) return false;
        $len = count($arr);
        if ($len <= 1) return $arr;
    //设置最小值，遍历整个数组
    for ($i=0; $i<$len-1; $i++) {
        //最小值为$i
        $p = $i;
        for ($j=$i+1; $j<$len; $j++) {
            //得到值最小的下标
            if ($arr[$p] > $arr[$j]) {
                $p = $j;
            }
        }
        if ($p != $i) {
            $tmp = $arr[$i];
            $arr[$i] = $arr[$p];
            $arr[$p] = $tmp;
        }
    }
    return $arr;
}

3. 快速排序

function quickSort($arr)
{
    if (!is_array($arr)) return false;
    $len = count($arr);
    if ($len <= 1) return $arr;
    $right = $left = array();
    for ($i=1; $i<$len; $i++) {
        if ($arr[$i] < $arr[0]) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    $left  = $quickSort($left);
    $right = $quickSort($right);
    return array_merge($left, array($arr[0]), $right);
}

4. 插入排序

/*
 * 从后向前扫描
 * 该元素已大于已排序$tmp，则该元素下移一个位置
 **/
function insertSort($arr)
{
    $len = count($arr);
    for ($i=1; $i<$len; $i++) {
        //假设当前值
        $tmp = $arr[$i];
        //需要插入次数
        for ($j=$i-1; $j>=0; $j--) {
            //位置互换
            if ($tmp < $arr[$j]) {
                $arr[$j+1] = $arr[$j];
                $arr[$j]    = $tmp;
            } else {
                break;
            }
        }
    }
    return $arr;
}