常见排序算法

1、冒泡排序

原理：两两相邻的数进行比较，如果反序就交换，否则不交换
时间复杂度：O(n^2)
空间复杂度：O(1)

<?php
function func($array) {
    $len = count($array);
    for ($i = 0; $i < $len; $i++) {
        for ($j = $i + 1; $j < $len; $j++) {
            if ($array[$i] > $array[$j]) {
                $temp = $array[$i];
                $array[$i] = $array[$j];
                $array[$j] = $temp;
            }
        }
    }
    return $array;
}

2、插入排序

原理：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的数据序列的适当位置，直到全部记录插入完成为止。
时间复杂度：O(n^2)
空间复杂度：O(1)

<?php
function func(array $array)
{
    $count = count($array);
    for ($i = 1; $i < $count; $i++) { //从第二个元素开始插入
        for ($j = $i - 1; $j >= 0; $j--) { //与前面的数比较，找到插入的位置

            if ($array[$j] > $array[$j + 1]) { //比前面的数小，交换位置
                $tmp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $tmp;
            } else { //大于或等于前面的数，表示已找到插入的位置
                break;
            }
        }
        echo '<pre>';print_r($array);
    }
    return $array;
}

3、选择排序

原理：在每一次大循环的时候得出一个最大值或者最小值来替换相应的位置
时间复杂度：O(n^2)
空间复杂度：O(1)

function func($array) {
    $count = count($array);
    for ($i = 0; $i < $count; $i++) {
        $min = $array[$i];
        for ($j = $i + 1; $j < $count; $j++) {
            if ($array[$j] < $min) {
                $min = $array[$j];
                $array[$j] = $array[$i];
                $array[$i] = $min;
            }
        }
    }
    return $array;
}

4、快速排序

原理：通过设置一个初始中间值，来将需要排序的数组分成3部分，小于中间值的左边，中间值，大于中间值的右边，继续递归用相同的方式来排序左边和右边，最后合并数组
时间复杂度：O(nlogn)
空间复杂度：O(1)

function func($array)
{
    if (count($array) <= 1) {
        return $array;
    }
    $middle = $array[0]; // 中间值
    $left = []; // 接收小于中间值
    $right = [];// 接收大于中间值
    // 循环比较
    for ($i = 1; $i < count($array); $i++) {
        if ($middle < $array[$i]) {
            // 大于中间值
            $right[] = $array[$i];
        } else {
            // 小于中间值
            $left[] = $array[$i];
        }
    }
    // 递归排序划分好的2边
    $left = func($left);
    $right = func($right);
    // 合并排序后的数据，别忘了合并中间值
    return array_merge($left, array($middle), $right);
}

5、归并排序（最优）

原理：
第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置
第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针超出序列尾
时间复杂度：O(nlogn)
空间复杂度：O(1)

还有一种写法

<?php
function mergeSort($array){
    if (count($array) <= 1) {
        return $array;
    }
    $left = array_slice($array, 0, intval(count($array)/ 2));
    $right = array_slice($array, intval(count($array)/ 2));

    $left = mergeSort($left);
    echo json_encode($left);echo "<br>";
    $right = mergeSort($right);
    echo json_encode($left);echo "<br>";

    return merge($left, $right);
}

function merge($left,$right) {
    $result = [];
    while(count($left) >0 && count($right) > 0) {
        if($left[0] <= $right[0]){
            array_push($result,array_shift($left));
        } else {
            array_push($result,array_shift($right));
        }
    }

    array_splice($result,count($result),0,$left);
    array_splice($result,count($result),0,$right);

    return $result;
}