重复第二步，直到所有元素均排序完毕。
PHP代码实现：
function selectSort($arr)
{
$len = count($arr);
for ($i = 0; $i < $len; $i++) {
$p = $i;
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$p] > $arr[$j]) {
$p = $j;
}
}
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
return $arr;
}
5 归并排序
归并排序是建立在归并操作上的一种有效的排序算法。
归并排序将待排序的序列分成若干组，保证每组都有序，然后再进行合并排序，最终使整个序列有序。
该算法是采用分治法的一个非常典型的应用。
算法步骤：
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
排序效果：
PHP实现代码：
/**
* 归并排序
*
* @param array $lists
* @return array
*/
function merge_sort(array $lists)
{
$n = count($lists);
if ($n <= 1) {
return $lists;
}
$left = merge_sort(array_slice($lists, 0, floor($n / 2)));
$right = merge_sort(array_slice($lists, floor($n / 2)));
$lists = merge($left, $right);
return $lists;
}
function merge(array $left, array $right)
{
$lists = [];
$i = $j = 0;
while ($i < count($left) && $j < count($right)) {
if ($left[$i] < $right[$j]) {
$lists[] = $left[$i];
$i++;
} else {
$lists[] = $right[$j];
$j++;
}
}
$lists = array_merge($lists, array_slice($left, $i));
$lists = array_merge($lists, array_slice($right, $j));
return $lists;
}
6 堆排序
堆排序是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆排序的平均时间复杂度为Ο(nlogn) 。
算法步骤：
创建一个堆H[0..n-1]；
把堆首（最大值）和堆尾互换；
把堆的尺寸缩小1，并调用shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
重复步骤2，直到堆的尺寸为1。
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);
}
}
