数据结构和算法

当前位置:首页>数据结构和算法

排序算法-快速排序

时间:2019-04-17   访问量:21

<?php

/**

 * 快速排序

 *

 * -------------------------------------------------------------

 * 思路分析:从数列中挑出一个元素,称为 “基准”(pivot) 

 * 大O表示: O(n log n) 最糟 O(n 2)

 * -------------------------------------------------------------

 * 重新排序数列,所有元素比基准值小的摆放在基准前面,C 语言中的 qsort就是快速排序

 * 所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。

 * 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序

 */

// +--------------------------------------------------------------------------

// | 解题方式

// +--------------------------------------------------------------------------

/**

 * QuickSort

 *

 * @param array $container

 * @return array

 */

function QuickSort(array $container)

{

    $count = count($container);

    if ($count <= 1) { // 基线条件为空或者只包含一个元素,只需要原样返回数组

        return $container;

    }

    $pivot = $container[0]; // 基准值 pivot

    $left  = $right = [];

    for ($i = 1; $i < $count; $i++) {

        if ($container[$i] < $pivot) {

            $left[] = $container[$i];

        } else {

            $right[] = $container[$i];

        }

    }

    $left  = QuickSort($left);

    $right = QuickSort($right);

    return array_merge($left, [$container[0]], $right);

}

// +--------------------------------------------------------------------------

// | 方案测试

// +--------------------------------------------------------------------------

var_dump(QuickSort([4, 21, 41, 2, 53, 1, 213, 31, 21, 423]));

/**

 * array(10) {

 * [0] =>

 * int(1)

 * [1] =>

 * int(2)

 * [2] =>

 * int(4)

 * [3] =>

 * int(21)

 * [4] =>

 * int(21)

 * [5] =>

 * int(31)

 * [6] =>

 * int(41)

 * [7] =>

 * int(53)

 * [8] =>

 * int(213)

 * [9] =>

 * int(423)

 * }

 */

/**

 * PS & EX:

 *  快速排序使用分而治之【 divide and conquer,D&C 】的策略,D&C 解决问题的过程包括两个步骤

 *  1. 找出基线条件,这种条件必须尽可能简单

 *  2. 不断将问题分解(或者说缩小规模),直到符合基线条件

 * (D&C 并非解决问题的算法,而是一种解决问题的思路)

 */


上一篇:排序算法-插入排序

下一篇:排序算法-堆排序

在线咨询

点击这里给我发消息 售前咨询专员

点击这里给我发消息 售后服务专员

在线咨询

免费通话

24小时免费咨询

请输入您的联系电话,座机请加区号

免费通话

微信扫一扫

微信联系
返回顶部