PHP实现八大算法

计算数组乘积，array_product()

1. 直接插入排序（Straight Insertion Sort）
2. 希尔排序（Shells Sort）
3. 直接选择排序（Straight Selection Sort）
4. 堆排序（Heap Sort）
5. 冒泡排序（Bubble Sort）
6. 快速排序（Quick Sort）
7. 归并排序（Merge Sort）
8. 桶排序（Bucket Sort）/基数排序（Radix Sort）
9. 各种排序算法性能比较

排序有内部排序和外部排序之分，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。我们这里说的八大排序算法均为内部排序。
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.基数排序算法