面试常见的基本排序算法简单理解

1、冒泡排序

从前往后进行，比较相邻两个元素，小的往上冒，大的往下沉。

$arr = array(100,43,54,62,21,66,32,78,36,76,39);
//逻辑：从前往后进行，比较相邻两个元素，小的往上冒，大的往下沉
function mpSort($arr)
{
    $num = count($arr);
    for ($j=0; $j < $num; $j++) { //排序需要的冒泡次数
        for ($i=0; $i < $num-1; $i++) { //每次冒泡需要进行的比较次数
            if ($arr[$i] > $arr[$i+1]) {
                $tmp = $arr[$i];
                $arr[$i] = $arr[$i+1];
                $arr[$i+1] = $tmp;
            }
        }
    }

}
// mpSort($arr);

2、快速排序

选取一个基准元素，一般会选取第一个或者最后一个元素，以此为基准把序列拆分，左边为比基准值小的序列，右边为比基准值大的序列，以此类推利用递归重复不断拆分，直到不能拆分为止。

function ksSort($arr)
{
    $num = count($arr);
    if ($num <= 1) {//判断是否继续
        return $arr;
    }
    $p = $arr[0];//基准元素
    $aArr = array();
    $bArr = array();
    for ($i=1; $i < $num; $i++) { 
        if ($arr[$i] < $p) {
            $aArr[] = $arr[$i];
        }else {
            $bArr[] = $arr[$i];
        }
    }
    $aArr = ksSort($aArr);
    $bArr = ksSort($bArr);
    return array_merge($aArr,array($p),$bArr);
}

3、选择排序

选出最小的一个元素与第一个位置的元素交换，然后在剩下的数当中再找最小的与第二个位置的数交换。(这里可以假设最小值就是第一个元素)

function stSort($arr) {
//双重循环完成，外层控制轮数，内层控制比较次数
    $num=count($arr);
    for($i=0; $i<$num-1; $i++) {
        //假设最小的值的位置
        $p = $i;
        for($j=$i+1; $j<$num; $j++) {
            //$arr[$p] 是当前已知的最小值
            if($arr[$p] > $arr[$j]) {
            //比较，发现更小的,记录下最小值的位置；并且在下次比较时采用已知的最小值进行比较。
                $p = $j;
            }
        }
        //已经确定了当前的最小值的位置，保存到$p中。如果发现最小值的位置与当前假设的位置$i不同，则互换位置。
        if($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    //返回最终结果
    return $arr;
}