四种常用的排序算法

1、冒泡排序：

两两相比，每循环一轮就不用再比较最后一个元素了，因为最后一个元素已经是最大或者最小。
第一个循环次数为n,第二个循环次数最大为 n-1，每轮选出一个最大或者是最小的值，时间复杂度O(n^2)。

function maopaoSort ($list)
{
    $len = count($list);
    for ($i = 0; $i < $len - 1; $i++) {
        for ($j = 0; $j < $len - $i - 1; $j++) {
            if ($list[$j] > $list[$j + 1]) {
                $tmp = $list[$j];
                $list[$j] = $list[$j + 1];
                $list[$j + 1] = $tmp;
            }
        }
    }
    return $list;
}

2、选择排序：

选定一个作为最小值，剩下的和这个比较，然后调换位置。

第一个循环次数为n,第二个循环次数最大为 n-1，时间复杂度O(n^2)。

function xuanzeSort ($list)
{
    $len = count($list);
    for ($i = 0; $i < $len - 1; $i++) {
        $pos = $i;
        for ($j = $i + 1; $j < $len; $j++) {
            if ($list[$pos] > $list[$j]) {
                $pos = $j;
            }
        }
        if ($pos != $i) {
            $tmp = $list[$pos];
            $list[$pos] = $list[$i];
            $list[$i] = $tmp;
        }
    }
    return $list;
}

3、插入排序：

假设前面的数都是排好顺序的，要把第n个数插入到有序的数组里。

第一个循环次数为n,第二个循环次数最大为 n-1，时间复杂度O(n^2)。

function charuSort ($list){
    $len = count($list);
    for ($i = 1; $i < $len; $i++) {
        $tmp = $list[$i];//获取对比元素
        for ($j = $i - 1; $j > 0; $j--) {
            if ($list[$j] > $tmp) {
                $list[$j + 1] = $list[$j];
                $list[$j] = $tmp;
            } else {
                break;
            }
        }
    }
    return $list;
}

4. 快速排序：

设置一个基准值，小于基准值放左边，大于基准值放右边，最后递归继续排左右两侧的，最后将排完后数组合并。时间复杂度为O(nlogn)

public function kuaisuSort($list)
{
   $len = count($list);
   
   // 设置一个中间的值，比这个值小的放左边，比这个值大的放右边，最后合并
   $middle = $list[0];
   $leftArr = $rightArr = [];
   for ($i = 1; $i < $len; $i++) {
      if ($list[$i] < $middle) {
         $leftArr[] = $list[$i];
      } else {
         $rightArr[] = $list[$i];
      }
   }
   
   // 再继续对左边和右边的数组继续排序
   if ($leftArr) {
      $leftArr =kuaisuSort($leftArr);
   }
   // 再继续对右边的数组排序
   if ($rightArr) {
      $rightArr = kuaisuSort($rightArr);
   }
   
   return array_merge($leftArr, [$middle], $rightArr);
}