PHP 快速排序

2020-11-17 08:00 PHP在线

曾经在一次面试中,面试官问过我这个算法,我当时一脸懵逼,就说它比较快,所以就是快速排序,至于怎么快的一问三不知。所谓吃一堑长一智嘛,不管你怎么理解,最终还不得反应到代码实现上么?不费话了,上代码。


概念

快速排序 - Quick Sort:又称划分交换排序 - partition-exchange sort,简称快排,一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n^2) 次比较,但这种状况并不常见。事实上,快速排序 O(n log n) 通常明显比其他算法更快,因为它的内部循环 (inner loop)可以在大部分的架构上很有效率地达成。

步骤

  1. 从数列中挑出一个元素,称为『基准』- pivot

  2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作

  3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序

实现

方案一

<?php
class QuickSort{ /** * 主运行方法 * * @return void */ public static function main(): void{ $random = self::random(); $array = self::sort($random); print_r($array); }
/** * 快速排序 * * @param array $array * * @return array */ public static function sort(array &$array): array{ $count = count($array);
if ($count <= 1) { return $array; }
$pivot = $array[0]; // 取数组第一个元素为基准值
$left = $right = [];
for ($i = 1; $i < $count; $i++) { $value = $array[$i]; if (self::compare($pivot, $value) > 0) { $left[] = $array[$i]; } else { $right[] = $array[$i]; } } $left = self::sort($left); $right = self::sort($right);
return array_merge($left, (array)$pivot, $right); }
/** * 比较大小 * * @param int $x * @param int $y * * @return int */ private static function compare(int $x, int $y): int{ return $x <=> $y; }
/** * 互换位置 * * @param int $x * @param int $y * * @return void */ private static function swap(int &$x, int &$y): void{ if ($x !== $y) { $t = $x; $x = $y; $y = $t; } }
/** * 生成随机数组 * * @param int $low * @param int $high * @param int $num * * @return array */ private static function random(int $low = 1, int $high = 9999, int $num = 10): array{ $num = $num > $high ? $high : $num; $range = range($low, $high); $array = array_rand(array_flip($range), $num); shuffle($array);
return $array; }}
QuickSort::main();
// 结果Array( [0] => 1073 [1] => 1535 [2] => 3376 [3] => 3702 [4] => 3961 [5] => 4139 [6] => 4644 [7] => 5032 [8] => 5803 [9] => 6450)

方案二

使用 Lomuto partition scheme 方式

<?php
class QuickSort{ /** * 主运行方法 * * @return void */ public static function main(): void{ $random = self::random(); $array = self::sort($random, 0, count($random) - 1); print_r($array); }
/** * 快速排序 * * @param array $array * @param int $low * @param int $high * * @return array */ public static function sort(array &$array, int $low, int $high): array{ if ($low < $high) { $index = self::partition($array, $low, $high); self::sort($array, $low, $index - 1); self::sort($array, $index + 1, $high); }
return $array; }
/** * 原地分区 * * @param array $array * @param int $low * @param int $high * * @return int */ private static function partition(array &$array, int $low, int $high): int{ $pivot = $array[$high]; // 选取最右边的元素为基准 $i = $low - 1;
for ($j = $low; $j < $high; $j++) { if (self::compare($pivot, $array[$j]) > 0) { $i++; self::swap($array[$i], $array[$j]); } } self::swap($array[$i + 1], $array[$high]);
return $i + 1; }
/** * 比较大小 * * @param int $x * @param int $y * * @return int */ private static function compare(int $x, int $y): int{ return $x <=> $y; }
/** * 互换位置 * * @param int $x * @param int $y * * @return void */ private static function swap(int &$x, int &$y): void{ if ($x !== $y) { $t = $x; $x = $y; $y = $t; } }
/** * 生成随机数组 * * @param int $low * @param int $high * @param int $num * * @return array */ private static function random(int $low = 1, int $high = 9999, int $num = 10): array{ $num = $num > $high ? $high : $num; $range = range($low, $high); $array = array_rand(array_flip($range), $num); shuffle($array);
return $array; }}
QuickSort::main();
// 结果Array( [0] => 1411 [1] => 3434 [2] => 3776 [3] => 6020 [4] => 6047 [5] => 6367 [6] => 7107 [7] => 7783 [8] => 9135 [9] => 9248)

本文章转载自公众号:phpdaily

首页 - PHP 相关的更多文章: