计算数组乘积，array_product()
- 直接插入排序（Straight Insertion Sort）
- 希尔排序（Shells Sort）
- 直接选择排序（Straight Selection Sort）
- 堆排序（Heap Sort）
- 冒泡排序（Bubble Sort）
- 快速排序（Quick Sort）
- 归并排序（Merge Sort）
- 桶排序（Bucket Sort）/基数排序（Radix Sort）
- 各种排序算法性能比较
排序有内部排序和外部排序之分，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。我们这里说的八大排序算法均为内部排序。
1.直接插入算法
// 第一种
function insert_sort($arr){
for ($i = 0; $i < count($arr)-1; $i++){
for($j = $i+1; $j > 0; $j--){
if($arr[$j] > $arr[$j-1]){
$temp = $arr[$j];
$arr[$j] = $arr[$j-1];
$arr[$j-1] = $temp;
}
}
}
return $arr;
}
$insert_sort = insert_sort([19, 22, 20, 12, 13, 15, 25, 26]);
var_dump($insert_sort);
// 第二种
function insert_sort($arr){
for ($i = 0; $i < count($arr)-1; $i++){
$j = $i + 1;
while($j > 0){
if($arr[$j] > $arr[$j-1]){
$temp = $arr[$j];
$arr[$j] = $arr[$j-1];
$arr[$j-1] = $temp;
}
$j--;
}
}
return $arr;
}
// 第三种
function insertSort($arr)
{
$len=count($arr);
for($i=1; $i<$len; $i++) {
// 获得当前需要比较的元素值。
$tmp = $arr[$i];
// 内层循环控制 比较 并 插入
for($j=$i-1; $j>=0; $j--) {
// $arr[$i]; 需要插入的元素; $arr[$j]; 需要比较的元素
if($tmp < $arr[$j]) {
// 发现插入的元素要小，交换位置
// 将后边的元素与前面的元素互换
$arr[$j+1] = $arr[$j];
// 将前面的数设置为 当前需要交换的数
$arr[$j] = $tmp;
} else {
// 如果碰到不需要移动的元素
// 由于是已经排序好是数组，则前面的就不需要再次比较了。
break;
}
}
}
// 将这个元素 插入到已经排序好的序列内。
return $arr;
}
2.希尔排序
3.直接选择排序
function selectSort($arr)
{
$len=count($arr);
for ($i = 0; $i < $len-1; $i++){
// 先假设最小的值的位置
$p = $i;
for ($j = $i+1; $j < $len; $j++){
// $arr[$p]是当前已知的最小值
if ($arr[$p] > $arr[$j]){
// 发现更小的记录一下次使用
$p = $j;
}
}
if ($p != $i){
$tmp = $arr[$p];
$arr[$p] = $arr[$i];
$arr[$i] = $tmp;
}
}
return $arr;
}
4.堆排序
5.冒泡排序法的基本思想是：对待排序记录关键字从后往前（逆序）进行多遍扫描，当发现相邻两个关键字的次序与排序要求的规则不符时，就将这两个记录进行交换。这样，关键字较小的记录将逐渐从后面向前面移动，就象气泡在水中向上浮一样，所以该算法也称为气泡排序法。
// 冒泡排序
function bubbleSort($arr)
{
$len = count($arr);
// 该层循环控制 需要冒泡的轮数
for ($i=1; $i<$len; $i++) {
// 该层循环用来控制每轮 冒出一个数 需要比较的次数
for ($j=0; $j<$len-$i; $j++) {
if($arr[$j] > $arr[$j+1]) {
$tmp = $arr[$j+1]; // 声明一个临时变量
$arr[$j+1] = $arr[$j];
$arr[$j] = $tmp;
}
}
}
return $arr;
}
6.快速排序算法
function quickSort($arr)
{
if (!is_array($arr)) return false;
$len = count($arr);
if ($len <= 1) return $arr;
$a = $b = array();
for ($i = 1; $i < $len; $i++){
if ($arr[$i] < $arr[0]){
$a[] = $arr[$i];
}else{
$b[] = $arr[$i];
}
}
$a = quickSort($a);
$b = quickSort($b);
return array_merge($a, array($arr[0]), $b);
}
7.归并排序算法【注意：数组按值传输】
function merge_sort(&$A, $p, $r)
{
if($p < $r){
$q = floor(($p + $r)/2);
merge_sort($A, $p, $q);
merge_sort($A, $q+1, $r);
merge($A, $p, $q, $r);
}
}
function merge(&$A, $p, $q, $r)
{
// 哨兵牌法
$n1 = $q - $p + 1;
$n2 = $r - $q;
for($i = 0; $i < $n1; $i++){
$L[$i] = $A[$p+$i];
}
for($j = 0; $j < $n2; $j++){
$R[$j] = $A[$q+$j+1];
}
// 防止越界(哨兵)
$L[$n1] = $R[$n2] = PHP_INT_MAX;
$i = $j = 0;
for($k = $p; $k <= $r; $k++){
if($L[$i] <= $R[$j]){
$A[$k] = $L[$i];
$i++;
}else{
$A[$k] = $R[$j];
$j++;
}
}
}
8.基数排序算法
