1. 云栖社区>
  2. PHP教程>
  3. 正文

快速排序法一窥 - 我读书少

作者:用户 来源:互联网 时间:2017-12-01 11:35:49

快速排序法一窥 - 我读书少 - 摘要: 本文讲的是快速排序法一窥 - 我读书少, 快速排序法作为一种分治法的算法,在原理上简单总结就是: 切分: 拿数组第一个数(也可以是随机任意一个)作为中心点(pivot); 扫描其它所有数,将小于这个中心点的数归类到左边,大于中心点的归类到右边; 将左边(右边)的所有数字递归第一步

快速排序法作为一种分治法的算法,在原理上简单总结就是:

切分:

拿数组第一个数(也可以是随机任意一个)作为中心点(pivot);

扫描其它所有数,将小于这个中心点的数归类到左边,大于中心点的归类到右边;

将左边(右边)的所有数字递归第一步,一直分叉;

合并:

当数组只有一个数的时候,递归结束,开始返回,每次返回都在中心点左右合并。

这里拿网上找来的一段PHP代码进行解释:

<?phpset_time_limit(10);function quicksort($seq) {if (count($seq) > 1) {$k = $seq[0];$x = array();$y = array();for ($i=1; $i<count($seq); $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); //递归逐层回溯的时候,进行merge动作}else{return $seq;  //递归终点,开始逐层返回数组}}$arr = array(12,2,16,30,8,28,4,10,20,6,18);print_r(quicksort($arr));?

还在网上看到一些改进版的快排算法,比如说前后来回扫描进行填坑,以避免单边数组量过大,但是原理是一样的,都是基于pivot.

这里给出wikipedia上的演示图和算法复杂度,看上去会更加直观形象。

快速排序法一窥 - 我读书少

使用快速排序法對一列數字進行排序的過程

分類 排序算法
數據結構 不定
最差時間複雜度 快速排序法一窥 - 我读书少
最優時間複雜度 快速排序法一窥 - 我读书少
平均時間複雜度 快速排序法一窥 - 我读书少
最差空間複雜度 根據實現的方式不同而不同

以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索 ,以便于您获取更多的相关知识。