1、冒泡排序 Bubble Sort

排队，依次交换

$arr = [1,4,2,9,7,5,8];

//2、 让下面的可以每次找出最大值的代码重复执行
for($i =0, $len = count($arr); $i < $len; $i++) {
    //1、将最大的放到最右边
    for($j = 0; $j < $len - 1 - $i; $j++ ) {
        //判断：两两相比
        if($arr[$j] > $arr[$j+1]) {
            //左边比右边大:交换
            $temp = $arr[$j];
            $arr[$j] = $arr[$j+1];
            $arr[$j+1] = $temp;
        }
    }
}

2、选择排序 Selection sort

不稳定 [5, 5, 3] 第一次将[5]和[3]交换，导致第一个5到第二个5后面
每次从待排序数据元素中挑选出最小元素，存放在序列的起始位置

$arr = [1,5,2,9,3,4];

//1、 确定要交换多少次：一次只能找到一个最小的，需要找数组长度对应的次数
for($i = 0,$len = count($arr); $i < $len; $i++) {
    //2、 假设当前第一个已经排好序了
    $min = $i; //当前第一个数是最小的
    //3、 拿该最小的比较剩余的其他
    for($j = $i + 1; $j < $len; $j++) {
        //4、 比较：比较当前元素与选定的最小元素
        if($arr[$j] < $arr[$min]) {
            //说明当前指定的$min不合适
            $min = $j;
        }
    }
    //5、 交换当前选定的值与实际最小的元素值
    if($min != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$min];
        $arr[$min] = $temp;
    }
}

3、插入排序 Insert sort

使用少量数据排序，稳定

$arr = [4,2,6,8,9,5];

//1、 确定要插入多少回(假设一个数字一次性出入对的位置，同时第一个位置是对的)
for($i = 1,$len = count($arr); $i < $len; $i++) {
    //2、 取出当前要插入的元素的值
    $temp = $arr[$i];
    //标记： 默认说明当前要插入的数组的位置是对的
    $change = fales;
    //3、 让该数据与前面已经排好序的元素重复比较（挨个比较），知道对的位置（交换）
    for($j = $i - 1; $j >=0; $j--) {
        //4、 比较
        if($arr[$j] > $temp) {
            //说明当前要插入的元素，比前面的已经排好序的元素值小：交换位置
            $arr[$j+1] = $arr[$j];
            //$arr[$j] = $temp;
            // 说明前面顺序的数组元素有不合适的位置
            $change = true;
        }else{
            //说明当前待插入元素，比前面元素大：说明位置正确
            break;
        }
    }
    //判断位置是否需要变动
    if($change) {
        //有数据移动：站错位置了
        $arr[$j+1] = $temp;
    }
}

4、快速排序 Quicksort

对冒泡排序的改进 不稳定 （递归）

$arr = [5,6,3,4,9,2,7,8];

// 快速排序
function quick_sort($arr) {
    //递归出口
    $len = count($arr);
    if($len <= 1) return $arr;

    //去除某个元素，将剩余的数组元素分散到两个不同的数组中
    $left = $right = [];
    for($i = 1; $i < $len; $i++) {
        //第一个元素作为比较元素
        //比较：小的放left中，大的放right中
        if($arr[$i] < $arr[0]) {
            $left[] = $arr[$i];
        }else{
            $right[] = $arr[$i];
        }
    }
    //$left和$righ数组元素没有排好序:递归点
    $left = quick_sort($left);
    $right = quick_sort($right);
    // 合并三个"数组"
    return array_merge($left, (array)$arr[0], $right);
}

5、归并排序 MERGE-SORT

采用分治法 Divide and Conquer

// 二路归并
$arr1 = [1,3,5];
$arr2 = [2,4,6];

//去除一个空数组用于归并空间
$arr3 = [];
while(count($arr1) && count($arr2)) {
    //只要$arr1和$arr2里面还有元素，就进行循环
    //去除每个数组的第一个元素：进行比较
    $arr3[] = $arr1[0] < $arr2[0] ? array_shitf($arr1) : array_shift($arr2);
}

//合并结果
array_merge($arr3, $arr1, $arr2);

$arr = [4,7,2,1,5,9,3];
//归并排序函数
function merge_sort($arr) {
    //递归出口
    $len = count($arr);
    if($len <= 1) return $arr;
    //拆分
    $middle = floor($len / 2);
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);

    //递归点：$left和$right都没有排好序：而且可能是多个元素的数组
    $left = merge_sort($left);
    $right = merge_sort($right);

    //假设左边和右边都已经排好序：二路归并
    $m = [];
    while(count($left) && count($right)) {
        //只要$arr1和$arr2里面还有元素，就进行循环
        //去除每个数组的第一个元素：进行比较
        $m[] = $left[0] < $right[0] ? array_shitf($left) : array_shift($right);
        //返回结果
    }
    return array_merge($m, $left, $right);
}