1、冒泡排序

• 原理：冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。
• 时间复杂度： O(n2)
• 空间复杂度：只涉及相邻元素的交换，是原地排序算法
• 算法稳定性：元素相等不会交换，是稳定的排序算法

function bubble_sort($array){
    $count = count($array);
    if ($count <= 0) return false;
    for($i=0; $i<$count; $i++){
        for($j=$i; $j<$count-1; $j++){
            if ($array[$i] > $array[$j]){
                $tmp = $array[$i];
                $array[$i] = $array[$j];
                $array[$j] = $tmp;
            }
        }
    }
    return $array;
}

2、快速排序

快速排序是原地排序算法，时间复杂度和归并排序一样，也是 O(nlogn)，这个时间复杂度数据量越大，越优于 O(n2)，但是快速排序也有其缺点，因为涉及到数据的交换，有可能破坏原来相等元素的位置排序，所以是不稳定的排序算法，尽管如此，凭借其良好的时间复杂度表现和空间复杂度的优势，快速排序在工程实践中应用较多，比如 PHP 数组的 sort 函数底层就是基于快速排序来实现的，明天我们就来一起探究下 PHP 底层 sort 函数是如何实现的。

function quick_sort($array) {
    if (count($array) <= 1) return $array;
    $key = $array[0];
    $left_arr = array();
    $right_arr = array();
    for ($i=1; $i<count($array); $i++){
        if ($array[$i] <= $key)
            $left_arr[] = $array[$i];
        else
            $right_arr[] = $array[$i];
    }
    $left_arr = quick_sort($left_arr);
    $right_arr = quick_sort($right_arr);
    return array_merge($left_arr, array($key), $right_arr);
}

3、插入排序

原理：我们将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

 /**
 * 插入排序
 * 固定首位,把下一个未排序的,与前面有序序列中的元素交换,
 * 当发现前面的那个不大于自身,则不再向前判断,中止本趟,进行下趟判断
 */
function insertionSort($randArr, $length)
{

    for ($i = 1; $i < $length; $i++) {
        //如果当前元素,比前一个元素小,就交换
        for ($j = $i; $j > 0 && $randArr[$j] < $randArr[$j - 1]; $j--) {
            $temp = $randArr[$j];
            $randArr[$j] = $randArr[$j - 1];
            $randArr[$j - 1] = $temp;
        }
    }
    return $randArr;
}

/**
 * 优化点:
 * 内层循环中,用覆盖代替了交换
 * @param $randArr
 * @param $length
 * @return mixed
 */
function insertionSort2($randArr, $length)
{
    for ($i = 1; $i < $length; $i++) {
        //保存本次考查元素,
        $e = $randArr[$i];
        //前面有序元素,若比当前元素大,就覆盖当前元素
        for ($j = $i; $j > 0 && $randArr[$j - 1] > $e; $j--) {
            $randArr[$j] = $randArr[$j - 1];
        }
        //最后,把当前元素 覆盖 它的前一个元素
        $randArr[$j] = $e;
    }
    return $randArr;
}

    
    $nums = [4, 5, 6, 3, 2, 1];
    $nums = insertionSort2($nums,6);
    print_r($nums);

4、选择排序

原理：选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

 /**
     * 选择排序算法实现
     */
    function selection_sort($nums)
    {
        if (count($nums) <= 1) {
            return $nums;
        }
    
        for ($i = 0; $i < count($nums); $i++) {
            $min= $i;
            for ($j = $i + 1; $j < count($nums); $j++) {
                if ($nums[$j] < $nums[$min]) {
                    $min = $j;
                }
            }
            if ($min != $i) {
                $temp = $nums[$i];
                $nums[$i] = $nums[$min];
                $nums[$min] = $temp;
            }
        }
    
        return $nums;
    }
    
    $nums = [4, 5, 6, 3, 2, 1];
    $nums = selection_sort($nums);
    print_r($nums);

选择排序的时间复杂度也是 O(n2)

由于不涉及额外的存储空间，所以是原地排序；

由于涉及非相邻元素的位置交换，所以是不稳定的排序算法。

插入排序 、冒泡排序、选择排序三者的优先级是插入排序 > 冒泡排序 >> 选择排序。

5、归并排序

原理：所谓归并排序，指的是如果要排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

    function merge_sort($nums)
    {
        if (count($nums) <= 1) {
            return  $nums;
        }
    
        merge_sort_c($nums, 0, count($nums) - 1);
        return $nums;
    }
    
    function merge_sort_c(&$nums, $p, $r)
    {
        if ($p >= $r) {
            return;
        }
    
        $q = floor(($p + $r) / 2);
        merge_sort_c($nums, $p, $q);
        merge_sort_c($nums, $q + 1, $r);
    
        merge($nums, ['start' => $p, 'end' => $q], ['start' => $q + 1, 'end' => $r]);
    }
    
    function merge(&$nums, $nums_p, $nums_q)
    {
        $temp = [];
        $i = $nums_p['start'];
        $j = $nums_q['start'];
        $k = 0;
        while ($i <= $nums_p['end'] && $j <= $nums_q['end']) {
            if ($nums[$i] <= $nums[$j]) {
                $temp[$k++] = $nums[$i++];
            } else {
                $temp[$k++] = $nums[$j++];
            }
        }
    
        if ($i <= $nums_p['end']) {
            for (; $i <= $nums_p['end']; $i++) {
                $temp[$k++] = $nums[$i];
            }
        }
    
        if ($j <= $nums_q['end']) {
            for (; $j <= $nums_q['end']; $j++) {
                $temp[$k++] = $nums[$j];
            }
        }
    
        for ($x = 0; $x < $k; $x++) {
            $nums[$nums_p['start'] + $x] = $temp[$x];
        }
    }
    
    $nums = [4, 5, 6, 3, 2, 1];
    $nums = merge_sort($nums);
    print_r($nums);

归并排序不涉及相等元素位置交换，是稳定的排序算法，时间复杂度是 O(nlogn)，要优于冒泡排序和插入排序的 O(n2)，但是归并排序需要额外的空间存放排序数据，不是原地排序，最多需要和待排序数组同样大小的空间，所以空间复杂度是 O(n)。