快速排序的php实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› PHP›PHP编程经验

原作者: [db:作者] 来自: [db:来源] 收藏邀请

　　再来一个非常高级的排序算法，快速排序...这个算法是很高效的。

快速排序的思路是，找到一个分割点（中枢点默认是列表第一个值），把原列表分隔成两部分，在分割点左侧的是都比它小的，在它右侧的是都比它大的。然后分别把这两部分再递归调用排序，自然就全部排序完成。

当然最重要的步骤就是切分，然后进行递归调用，重复以上分割操作，直到break。代码示例如下：

第一种实现更能直观细节展示出快排中的含义：

$arr = array(19, 17, 13, 16,12 , 11, 4, 9, 77, 18);

qsort(0, count($arr) - 1, $arr);

echo "<pre>";
print_r($arr);

/**
 * @param $low
 * @param $high
 * @param $arr
 * 快速排序 递归调用
 * 关键点在于part动作
 */
function qsort($low, $high, &$arr){
    if($low < $high){
        $pivot = part($low, $high, $arr);
        qsort($low, $pivot-1, $arr);
        qsort($pivot+1, $high, $arr);
    }

}


/**
 * @param $low
 * @param $high
 * @param $arr
 * @return mixed
 * part的核心动作在于-- 中枢点的位置不断变换,比它小的换到它的左边,比它大的换到它的右边
 */
function part($low, $high, &$arr){
    $pivot = $arr[$low];// 中枢点默认是列表第一个

    while($low < $high){
        while($low < $high && $arr[$high] >= $pivot){// 右边选比中枢点小的
            $high--;
        }
        swap($arr, $low, $high);// 此时中枢点在低位置,而此时的高位置小于中枢点。两点交换

        while($low < $high && $arr[$low] <= $pivot){// 左边选比中枢点大的
            $low++;
        }
        swap($arr, $low, $high);// 此时中枢点在高位置,而此时的低位置大于中枢点。两点交换
    }

    return $low;// 低位此时是中枢点,返回中枢点位置
}

/**
 * @param $arr
 * @param $i
 * @param $j
 * 交换位置
 */
function swap(&$arr, $i, $j){
    $temp = $arr[$i];
    $arr[$i] = $arr[$j];
    $arr[$j] = $temp;
}

理解快速排序怎么交换值这点尤为关键，这个算法很机智。。加深理解算法中的智慧吧～

另一种流传比较广的php写快速排序，切分后的两边用两个数组装起来。

代码：

$arr = array(19, 17, 13, 16, 12, 11, 4, 9, 77, 18);

echo "<pre>";
print_r(quick_sort($arr));

/**
 * @param $arr
 * @return array
 * 快速排序
 */
function quick_sort($arr) {
    // 递归结束: 数组长度为1，直接返回
    $length = count($arr);
    if ($length <= 1) {
        return $arr;
    }
    // 数组元素有多个,则定义两个空数组
    $left = $right = array();
    // 使用for循环进行遍历，默认第一个元素作为中枢点
    for ($i = 1; $i < $length; $i++) {
        // 判断当前元素的大小
        if ($arr[$i] < $arr[0]) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }
    // 递归调用
    $left = quick_sort($left);
    $right = quick_sort($right);
    // 将所有的结果合并
    return array_merge($left, array($arr[0]), $right);// 中间切点
}