快速排序(以下簡(jiǎn)稱快排)算法的PHP與JQuery簡(jiǎn)單實(shí)現(xiàn)

1.簡(jiǎn)介:

• 1.快排的本質(zhì)是冒泡排序(Bubble Sort)的優(yōu)化;
• 2.快排的排序效率在同為O(N*logN)的幾種排序方法中效率較高;
• 3.為了便于說明,這里將以數(shù)組為例,實(shí)際應(yīng)用可靈活拓展;

2.核心思想:

• 1.選擇一個(gè)基本元素作為參照值,通常選擇為第一位或中間一位;
• 2.以基本元素為參照,將數(shù)組分割為兩個(gè)區(qū)間:一個(gè)區(qū)間A全部大于該值,一個(gè)區(qū)間B全部小于該值;
• 3.再分別對(duì)AB區(qū)間重復(fù)上述1,2操作,直到再無可被拆分的元素;
• 4.整合區(qū)間碎片,即得目標(biāo)對(duì)象;

PHP Demo:

public function fsort($a_array) {
// 初始化分隔區(qū)間
$a_left = array();
$a_right = array();
// 設(shè)置終止條件
if (isset($a_array[0])) {
    $o_flag = $a_array[0];
}
if (!isset($a_array[1])) {
    return $a_array;
}
// 分割目標(biāo)對(duì)象
for ($i = 0; $i < count($a_array); $i++) { 
    if ($a_array[$i] < $o_flag) {
        $a_left[] = $a_array[$i];
    }
    if ($a_array[$i] > $o_flag) {
        $a_right[] = $a_array[$i];
    }
}
// 遞歸處理分割后的兩個(gè)區(qū)間
$a_left = $this->fsort($a_left);
$a_left[] = $o_flag;
$a_right = $this->fsort($a_right);
return array_merge($a_left, $a_right);
}

JQuery Demo:

var qSort = function(array){
// 初始化分隔區(qū)間
var left = [],
    right = [];
// 設(shè)置終止條件
if (array[0]) {
    var flag = array[0];
}
if (!array[1]) {
    return array;
}
// 分割目標(biāo)對(duì)象
for (i = 0; i < array.length; i++) { 
    if (array[i] < flag) {
        left.push(array[i]);
    }
    if (array[i] > flag) {
        right.push(array[i]);
    }
}
// 遞歸處理分割后的兩個(gè)區(qū)間
left = qSort(left);
left.push(flag);
right = qSort(right);
return $.merge(left, right);
}