快速排序算法的PHP与JQuery简单实现

快速排序(以下简称快排)算法的PHP与JQuery简单实现

1.简介:

• 1.快排的本质是冒泡排序(Bubble Sort)的优化;
• 2.快排的排序效率在同为O(N*logN)的几种排序方法中效率较高;
• 3.为了便于说明,这里将以数组为例,实际应用可灵活拓展;

2.核心思想:

• 1.选择一个基本元素作为参照值,通常选择为第一位或中间一位;
• 2.以基本元素为参照,将数组分割为两个区间:一个区间A全部大于该值,一个区间B全部小于该值;
• 3.再分别对AB区间重复上述1,2操作,直到再无可被拆分的元素;
• 4.整合区间碎片,即得目标对象;

PHP Demo:

public function fsort($a_array) {
// 初始化分隔区间
$a_left = array();
$a_right = array();
// 设置终止条件
if (isset($a_array[0])) {
    $o_flag = $a_array[0];
}
if (!isset($a_array[1])) {
    return $a_array;
}
// 分割目标对象
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];
    }
}
// 递归处理分割后的两个区间
$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){
// 初始化分隔区间
var left = [],
    right = [];
// 设置终止条件
if (array[0]) {
    var flag = array[0];
}
if (!array[1]) {
    return array;
}
// 分割目标对象
for (i = 0; i < array.length; i++) { 
    if (array[i] < flag) {
        left.push(array[i]);
    }
    if (array[i] > flag) {
        right.push(array[i]);
    }
}
// 递归处理分割后的两个区间
left = qSort(left);
left.push(flag);
right = qSort(right);
return $.merge(left, right);
}