php快速排序

sisophon 2019-10-02 PM 15℃ 0条

快速排序(Quicksort)是对冒泡排序的一种改进。

原理:

a.挑选基准值:从数列中挑出一个元素,称为“基准”(pivot)

b.分割:重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(与基准值相等的数可以到任何一边)。在这个分割结束之后,对基准值的排序就已经完成,

c.递归排序子序列:递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

代码:

$arr = [6,9,8,5,2,1,4];
function quickSort($arr)
{
    $count = count($arr);
    if ($count < 2) {
        return $arr;
    }
    $leftArray = $rightArray = array();
    $middle = $arr[0];// 基准值

    for ($i = 1; $i < $count; $i++) {
        // 小于基准值,存入左边;大于基准值,存入右边
        if ($arr[$i] < $middle) {
            $leftArray[] = $arr[$i];
        } else {
            $rightArray[] = $arr[$i];
        }
    }
    $leftArray =  quickSort($leftArray);
    $rightArray = quickSort($rightArray);
    return array_merge($leftArray, array($middle), $rightArray);
}
print_r(quickSort($arr));

解析:

第一次:

6

左边 右边

5 2 1 4 9 8

左边数组:

middle:5 1 2 4 5

left:2 1 4 right:0

middle:2 1 2 4

left:1 right:4

middle:1 1

left:1

左边退出外层,最终的结果是1 2 4 5

右边数组:

middle:9 8 9

left:8

右边退出外层,最终的结果是8 9

左边数组: 1 2 4 5

右边数组: 8

middle:9

最后结果是:1 2 4 5 8 9

复杂度:

在平均状况下,排序{displaystyle n}n个项目要{displaystyle O(nlog n)}{displaystyle O(nlog n)}(大O符号)次比较。在最坏状况下则需要{displaystyle O(n^{2})}{displaystyle O(n^{2})}次比较,但这种状况并不常见。事实上,快速排序{displaystyle Theta (nlog n)}{displaystyle Theta (nlog n)}通常明显比其他算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地达成。

标签: PHP

非特殊说明,本博所有文章均为博主原创。

评论啦~