当前位置: 首页 > 文章 > PHP快速排序算法

PHP快速排序算法

[ PHP ] 2019-12-28 22:43:11 杨歆 438
<?php

/**
 * 顾名思义,这是实践中的一种快速的排序算法,它平均运行实践是O(N log N)。
 * 该算法之所以特别快,主要是由于非常精炼和高度优化的内部循环。
 * 它的最坏情形性能为O(N^2)。像归并排序一样,快速排序也是一种分治的递归算法。
 * 步骤:
 * 1、从数列中挑出一个元素,称为"基准"(pivot)
 * 2、重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面。
 * 在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
 * 3、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
 */

$array = [1, 3, 34, 2, 32, 2, 78, 43, 53, 35, 10, 70, 89, 102, 60];

function quickSort($array){
    $count = count($array);
    if ($count < 2) {
        return $array;
    }
    //创建临时数组,以基准值为分界线,大于基准值的放在右侧,小鱼基准值的放在左侧
    $leftArray = $rightArray = [];
    //基准值,一般取数组第一个元素
    $middle = $array[0];
    //循环数组与基准值比较
    for ($i = 1; $i < $count; $i++) {
        if ($array[$i] < $middle) {
            $leftArray[] = $array[$i];
        } else {
            $rightArray[] = $array[$i];
        }
    }
    //递归,将左右数组排序
    $leftArray = quickSort($leftArray);
    $rightArray = quickSort($rightArray);
    //将排好序的临时数组合并
    return array_merge($leftArray, array($middle), $rightArray);
}

var_dump(quickSort($array));
支付宝支付
打赏
微信支付

联系我吧

有些人是会淡出你的生活的,有些人刻意不再联系,是因为你知道ta不需要你,或者从一开始就不是同一个初衷在一起度过,不主动联系很久也不见一次面,所有的感情也罢,都会败给时间和距离。因为时间是最无情,给你后悔的时刻却不会给你改过重来的机会。

位置

成都市 四川省 中国

联系电话

028-6406-0000

邮箱

y139w@163.com

企鹅

27572048

网址

https://www.weania.com