本文主要介绍了一些常用的排序算法，以及PHP的代码实现等，希望对您能有所帮助。
本文来自于awaimai.com,由火龙果软件Luca编辑推荐。
作为phper，一般接触算法的编程不多。
但基本的排序算法还是应该掌握。
毕竟算法作为程序的核心，算法的好坏决定了程序的质量。
本文将依次介绍一些常用的排序算法，以及PHP实现。
1 快速排序
快速排序是由东尼·霍尔发展的一种排序算法。
在平均状况下，排序 n 个项目要Ο(n log n)次比较。
在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。
事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环可以在大部分的架构上，很有效率地被实现出来。
快速排序采用分治法实现排序，具体步骤：
从数列中挑出一个数作为基准元素。通常选择第一个或最后一个元素。
扫描数列，以基准元素为比较对象，把数列分成两个区。规则是：小的移动到基准元素前面，大的移到后面，相等的前后都可以。分区完成之后，基准元素就处于数列的中间位置。
然后再用同样的方法，递归地排序划分的两部分。
递归的结束条件是数列的大小是0或1，也就是永远都已经被排序好了。
PHP代码实现：
function quickSort($arr)
{
$len = count($arr);
// 先设定结束条件，判断是否需要继续进行
if($len <= 1) {
return $arr;
}
// 选择第一个元素作为基准元素
$pivot = $arr[0];
// 初始化左数组
$left = $right = array();
// 初始化大于基准元素的右数组
$right = array();
// 遍历除基准元素外的所有元素，按照大小关系放入左右数组内
for ($i = 1; $i < $len ; $i++) {
if ($arr[$i] < $pivot) {
$left[] = $arr[$i];
} else {
$right[] = $arr[$i];
}
}
// 再分别对左右数组进行相同的排序
$left = quickSort($left);
$right = quickSort($right);
// 合并基准元素和左右数组
return array_merge($left, array($pivot), $right);
}
原地排序版本，不需要额外的存储空间：
function partition(&$arr, $leftIndex, $rightIndex)
{
$pivot = $arr[($leftIndex + $rightIndex) / 2];
while ($leftIndex <= $rightIndex) {
while ($arr[$leftIndex] < $pivot) {
$leftIndex++;
}
while ($arr[$rightIndex] > $pivot) {
$rightIndex--;
}
if ($leftIndex <= $rightIndex) {
list($arr[$leftIndex], $arr[$rightIndex]) = [$arr[$rightIndex], $arr[$leftIndex]];
$leftIndex++;
$rightIndex--;
}
}
return $leftIndex;
}
function quickSort(&$arr, $leftIndex, $rightIndex)
{
if ($leftIndex < $rightIndex) {
$index = partition($arr, $leftIndex, $rightIndex);
quickSort($arr, $leftIndex, $index - 1);
quickSort($arr, $index, $rightIndex);
}
}
内容版权声明：除非注明，否则皆为本站原创文章。