function bubbleSort($array)
{
    //计算传入的数组的长度
    $length = count($array)
    //每一次循环，都会把最大的数据冒出到队尾
    for ($i = $length;$i > 0;$i--) {
        $swape = true;
        for ($j = 0; $j < $i - 1;$j++) {
            //相邻的两个做比较，满足条件的话做交换
            if ($array[$j]>$array[$j+1]){
                $temp=$array[$j];
                $array[$j]=$array[$j+1];
                $array[$j+1]=$temp;
                //当发生了交换，标记设为false
                $swape=false;
            }
        }
        //当标记没有变化时，说明整个序列都有序了，结束循环，
        if ($swape) {
            break;
        }
    }
    return $array;
} 

function bubbleSort(array $input)
{
    if(!isset($input))
    {
        return [];
    }

    do {
        $swapped = false;

        for($i = 0,$count = sizeof($input) - 1;$i < $count;$i++) {
            //也是交换
            if($input[$i + 1] < $input[$i]) {
                list($input[$i + 1],$input[$i]) = [$input[$i],$input[$i + 1]];
                $wrapped = true;
            }
        }
    } while($swapped);

    return $input;
}

//min和max是数组里的最小值和最大值
function countSort($array,$min,$max)
{
    $count = array();
    //对count进行标记，对min和max之间的位置进行置0
    for($i = $min;$i <= $max;$i++) {
        $count[$i] = 0;
    }

    //读取数组，读取一遍，把对应数字下标的count加一
    foreach($array as $number) {
        $count[$number]++;
    }
    //设置数组的访问下标为0，置0
    $z = 0;
    //遍历一遍count数组，遇见不为零的情况，则说明该处有数字，把下标存在array
    for($i = $min;$i <= $max;$i++) {
        while($count[$i] > 0) {
            $array[$z++] = $i;
        }
    }
    //但这样好像把重复的数字抹掉了？
    return $array;
}

function insertionSort(array $array)
{
    for ($i = 1;$i < count($array);$i++) {
        $currentVal = $array[$i];
        for ($j = $i - 1;$j >= 0&&$array[$j]>$currentVal;$j--) {
            $array[$j+1] = $array[$j];
        }
        $array[$j+1] = $currentVal;
    }
    return $array;
}

//处理两个数组的合并
function merge(array $arr1,array $arr2)
{
    $result = [];
    $i = 0;
    $j = 0;
    //用i，j来做arr的比较下标
    while($i < count($arr1) && j < count($arr2)) {
        //小的入数组
        if ($arr2[$j] > $arr1[$i]) {
            $result[] = $arr1[$i];
            $i++;
        } else {
            $result[] = $arr2[$j];
            $j++;
        }
    }
    //arr1还有数据，，不为空
    while ($i < count($arr1)) {
        $result[] = $arr1[$i];
        $i++;
    }
    //arr2还有数据，不为空
    while ($j < count($arr2)) {
        $result[] = $arr2[$j];
        $j++;
    }
    return $result;
}

function mergeSort(array $arr)
{
    //当数组长度不大于1时，返回数组
    if (count($arr) <= 1) {
        return $arr;
    }
    //取整
    $mid = floor(count($arr)/2);
    //还是接着切分数组
    $left = mergeSort(array_slice($arr,0,$mid));
    $right = mergeSort(array_slice($arr,$mid));

    //两个参数都是数组
    return merge($left,$right);
}

function quickSort(array $input)
{
    if (!isset($input)) {
        return [];
    }

    $lt = [];
    $gt = [];

    if (sizeof($input) < 2) {
        return $input;
    }

    $key = key($input);
    $shift = array_shift($input);

    foreach($input as $value) {
        $value <= $shift ? $lt[] = $value : $gt[] = $value;
    }

    return array_merge(quickSort($lt),[$key => $shift],quickSort($gt));
}

function getDigit($num,$i)
{
    return floor(abs($num)/pow(10,$i)) % 10;
}

function digitsCount($num)
{
    if ($num == 0) {
        return 1;
    }
    return floor(log10(abs($num)))+1;
}

function maxDigits($arr)
{
    $maxDigits = 0;
    for ($i = 0;$i < count($arr);$i++) {
        $maxDigits = max($maxDigits,digitsCount($arr[$i]));
    }
    return $maxDigits;
}

function radixSort($nums)
{
    $maxDigitsCount = maxDigits($nums);
    for ($k = 0;$k < $maxDigitsCount;$k++) {
        $digitBucket = array_fill(0,10,[]);

        for ($i = 0;$i < count($nums);$i++) {
            $digitBucket[getDigit($nums[$i],$k)][] $nums[$i];
        }

        $nums = concat($digitBucket);
    }
    return $nums;
}

function concat(array $array)
{
    $newArray = [];
    for ($i = 0;$j < count($count[$i]);$i++) {
        for ($j = 0;$j < count($array[$i]);$j++) {
            $newArray[] = $array[$i][$j];
        }
    }
    return $newArray;
}

function selectionSorting($array)
{
    $length = count($array);
    for ($i = 0;$i < $length;$i++) {
        $lowest = $i;
        for ($j = $i + 1;$j < length;$j++) {
            if ($array[$j] < $array[$lowest]) {
                $lowest = $j;
            }
        }
        if ($i !== $lowest) {
            $temp = $array[$i];
            $array[$i] = $array[$lowest];
            $array[$lowest] = $temp;
        }
    }
    return $array;
}