PHP实现代码：
/**
* 堆排序
*
* @param array $lists
* @return array
*/
function heap_sort(array $lists)
{
$n = count($lists);
build_heap($lists);
while (--$n) {
$val = $lists[0];
$lists[0] = $lists[$n];
$lists[$n] = $val;
heap_adjust($lists, 0, $n);
//echo "sort: " . $n . "\t" . implode(', ', $lists) . PHP_EOL;
}
return $lists;
}
function build_heap(array &$lists)
{
$n = count($lists) - 1;
for ($i = floor(($n - 1) / 2); $i >= 0; $i--) {
heap_adjust($lists, $i, $n + 1);
//echo "build: " . $i . "\t" . implode(', ', $lists) . PHP_EOL;
}
//echo "build ok: " . implode(', ', $lists) . PHP_EOL;
}
function heap_adjust(array &$lists, $i, $num)
{
if ($i > $num / 2) {
return;
}
$key = $i;
$leftChild = $i * 2 + 1;
$rightChild = $i * 2 + 2;
if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) {
$key = $leftChild;
}
if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) {
$key = $rightChild;
}
if ($key != $i) {
$val = $lists[$i];
$lists[$i] = $lists[$key];
$lists[$key] = $val;
heap_adjust($lists, $key, $num);
}
}
7 希尔排序
希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。
但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
算法步骤：
先将整个待排序的记录序列分割成为若干子序列，分别进行直接插入排序
待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
PHP实现代码：
/**
* 希尔排序 标准
*
* @param array $lists
* @return array
*/
function shell_sort(array $lists)
{
$n = count($lists);
$step = 2;
$gap = intval($n / $step);
while ($gap > 0) {
for ($gi = 0; $gi < $gap; $gi++) {
for ($i = $gi; $i < $n; $i += $gap) {
$key = $lists[$i];
for ($j = $i - $gap; $j >= 0 && $lists[$j] > $key; $j -= $gap) {
$lists[$j + $gap] = $lists[$j];
$lists[$j] = $key;
}
}
}
$gap = intval($gap / $step);
}
return $lists;
}
8 基数排序
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。
由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。