欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

PHP快速排序算法實現(xiàn)的原理及代碼詳解

 更新時間：2019年04月03日 08:29:04   投稿：laozhang  
在本篇文章里小編給大家整理了關(guān)于PHP快速排序算法實現(xiàn)的原理及代碼相關(guān)知識點，需要的朋友們跟著學(xué)習(xí)下。

算法原理

下列動圖來自五分鐘學(xué)算法，演示了快速排序算法的原理和步驟。

步驟:

從數(shù)組中選個基準(zhǔn)值

將數(shù)組中大于基準(zhǔn)值的放同一邊、小于基準(zhǔn)值的放另一邊，基準(zhǔn)值位于中間位置

遞歸的對分列兩邊的數(shù)組再排序

代碼實現(xiàn)

function quickSort($arr)

{

 $len = count($arr);

 if ($len <= 1) {

  return $arr;

 }

 

 $v = $arr[0];

 $low = $up = array();

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

  if ($arr[$i] > $v) {

   $up[] = $arr[$i];

  } else {

   $low[] = $arr[$i];

  }

 }

 $low = quickSort($low);

 $up = quickSort($up);

 

 return array_merge($low, array($v), $up);

}

測試代碼:

$startTime = microtime(1);

 

$arr = range(1, 10);

shuffle($arr);

 

echo "before sort: ", implode(', ', $arr), "\n";

$sortArr = quickSort($arr);

echo "after sort: ", implode(', ', $sortArr), "\n";

 

echo "use time: ", microtime(1) - $startTime, "s\n";

測試結(jié)果:

before sort: 1, 7, 10, 9, 6, 3, 2, 5, 4, 8

after sort: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

use time: 0.0009009838104248s

時間復(fù)雜度

快速排序的時間復(fù)雜度在最壞情況下是O(N2)，平均的時間復(fù)雜度是O(N*lgN)。

這句話很好理解：假設(shè)被排序的數(shù)列中有N個數(shù)。遍歷一次的時間復(fù)雜度是O(N)，需要遍歷多少次呢？至少lg(N+1)次，最多N次。

1) 為什么最少是lg(N+1)次？快速排序是采用的分治法進行遍歷的，我們將它看作一棵二叉樹，它需要遍歷的次數(shù)就是二叉樹的深度，而根據(jù)完全二叉樹的定義，它的深度至少是lg(N+1)。因此，快速排序的遍歷次數(shù)最少是lg(N+1)次。

2) 為什么最多是N次？這個應(yīng)該非常簡單，還是將快速排序看作一棵二叉樹，它的深度最大是N。因此，快讀排序的遍歷次數(shù)最多是N次。

相關(guān)文章

最新評論