PHP排序算法之快速排序

CoderDock 發(fā)布于2019-07-01 10:30 / 2101人閱讀

摘要：實(shí)現(xiàn)代碼判斷參數(shù)是否是一個(gè)數(shù)組遞歸出口數(shù)組長(zhǎng)度為，直接返回?cái)?shù)組數(shù)組元素有多個(gè)，則定義兩個(gè)數(shù)組循環(huán)遍歷數(shù)組，把第一個(gè)元素當(dāng)做比較的對(duì)象判斷當(dāng)前元素的大小遞歸調(diào)用將所有的結(jié)果合并

原理：找到當(dāng)前數(shù)組中的任意一個(gè)元素（一般選擇第一個(gè)元素），作為標(biāo)準(zhǔn)，新建兩個(gè)空數(shù)組left、rignt，遍歷整個(gè)數(shù)組元素，如果遍歷到的元素比當(dāng)前的元素小就放到數(shù)組left，比當(dāng)前的元素大放到rignt，然后再對(duì)新數(shù)組進(jìn)行同樣的操作。

遞歸：
遞歸是一種函數(shù)調(diào)用自身的機(jī)制。
遞歸必須要有邊界條件，也就是遞歸出口（退出遞歸）
遞歸前進(jìn)段和遞歸返回段，也就是最后得到的值
當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件（遞歸出口）滿足是，遞歸返回。
PHP的遞歸非常消耗性能，盡量避免使用。

快速排序的原理復(fù)合遞歸原理
遞歸點(diǎn)：如果數(shù)組元素大于1，就需要再進(jìn)行分解，所以我們的遞歸點(diǎn)就是新構(gòu)造的數(shù)組元素個(gè)數(shù)大于1
遞歸出口：當(dāng)數(shù)組元素個(gè)數(shù)為1，不需再對(duì)新數(shù)組進(jìn)行排序。

實(shí)現(xiàn)代碼：

$arr = [34,56,7,89,12,9];
function quick_sort($arr)
{

// 判斷參數(shù)是否是一個(gè)數(shù)組
if(!is_array($arr)) return false;
// 遞歸出口：數(shù)組長(zhǎng)度為1，直接返回?cái)?shù)組
$length = count($arr);
if($length <= 1) return $arr;
// 數(shù)組元素有多個(gè)，則定義兩個(gè)數(shù)組
$left = $right = [];
// 循環(huán)遍歷數(shù)組，把第一個(gè)元素當(dāng)做比較的對(duì)象
for($i=1;$i<$length;$i++)
{
    //判斷當(dāng)前元素的大小
    if($arr[$i] < $arr[0])
    {
        $left[] = $arr[$i];
    }
    else
    {
        $right[] = $arr[$i];
    }
}
// 遞歸調(diào)用
$left = quick_sort($left);
$right = quick_sort($right);
// 將所有的結(jié)果合并
return array_merge($left,[$arr[0]],$right);

}
print_r(quick_sort($arr));