PHP排序算法

1. 冒泡排序法
   在要排序的一组数中，对当前还未排好的序列，从前往后对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒，故名冒泡。

function bubbleSort1 ($a) {
    $c = count($a);
    for ($i=1; $i < $c; $i++) { 
        //该层循环控制 需要冒泡的轮数，即，数组长度-1 
        for ($j=0; $j < $c-$i; $j++) { 
            //该层循环控制 每轮冒泡的次数，即，数组长度-轮次
            if ($a[$j] > $a[$j+1]) {
                list($a[$j],$a[$j+1]) = [$a[$j+1],$a[$j]];
            }
        }
    }
    return $a;
}

2. 选择排序法
   在要排序的一组数中，选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。

function selSort($arr){
    $num=count($arr);
    for($i = 0; $i< $num -1; $i++){
        for($j=$i+1; $j<$num;$j++){
            if($arr[$i] > $arr[$j]){
            list($arr[$i],$arr[$j]) = [$arr[$j], $arr[$i]];
            }
        }
    }
    return $arr;
}
$arr = [2,6,2,8,2,34,5,9,2341,23];
print_r(selSort($arr));

3. 插入排序
   在要排序的一组数中，假设前面的数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

function insertSort($a) {
    $c = count($a);
    for ($i=1; $i < $c; $i++) {
        for ($j=$i-1; $j>=0 ; $j--) { 
            if ($a[$j]>$a[$j+1]) {
                list($a[$j+1],$a[$j]) = [$a[$j],$a[$j+1]];
            } else {
                break;
            }
        }
    }
    return $a;
}

4、二分查找法
二分查找也称折半查找（Binary Search），时间复杂度O(logn)，是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

function binarySearch($a, $n) {
    $c = count($a);
    if ($c < 1) {
        return -1;
    }
    if ($c === 1) {
        return $a[0] == $n ? 0 : -1;
    }
    $min = 0;
    $max = $c -1;
    $k = -1;
    while ($min <= $max) {
        $mid = intval(($min+$max)/2);
        if ($a[$mid] > $n) {
            $max = $mid - 1;
        } else if ($a[$mid] < $n) {
            $min = $mid + 1;
        } else {
            $k = $mid;
            break;
        }
    }
    return $k;
}
$astr = '12356789';
$a = str_split($astr);
var_dump(binarySearch($a, 8));

5、快速排序
顾名思义，这是实践中的一种快速的排序算法，它平均运行时间是O(N log N).该算法之所以特别快，主要是由于非常精炼和高度优化的内部循环。它的最坏情形性能为O(N^2)。像归并排序一样，快速排序也是一种分治的递归算法。其原理如下：

1、从数列中挑出一个元素，称为"基准"。（pivot）
2、重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3、递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

function quickSort($a) {
    $c = count($a);
    if (empty($a) || $c < 2) {
        return $a;
    }
    $larr = [];
    $rarr = [];
    $mid = $a[0];
    $midarr = [$mid];
    for ($i=1; $i < $c; $i++) { 
        if ($a[$i] > $mid) {
            $rarr[] = $a[$i];
        } else if ($a[$i] < $mid) {
            $larr[] = $a[$i];
        } else {
            $midarr[] = $a[$i];
        }
    }
    $larr = quickSort($larr);
    $rarr = quickSort($rarr);
    return array_merge($larr, $midarr, $rarr);
}
$arr = [1, 0, 8, 3, 4, 1, -6, 1, -10];
print_r(quickSort($arr));