백엔드 개발 PHP 튜토리얼 php实现快速排序的三种方法_PHP教程

php实现快速排序的三种方法_PHP教程

Jul 13, 2016 am 10:36 AM
php 기본 성취하다 빠른 종류 기사 방법 ~의

这篇文章主要介绍了php实现快速排序的三种方法,三种方法各有优缺点,需要的朋友可以参考下

写了三种php快速排示例,第一种效率低但最简单最容易理解,第二个是算法导论上提供的单向一次遍历找中值方法,第三种是双向遍历找中值经典快排算法。三组算法实现和比较如下:

 

方法一:该方法比较直观,但损失了大量的空间为代价,使用了效率较低的merge函数。在三种方法中效率最低。最坏情况下算法退化为(O(n*n))

 代码如下:

function quick_sort($array) {

 if(count($array)

 $key = $array[0];

 $rightArray = array();

 $leftArray = array();

 for($i = 1; $i

           if($array[$i] >= $key) {

  $rightArray[] = $array[$i];

    } else {

  $leftArray[] = $array[$i];

    }

 }

 $leftArray = quick_sort($leftArray);

 $rightArray = quick_sort($rightArray);

 return array_merge($leftArray, array($key), $rightArray);

}

 

 

 

方法二:该算法来自算法导论,叫作Nico Lomuto方法(感兴趣goole上有详细说明)使用最经典的单方向一次遍历找到中值。

但这种算法在最坏情况下(例如值相同的数组,需要n-1次划分,每一次划分需要O(n) 时间去掉一个元素)最坏情况下为O(n*n)

代码如下:

function quick_sort(&$array, $start, $end) {

    if ($start >= $end) return;

    $mid = $start;

    for ($i = $start + 1; $i

 if ($array[$i]

     $mid++;

     $tmp = $array[$i];

     $array[$i] = $array[$mid];

     $array[$mid] = $tmp;

 }

    }

    $tmp = $array[$start];

    $array[$start] = $array[$mid];

    $array[$mid] = $tmp;

    quick_sort($array, $start, $mid - 1);

    quick_sort($array, $mid + 1, $end);

}

 

 

方法三:该方法基本上是教科书式的常见写法,首先从左向右遍历小于中间元素的跳过,同时从右向左遍历遇到大的元素跳过,然后

 

如果没有交叉着交换两边值,继续循环,直到找到中间点。注意该方法在处理相同元素的时候,仍旧交换,这样在最坏情况下也有O(nlogn)

 

效率。但下面的函数中,如果将$array[$right] > $key 改成 $array[$right] >=$key 或将 $array[$left]

 

情况不但会堕落为O(n*n).而且除了每次比较的消耗外,还会产生n次交互的额外开销。该题还有另外两个考点,针对死记硬背的同学:

 

1:中间的两个while可否互换。当然不能互换,因为对于快盘需要一个额外的空间保存初始的左值,这样左右互换的时候,先用右边覆盖已经保存

 

为中值的左值,否则会出现问题。见这句$array[$left] = $array[$right];

 

2:$array[$right] = $key; 该语句含义可否省略。该句不能省略,大家可以考虑一个极端情况比如两个值的排序(5,2),逐步看下就明白了。

 代码如下:

function quick_sort_swap(&$array, $start, $end) {

 if($end

 $key = $array[$start];

 $left = $start;

 $right = $end;

 while($left

  while($left $key)

   $right--;

  $array[$left] = $array[$right];

  while($left

   $left++;

  $array[$right] = $array[$left];

 }

 $array[$right] = $key;

 quick_sort_swap(&$array, $start, $right - 1);

 quick_sort_swap(&$array, $right+1, $end);

}

 

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/740818.htmlTechArticle这篇文章主要介绍了php实现快速排序的三种方法,三种方法各有优缺点,需要的朋友可以参考下 写了三种php快速排示例,第一种效率低但最...
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

뜨거운 기사 태그

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드 Dec 24, 2024 pm 04:42 PM

Ubuntu 및 Debian용 PHP 8.4 설치 및 업그레이드 가이드

CakePHP 날짜 및 시간 CakePHP 날짜 및 시간 Sep 10, 2024 pm 05:27 PM

CakePHP 날짜 및 시간

CakePHP 파일 업로드 CakePHP 파일 업로드 Sep 10, 2024 pm 05:27 PM

CakePHP 파일 업로드

CakePHP 라우팅 CakePHP 라우팅 Sep 10, 2024 pm 05:25 PM

CakePHP 라우팅

CakePHP 프로젝트 구성 CakePHP 프로젝트 구성 Sep 10, 2024 pm 05:25 PM

CakePHP 프로젝트 구성

CakePHP 토론 CakePHP 토론 Sep 10, 2024 pm 05:28 PM

CakePHP 토론

CakePHP 빠른 가이드 CakePHP 빠른 가이드 Sep 10, 2024 pm 05:27 PM

CakePHP 빠른 가이드

PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법 PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법 Dec 20, 2024 am 11:31 AM

PHP 개발을 위해 Visual Studio Code(VS Code)를 설정하는 방법

See all articles