排序

冒泡排序

• 空间复杂度O(n)
• 时间复杂度O(n)

  <?
  // 从小到大
  function bubbleSort($nums){
    for ($i = 0; $i < count($nums); $i++){
        for ($j = 0; $j < count($nums)-$i-1; $j++){
            if ($nums[$j+1] < $nums[$j]){ // 小的往上冒
                list($nums[$j],$nums[$j+1]) = array($nums[$j+1],$nums[$j]);
            }
        }
    }
    return $nums;
  }

插入排序

• 前面的永远是排好序的，找合适位置插进去就行
• 空间复杂度O(1)
• 时间复杂度O(n)

<?
function insertSort($nums){
    for ($i = 1; $i < count($nums); $i++){
        $current = $nums[$i];
        for ($j = $i-1; $j >= 0 && $nums[$j] > $current; $j--){
            $nums[$j+1] = $nums[$j];
        }
        $nums[$j+1] = $current;
    }
    return $nums;
}

归并排序

• 核心思想是分治，把一个复杂问题拆分成若干个子问题来求解。
• 时间复杂度 T(n)
• 空间复杂度 O(n) ```php <? function mergeSort($nums){ _sort($nums,0,count($nums)-1); return $nums; }

function _sort(&$nums, $left, $right){ if ($left >= $right) return;

$mid = floor(($left+$right)/2);

_sort($nums,$left,$mid);
_sort($nums,$mid+1,$right);
merge($nums,$left,$mid,$right);

}

function merge(&$nums,$left,$mid,$right){ $cp = $nums; $k = $i = $left; $j = $mid + 1; while ($k <= $right){ if ($i > $mid){ # 左半边的数据都处理完毕 $nums[$k++] = $cp[$j++]; }else if ($j > $right){ # 右半边的数据都处理完毕 $nums[$k++] = $cp[$i++]; }else if ($cp[$j] < $cp[$i]){ # 右边的数小于左边的数 $nums[$k++] = $cp[$j++]; }else{ # 左边的数小于右边的数 $nums[$k++] = $cp[$i++]; } } }

---

<a name="Ovoxs"></a>
### 快速排序

- 分治+1，把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。
- 时间复杂度O(n)
- 空间复杂度O(n)
```php
<?
function quickSort($nums){
    _sort($nums,0,count($nums)-1);
    return $nums;
}

function _sort(&$nums,$left,$right){
    if ($left >= $right) return;

    $p = partition($nums,$left,$right);
    _sort($nums,$left,$p-1);
    _sort($nums,$p+1,$right);
}

function partition(&$nums,$left,$right){
    $len = count($nums);
    if ($len <= 1){
        return $nums;
    }
    $p = $nums[$left];
    while ($left < $right){
        while ($nums[$right] >= $p && $right > $left){
            $right--;
        }
        $nums[$left] = $nums[$right];
        while ($nums[$left] <= $p && $right > $left){
            $left++;
        }
        $nums[$right] = $nums[$left];
    }
    $nums[$right] = $p;
    return $right;
}

拓扑排序

• 图必须是有向图，图里面没有环。
• 一般用来理清具有依赖关系的任务。
• 时间复杂度O(n) ```php <?php

function topologicalSort($nums){

# 广度优先搜索
$res = [];
$q = new SplQueue();
$va = new SplQueue();
foreach ($nums as $k => $num){
    if ($num['in_degree'] == 0) {$q->push($num); $va->push($k);} # 找出所有入度为0的数
}
while (!$q->isEmpty()){
    $v = $q->shift();
    $res[] = $va->shift(); # 存值
    for ($i = 0; $i < count($v['out_degree']); $i++){ # 遍历出度
        $nums[$v['out_degree'][$i]]['in_degree'] --; # 依次减一
        if ($nums[$v['out_degree'][$i]]['in_degree'] == 0){ # 存取新的入度为0的数
            $q->push($nums[$v['out_degree'][$i]]);
            $va->push($v['out_degree'][$i]);
        }
    }
}
return $res;

}

$nums = [ 1 => [ ‘in_degree’ => 0, # 入度（指向箭头） ‘out_degree’ => [2,4], # 出度（指出箭头） ], 2 => [ ‘in_degree’ => 1, ‘out_degree’ => [3,4], ], 3 => [ ‘in_degree’ => 2, ‘out_degree’ => [5], ], 4 => [ ‘in_degree’ => 2, ‘out_degree’ => [3,5], ], 5 => [ ‘in_degree’ => 2, ‘out_degree’ => [], ], ]; var_dump(topologicalSort($nums)); ```