您的位置：首页 > 编程学习 > > 正文

排序算法口诀php（PHP快速排序算法实现的原理及代码详解）

更多 时间：2022-03-31 22:15:55 类别：编程学习 浏览量：666

排序算法口诀php

PHP快速排序算法实现的原理及代码详解

算法原理

下列动图来自五分钟学算法，演示了快速排序算法的原理和步骤。

排序算法口诀php（PHP快速排序算法实现的原理及代码详解）

步骤:

从数组中选个基准值

将数组中大于基准值的放同一边、小于基准值的放另一边，基准值位于中间位置

递归的对分列两边的数组再排序

代码实现

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
    		•
  • 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);
  •  
  • }
    		•

    测试代码:

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
    		•
  • $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";
    		•

    测试结果:

  • ?
  • 1
  • 2
  • 3
  • 4
  • 5
    		•
  • 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
    		•

    时间复杂度

    快速排序的时间复杂度在最坏情况下是o(n2)，平均的时间复杂度是o(n*lgn)。

    这句话很好理解：假设被排序的数列中有n个数。遍历一次的时间复杂度是o(n)，需要遍历多少次呢？至少lg(n+1)次，最多n次。

    1) 为什么最少是lg(n+1)次？快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(n+1)。因此，快速排序的遍历次数最少是lg(n+1)次。

    2) 为什么最多是n次？这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是n。因此，快读排序的遍历次数最多是n次。

    标签：PHP 快速排序
  • 上一篇：php运算符与操作符（php中的buffer缓冲区用法分析）
  • 下一篇：python删除数据框重复变量（Python3删除排序数组中重复项的方法分析）
    • 您可能感兴趣
    首页 编程学习 Web前端 数据库 软件设计
    开心学习 ©2013-2021 保留所有权利