- 冒泡排序
两数相较，大的数下沉，小的数上升。
function bubbleSort(array $arr){ for ($i=0, $len=count($arr); $i < $len; $i++) { $flag = false; for ($j=0; $j < $len-1; $j++) { if ($arr[$j] > $arr[$j+1]) { $tmp = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $tmp; $flag = true; } } // 若没有交换发生，提前终止; if ($flag == false) break; } return $arr;} - 选择排序
在长度为N的数组中，找到后面N-1个数中的最小值与第1个数字交换，后N-2中最小值与第2个交换，以此类推直至最后一个数。
function selectSort(array $arr){ for ($i=0, $len=count($arr); $i < $len-1; $i++) { $min_key = $i+1; for ($j=$i+1; $j < $len; $j++) { if ($arr[$j] < $arr[$min_key]) { $min_key = $j; } } if ($arr[$i] > $arr[$min_key]) { $tmp = $arr[$i]; $arr[$i] = $arr[$min_key]; $arr[$min_key] = $tmp; } } return $arr;}
- 插入排序
假设数组中前n-1是已排好序，将第n个数插入到前面使这n个数也是排好序的，如此从第一个数开始循环直至全部排好序。
function insertSort(array $arr){ for ($i=0, $len=count($arr); $i < $len-1; $i++) { for ($j=$i+1; $j > 0; $j--) { // 若后面的数比前面的小，则发生交换 if ($arr[$j] < $arr[$j-1]) { $tmp = $arr[$j]; $arr[$j] = $arr[$j-1]; $arr[$j-1] = $tmp; } } } return $arr;}
- 希尔排序
可以看做是一种分组插入排序，将数组按照某个增量进行排序，再将增量逐步减小，直至增量为1
function shellSort(array $arr){ $len = count($arr); $inc = round($len / 2); while (true) { for ($i=0; $i < $inc; $i++) { for ($j=$i+$inc; $j < $len; $j+=$inc) { for ($k=$j-$inc; $k >= $i; $k-=$inc) { if ($arr[$k] > $arr[$k+$inc]) { $tmp = $arr[$k]; $arr[$k] = $arr[$k+$inc]; $arr[$k+$inc] = $tmp; } } } } if ($inc == 1) break; $inc = round($inc / 2); } return $arr;}
- 快速排序
先从数组中选取1个数作为key值，将比key小的放在左边，大的放在右边。使用递归对key两端的数列作同样的操作。
function quickSort(array $arr, $left = null, $right = null){ $left = $left===null ? 0 : $left; $right = $right===null ? count($arr)-1 : $right; if ($left >= $right) { return $arr; } $key = $arr[$left]; $i = $left; $j = $right; while ($i < $j) { while ($i < $j && $arr[$j] >= $key) { $j--; } if ($i < $j) { $arr[$i] = $arr[$j]; $i++; } while ($i < $j && $arr[$i] < $key) { $i++; } if ($i < $j) { $arr[$j] = $arr[$i]; $j--; } } $arr[$i] = $key; $arr = quickSort($arr, $left, $i-1); $arr = quickSort($arr, $i+1, $right); return $arr;}
- 归并排序
有序数组的合并，将数列分解为最小单元，然后依次合并。
function mergeSort(array $arr){ $merge = $arr; while (true) { $tmp = []; $count = count($merge); if ($count == 1) { return $merge[0]; } for ($i=0; $i < $count; $i+=2) { if (isset($merge[$i+1])) { $tmp[] = arrayMerge($merge[$i], $merge[$i+1]); } else { $tmp[] = $merge[$i]; } } $merge = $tmp; }}function arrayMerge($a, $b){ if (!is_array($a) && !is_array($b)) { if ($a < $b) return [$a, $b]; else return [$b, $a]; } else { $c = []; $i = $j = $k = 0; $m = count($a); $n = count($b); while ($i<$m && $j<$n) { if($a[$i] < $b[$j]) $c[$k++] = $a[$i++]; else $c[$k++] = $b[$j++]; } while ($i < $m) { $c[$k++] = $a[$i++]; } while ($j < $n) { $c[$k++] = $b[$j++]; } return $c; }}
- 堆排序
堆是一种完全二叉树，分为大根堆和小根堆，大根堆要求每个节点的值不大于父节点的值，小根堆反之。堆排序就是利用这种数据结构设计的一种排序算法，它是选择排序的一种，可以利用数组的特点快速定位索引所在的元素。
function heapSort(array $arr){ $len = count($arr); for ($i=$len-1; $i >= 0; $i--) { $arr = buildHeap($arr, $len, $i); $arr = swap($arr, 0, $i); } return $arr;}// 建立堆，顺序逆序分拣建立大根堆小根堆function buildHeap($arr, $len, $lmt){ for ($i=intval($len/2)-1; $i >= 0; $i--) { $left = 2*$i+1; $right = 2*$i+2; if ($left > $lmt) continue; if ($right > $lmt) { $k = $left; } else { $k = $arr[$left]>$arr[$right] ? $left : $right; } if ($arr[$i] < $arr[$k]) { $arr = swap($arr, $i, $k); } } return $arr;}// 交换数据function swap($arr, $k1, $k2){ $tmp = $arr[$k1]; $arr[$k1] = $arr[$k2]; $arr[$k2] = $tmp; return $arr;}
- 基数排序
binSort将值作为键值放入对应的位置，然后直接遍历数组得到结果。当序列中存在较大值时，BinSort 的排序方法会浪费大量的空间开销。基数排序是在BinSort的基础上，通过基数的限制来减少空间的开销。基数排序的过程是将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
function radixSort(array $arr, $level=1){ // 采用LSD $limit = pow(10, $level); $div = pow(10, $level-1); $flag = false; $bucket = []; $ret = []; foreach ($arr as $v) { $bucket[intval($v/$div)%10][] = $v; if ($v >= $limit) $flag = true; } for ($i=0; $i < 10; $i++) { if (isset($bucket[$i])) { $ret = array_merge($ret, $bucket[$i]); } } if ($flag) { $ret = radixSort($ret, $level+1); } return $ret;}