排序算法

快速排序

选择一个基准元素，通常选择第一个元素或者最后一个元素。通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。

function quicksort($arr)
{
//判断参数是否是一个数组
    if(!is_array($arr)) return false;
//递归出口:数组长度为1，直接返回数组
    $length = count($arr);
    if($length<=1) return $arr;
//数组元素有多个,则定义两个空数组
    $left = $right = array();
//使用for循环进行遍历，把第一个元素当做比较的对象
    for($i=1; $i<$length; $i++)
    {
//判断当前元素的大小
        if($arr[$i]<$arr[0]){
            $left[]=$arr[$i];
        }else{
            $right[]=$arr[$i];
        }
    }
//递归调用
    $left=quicksort($left);
    $right=quicksort($right);
//将所有的结果合并
    return array_merge($left,array($arr[0]),$right);
}

插入排序

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

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;
}

选择排序

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

function selectsort($arr) {
//$i 当前最小值的位置， 需要参与比较的元素
    for($i=0, $len=count($arr); $i<$len-1; $i++) {
//先假设最小的值的位置
        $p = $i;
//$j 当前都需要和哪些元素比较，$i 后边的。
        for($j=$i+1; $j<$len; $j++) {
//$arr[$p] 是 当前已知的最小值
            if($arr[$p] > $arr[$j]) {
//比较，发现更小的,记录下最小值的位置；并且在下次比较时，应该采用已知的最小值进行比较。
                $p = $j;
            }
        }

//已经确定了当前的最小值的位置，保存到$p中。
//如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可
        if($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
//返回最终结果
    return $arr;
}

冒泡排序

在要排序的一组数中，对当前还未排好的序列，从前往后对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即，每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换

function bubbleSort ($arr)
{
    $len = count($arr);
//该层循环控制 需要冒泡的轮数
    for ($i=1; $i<$len; $i++) {
//该层循环用来控制每轮 冒出一个数 需要比较的次数
        for ($k=0; $k<$len-$i; $k++) {
            if($arr[$k] > $arr[$k+1]) {
                $tmp = $arr[$k+1]; // 声明一个临时变量
                $arr[$k+1] = $arr[$k];
                $arr[$k] = $tmp;
            }
        }
    }
    return $arr;
}

思路分析：希尔排序是基于插入排序的，区别在于插入排序是相邻的一个个比较（类似于希尔中h=1的情形），
而希尔排序是距离h的比较和替换。
希尔排序中一个常数因子n，原数组被分成各个小组，每个小组由h个元素组成，很可能会有多余的元素。
当然每次循环的时候，h也是递减的（h=h/n）。第一次循环就是从下标为h开始。
希尔排序的一个思想就是，分成小组去排序

function shellsort(array $arr){
    // 将$arr按升序排列
    $len = count($arr);
    $f = 3;// 定义因子
    $h = 1;// 最小为1
    while ($h < $len/$f){
        $h = $f*$h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
    }
    while ($h >= 1){  // 将数组变为h有序
        for ($i = $h; $i < $len; $i++){  // 将a[i]插入到a[i-h], a[i-2*h], a[i-3*h]... 之中 （算法的关键)
            for ($j = $i; $j >= $h;  $j -= $h){
                if ($arr[$j] < $arr[$j-$h]){
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j-$h];
                    $arr[$j-$h] = $temp;
                }
                //print_r($arr);echo '<br/>'; // 打开这行注释，可以看到每一步被替换的情形
            }
        }
        $h = intval($h/$f);
    }
    return $arr;
}