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;
}

5. 二分法排序

时间复杂度log(N)

/**
 * 数据量很大时适合使用
 * 有序且不重复的数组
 * 基本原理： 
 *   假设数据按照升序排序，对于给定值x，从序列的中间开始比较：
 *      如果当前位置正好相等，则返回。
 *      若小于该值，则从前面开始查找
 *      若大于该值，则从后面继续查找，直到查找到该值
 * $array 要查询有序数组
 * 要查找值$val
 **/

function binarySearch($array, $val) {
    if (empty($val) || empty($array)) {
        return false;
    }
    $array = sort($array);
    $count = count($array);
    $low = 0;
    $high = $count - 1;
    while ($low <= $high) {
        $mid = intval(($low + $high) / 2);
        if ($array[$mid] == $val) {
            return $mid;
        }
        if ($array[$mid] < $val) {
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
    }
    return false;
}