search
Homephp教程PHP源码递归与迭代同时实现php快速排序

php代码

/**
 * 递归法实现的快速排序
 * @param $seq
 * @return array
 */
function quicksort($seq)
{
    if (count($seq) > 1) {
        $k = $seq[0];
        $x = array();
        $y = array();
        $_size = count($seq); //do not use count($seq) in loop for.
        for ($i = 1; $i < $_size; $i++) {
            if ($seq[$i] <= $k) {
                $x[] = $seq[$i];
            } else {
                $y[] = $seq[$i];
            }
        }
        $x = quicksort($x);
        $y = quicksort($y);
        return array_merge($x, array($k), $y);
    } else {
        return $seq;
    }
}

/**用迭代实现
 * @param $seq
 * @return array
 */
function quicksortX(&$seq)
{
    $stack = array($seq);
    $sort = array();
    while ($stack) {
        $arr = array_pop($stack);
        if(count($arr) <= 1){
            if (count($arr) == 1) {
                $sort[] = &$arr[0];
            }
            continue;
        }

        $k = $arr[0];
        $x = array();
        $y = array();
        $_size = count($arr);
        for ($i = 1; $i < $_size; $i++) {
            if ($arr[$i] <= $k) {
                $x[] = &$arr[$i];
            } else {
                $y[] = &$arr[$i];
            }
        }
        !empty($y) && array_push($stack, $y);
        array_push($stack, array($arr[0]));
        !empty($x) && array_push($stack, $x);
    }
    return $sort;
}
//$testArr = array(5545, 5, 6, 7675, 100, 9, 233, 566, 789, 456, 23, 55, 7, 4, 343, 564, 5, 45657, 8, 998, 9, 34, 34, 55, 6, 5, 6433, 67, 6, 6766, 4, 2, 42, 25634, 34343, 3, 3, 454, 4, 65, 6678, 57, 5455);
for($i=0;$i<20;$i++){
    $testArr[]=mt_rand(0,10000);
}
//var_dump($testArr);
echo count($testArr).&#39;
&#39;;
$start=microtime();
echo count(quicksort($testArr)).&#39;
&#39;;
echo microtime()-$start.&#39;
&#39;;
var_dump(quicksort($testArr));
echo &#39;------------------------------------------------------------------------
&#39;;
echo count($testArr).&#39;
&#39;;
$start=microtime();
echo count(quicksortX($testArr)).&#39;
&#39;;
echo microtime()-$start.&#39;
&#39;;
var_dump(quicksortX($testArr));

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
1 months agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

Powerful PHP integrated development environment

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools