eleven26
0%

Posted on Edited on

因为最近这电脑在 CPU 暴涨的时候会很容易死机，所以需要找个办法来限制一下一些进程的 CPU 占用，防止这些进程运行的时候导致死机。

安装 cpulimit

1
2
3
4
5
wget -O cpulimit.zip https://github.com/opsengine/cpulimit/archive/master.zip
unzip cpulimit.zip
cd cpulimit-master
make
sudo cp src/cpulimit /usr/bin

使用 cpulimit

1
cpulimit -l 50 -i <这里接你想要执行的命令>

比如，我想限制一下 npm install 的 cpu 占用，则可以像如下这样使用 cpulimit

1
cpulimit -l 50 -i npm install

执行之后，npm install 产生的那个进程占用的 CPU 占用率就不会再超过 50% 了。

Posted on Edited on

本文主要讲一下个人最近在看 redux 过程中的一点体会和总结。

redux 中的核心元素

redux

网上找的一张图，里面的内容就是本文要说的内容了。一句话说完就是：

React 组件会通过 Action 来告诉 Store 需要更新哪些状态，Store 通过调用 Reducer 来获取一个新的状态，应用最终的状态就是 reducer 返回的这个新的状态。

关于 state

在 Web 应用中，常常需要保存一些全局的状态，用来做一些 UI 上或者其他方面的控制。比如是否登录，如果已经登录，则显示用户信息，如果没有登录则显示一个登录的按钮让用户点击进行登录操作。

这些状态往往存在于应用的整个生命周期中，并且在不同的组件中可能需要公用这些状态。

现在的一些前端框架都提供了一些状态管理的组件，比如 redux 和 vuex 等，我们可以通过这些组件来方便地对应用的状态进行管理。

三个主要概念

store

store 顾名思义就是存储的对象，在 redux 中，我们会将一些需要共享的状态存储到这个对象中，而这个 store 对象在我们的应用中应该只有一个。既然 store 是一个对象，自然也有一些可以调用的方法，比如：

  • getState() 获取当前的 state（也就是当前 store 保存的状态）
  • dispatch(action) 更新 state
  • subscribe(listener) 注册 state 变动的监听器，返回值是注销监听器的函数

简单来说，store 的主要作用是：

  • 存储 state
  • state 变动的时候可以执行用户注册的回调（比如，重新渲染某一个组件）

action

在 redux 这类状态管理组件中，推荐修改 state 的方法都是通过 store 对象的 dispatch 方法来进行状态的更新，dispatch 接受的参数就叫 action，每一个 action 代表了我们想对 store 执行哪种状态的变更。都通过 dispatch 来更新状态有什么好处呢？

  • 状态的变动都通过统一的接口，方便开发者调试（我们可以通过 subscribe 方法来监听到所有的 state 变动）
  • 个人觉得简洁的 API 可以降低开发者的心智负担吧

reducer

上面提到了 action，说到了 dispatch 的参数是一个 action，但实际我们是如何更新 store 里面的 state 的呢？答案是通过 reducer，reducer 就是一个函数，这个函数接收当前的 state 和需要执行的 action 作为参数，返回一个新的 state(一定要返回)。

这个命名是不是有点熟悉，我们知道 js 里面数组有个 reduce 函数：

1
2
const arr = [1, 2, 3, 4, 5]
console.log(arr.reduce((res, cur) => res + cur, 0))

这里的 reduce 第一个函数参数的作用就是接收上一次执行的结果和数组当前下标指向的值作为参数，返回一个新的数作为此次遍历的结果，如此直到遍历完整个数组。等同于以下代码：

1
2
3
4
5
let res = 0
for (let i in arr) {
    res += arr[i]
}
console.log(res)

对比一下这个 Array.redux， redux 里面的 reducer 就很好理解了，reducer 的作用就是接收上一次执行 reducer 返回的结果和当前要操作的 action 作为参数，我们会在前一个 state 的基础上执行指定的 action。比如：

1
2
3
4
5
6
7
8
const reducer = (state = 0, action) => {
  switch (action.type) {
    case 'INCREMENT1': return state + 1;
    case 'DECREMENT1': return state - 1;
    default: return state;
  }
}
store.dispatch({ type: 'INCREMENT' })

这个 reducer 会依据 action 里面指定的 type 来对 store 里面的状态进行一些更新操作，然后返回一个新的 state。

store 初始化过程

做个小实验，在上述 reducer 的第一行写一个 console.log，然后我们可以发现在项目启动的时候控制台输出了我们 console.log 的东西，但实际上我们并没有调用任何的 store.dispatch 方法。

这说明一个问题是，store 里面保存的初始 state 也是通过执行 reducer 来获取的，所以我们的 recuer 里面都需要包含一个 default 分支，一方面是初始化使用，另一个原因下面会说到。

我们也可以通过 console.log 来看看 store 初始化的时候 action 是什么样的：

1
{type: "@@redux/INITk.3.4.k.v"}

这个一般用不上，知道有这么一个初始化的过程就好。

修改 state 的过程

上面说到了，我们修改 store 里面的 state 都是需要通过 store.dispatch 这个 API 来进行状态的更新的。这里简单说一下这个修改生效的过程：

  1. 拿到全局共享的 store 对象之后，假设我们的 action 是 {type: 'INCREMENT'}，我们需要通过 store.dispatch({ type: 'INCREMENT' }) 来执行一次 INCREMENT 操作
  2. store 对象拿到了这个 action({ type: 'INCREMENt' }) 之后，将旧的 state 和这个 action 值传递给初始化 store 时接收的 reducer 参数
  3. reducer 执行，依据 action 里面 type 的不同值来执行不同的操作，最后返回一个新的 state
  4. store 拿到 reducer 返回的新的 state，更新当前 store 的 state（实现上是 currentState = currentReducer(currentState, action)）
  5. 执行所有监听器，结束。

也就是说，监听器的执行是在状态更新之后才执行的。我们在 listener 里面如果通过 store.getState() 获取 state 的话将会是最新的 state。

redux 里 combineReducers 的作用

这里做一个简单的假设，假设我们的应用中有两个状态需要维护，一个是姓名 name，一个是年龄 age。如果我们使用一个 reducer 来完成对这两个状态的维护的话，代码将是下面这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const initialState = { name: '', age: 0 }

const reducer = (state = initialState, action) => {
  console.log(state)
  switch (action.type) {
    case 'NAME':
      return Object.assign({}, state, { name: action.payload })
    case 'AGE':
      return Object.assign({}, state, { age: action.payload })
    default:
      return Object.assign({}, state)
  }
}

const store = createStore(reducer)

// store.dispatch({ type: 'NAME', payload: 'react' })
// store.dispatch({ type: 'AGE', payload: 3 })

我们可以发现，在这个 reducer 里面维护了两个不同的状态的变更操作，在状态比较少的时候，这样写没有什么问题，一旦应用中需要共享的状态越来越多的时候，这个 reducer 也会越来越长，当我们需要对其中某一个状态的更新操作进行修改的时候就比较麻烦了。

redux 里面的 combineReducers 允许我们将不同状态的更新操作拆分到不同的 reducer 里面，这样一来在我们对某一个状态执行变更操作的代码需要修改时候，就可以很方便地找到具体的那一个 reducer 来进行修改。

将上面的两个状态拆分之后，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const name = (state = '', action) => {
  console.log('name: ', state)
  switch (action.type) {
    case 'NAME':
      return action.payload
    default:
      return state
  }
}

const age = (state = 0, action) => {
  console.log('age: ', state)
  switch (action.type) {
    case 'AGE':
      return action.payload
    default:
      return state
  }
}

const reducer = combineReducers({
  name,
  age
})

const store = createStore(reducer)

在这种写法中， 我们对 name 和 age 两个状态的维护拆分到了两个 reducer 里面，然后我们再使用 combineReducers 来将它们合并，然后传递给 createStore 创建一个 store 对象。

在这种情况下，我们调用 store.getState() 可以得到如下对象：

1
2
3
4
{
  name: '',
  age: 0
}

得出这个结果的过程是，combineReducers 会将 reducer 里面每一个 key 对应的值拿出来（也就是针对那个状态的 reducer），这个函数会返回一个新的函数，在这个新的函数中，会遍历所有的 reducer，执行所有的 reducer。然后将每一个 reducer 返回的结果合并到一个对象里面（也就是最终的 state）。具体实现可以看实现的源码 redux/src/combineReducers.js。下面是源代码里面的注释：

Turns an object whose values are different reducer functions, into a single reducer function. It will call every child reducer, and gather their results into a single state object, whose keys correspond to the keys of the passed reducer functions.

也就是说，虽然我们代码上是拆分成了不同的 reducer，但实际 store 在执行 reducer 的时候还是会将全部的 reducer 执行一遍。所以我们需要在 reducer 里面添加一个 default 分支返回 state。

这里有个需要非常注意的点是：store.dispatch 的时候都会触发所有 reducer 的执行。具体哪一个会修改到 store 的 state 完全是开发者自己控制的。

拆分的优势很明显，可以针对不同的状态来进行独立地维护。劣势就是，需要维护比较多的 reducer，但总的来说长期发展的时候还是建议拆分成不同的 reducer 来进行维护。

总结

  1. redux 通过 createStore 函数来创建 store 对象，一般只创建一个 store 对象，这个 store 对象保存了应用的状态。createStore 函数接收一个 reducer 函数作为参数
  2. reducer 函数接收上一个 state 和 action 作为参数，返回一个新的 state
  3. 修改 state 的唯一方式是 store.dispatch(action)
  4. combineReducers 的作用是合并多个 reducer，这些被合并的 reducer 维护某一个单一的状态，实现在不同的 reducer 里面维护不同状态的更新逻辑

Posted on Edited on

冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是 O(n²)，比较高，适合小规模数据的排序。归并排序和快速排序时间复杂度为 O(nlogn)，适合大规模的数据排序。

归并排序和快速排序都用到了分治思想。

归并排序

归并排序的原理

如果要排序一个数组，先从中间的位置将数组分割成两个子数组，然后再对这两个子数组从中间位置分割，如此直到分割之后的子数组只有一个元素。然后将最终分割的数组按大小顺序合并到一个新的数组中，如此递归地合并直到所有子数组合并完毕，就可以得到一个有序的数组了。

例子

假设要对下面这组数据利用归并排序方法进行排序：

1
$arr = [3, 5, 100, 6, 78];

第一次分割成下面两个数组：

1
$arr1 = [3, 5, 100]; $arr2 = [6, 78];

第二次分割：

1
2
3
4
// $arr1 划分成
[3] [5, 100]
// $arr2 划分成
[6] [78]

按递归的思想会先处理 $arr1 分割出来的两个数组：

[3] 里面只有一个元素，无需再分割，[5, 100] 还需要再次分割成 [5] 和 [100]，分割完成就开始合并了，合并的时候，需要创建一个大小等于两个需要合并的数组大小总和的数组 temp，然后将小的元素先放入 temp，如此直到所有元素都放进了 temp 之后，这次合并操作就完成了，就得到了一个有序的数组 temp。

所以 $arr1 最终合并得到：

1
[3, 5, 100]

$arr2 最终合并得到：

1
[6, 78]

再将 $arr1 和 $arr2 处理的结果合并，也就是将 [3, 5, 100] 和 [6, 78] 合并，即可得到：

1
[3, 5, 6, 78, 100]

PHP 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function merge_sort($arr, $p, $r)
{
    if ($p >= $r) return [$arr[$r]];

    $q = intval(($p + $r) / 2);

    $arr1 = merge_sort($arr, $p, $q);
    $arr2 = merge_sort($arr, $q + 1, $r);

    return merge($arr1, $arr2);
}

function merge($arr1, $arr2)
{
    $arr = [];
    $n1 = count($arr1);
    $n2 = count($arr2);

    $k = 0;
    $i = 0;
    $j = 0;
    while ($i < $n1 && $j < $n2) {
        if ($arr1[$i] <= $arr2[$j]) {
            $arr[$k++] = $arr1[$i++];
        } else {
            $arr[$k++] = $arr2[$j++];
        }
    }

    while ($i < $n1) {
        $arr[$k++] = $arr1[$i++];
    }

    while ($j < $n2) {
        $arr[$k++] = $arr2[$j++];
    }

    return $arr;
}

算法分析

  1. 归并排序是否稳定？

在 merge 实现里面对相等的元素，我们可以将 $arr1 的元素先合并到 $arr，这样即可实现排序算法的稳定性。

  1. 时间复杂度是多少？

归并排序的排序过程中不会受原始数据的有序度影响，都是固定的不断拆分成两个数组，直到最终拆分到只有一个元素的时候进行合并，小的在前面，大的在后面。也就是说，归并排序的时间复杂度是固定的 O(nlogn)，非常稳定。

  1. 空间复杂度是多少？

在将原始数据一分为二的时候，我们不需要开辟额外的空间来存储数据，但是在合并的过程中，我们需要开辟一个临时数组来存储排序后的数据，然后将这个数组覆盖掉原始数组的那一段范围的数据。

但由于某一时刻 CPU 中最多只有一个合并的操作在进行，所以最大的空间复杂度为 O(n)。

快速排序

快速排序原理

快速排序的过程中，我们会先从原始数组中随机选一个数 pivot，以这个数为中点，将剩余的其他 n-1 个数划分为两个部分，小于 pivot 的交换到 pivot 的左边，大于 pivot 的交换到 pivot 的右边。然后再对左边和右边两部分的子数组递归进行此操作，直到最后只有一个元素为止，这个时候我们的整个数组就排序完毕了。

例子

利用快速排序对以下数组进行排序：

1
$arr = [5, 1, 7, 8, 6];

  1. 选择最后一个数（6）作为中点，小于 6 的交换到 $arr 的左边，中间为 6，大于 6 的交换到 $arr 的右边。

  2. 经过上一步的交换后，$arr 为 [5, 1, 6, 8, 7]，这个时候 6 其实就是最终排序完的位置了。

  3. 再对 6 左边和右边的子数组 [5, 1]、[8, 7] 执行第一步操作，如此直到子数组只有一个元素，结束排序。

我们可以发现，快速排序的过程，其实就是一次次地确定最终排序数组中间元素的过程。

PHP 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function quick_sort(&$arr, $p, $r)
{
    if ($p >= $r) return;

    $q = partition($arr, $p, $r);

    quick_sort($arr, $p, $q - 1);
    quick_sort($arr, $q + 1, $r);
}

$array = [1, 5, 3, 7, 9, 4, 20, 100, 55, 67, 66];

// 分区+排序
function partition(&$arr, $p, $r)
{
    // 返回分区点
    $pivot = $arr[$r];

    $i = $p;
    for ($j = $p; $j < $r - 1; $j++) { // $r - 1 的值为 pivot，中间值
        if ($arr[$j] < $pivot) {
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
            $i++;
        }
    }

    // $i 永远不大于 $j，$i <= $j
    // $i == $j 的情况下不交换位置
    // 情况一：只有一个数，不影响
    // 情况二：数组里面全部都是小于 $pivot 的元素，这种情况不需要再互换了
    if ($i < $j) {
        $arr[$r] = $arr[$i];
        $arr[$i] = $pivot;
    }

    return $i;
}

quick_sort($array, 0, count($array) - 1);
var_export($array);

算法分析

  1. 快速排序是否是稳定的排序算法？

由于快速排序的过程中，会发生元素前后的交换，所以不能保证稳定性，所以是不稳定的排序算法。

  1. 快速排序的时间复杂度是多少？

平均时间复杂度是 O(nlogn)，但可能比这个大

  1. 快速排序的空间复杂度是多少？

快速排序是原地排序算法，排序过程不需要开辟新的空间来处理。

归并排序和快速排序对比

  1. 归并排序是稳定的排序算法，快速排序不是稳定的排序算法

  2. 归并排序的过程需要开辟临时的空间来进行合并操作，快速排序是原地排序算法，归并排序的空间复杂度太高

  3. 归并排序的时间复杂度是固定的，快速排序的时间复杂度会受实际数据有序度影响

  4. 实际使用中，快速排序用得更多，因为是原地排序算法，但是不能保证排序结果的稳定性

Posted on Edited on

冒泡排序

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

例子

假设要对一组数据排序（数组）：4，5，6，3，2，1

冒泡过程（由小到大排序，每次冒泡实质就是拿出最大的元素放到数组末尾）：

第一次冒泡：

1、拿 4 和 5 对比，4 < 5 所以不做元素互换操作，此时数组为 4，5，6，3，2，1

2、拿 5 和 6 对比，5 < 6 所以不做元素互换操作，此时数组为 4，5，6，3，2，1

3、拿 6 和 3 对比，6 > 3 所以将 6 和 3 位置互换，此时数组为 4，5，3，6，2，1

4、拿 6 和 2 对比，6 > 2 所以将 6 和 2 位置互换，此时数组为 4，5，3，2，6，1

5、拿 6 和 1 对比，6 > 1 所以将 6 和 1 位置互换，此时数组为 4，5，3，2，1，6

经过这次冒泡，元素 6 的位置就是最终排序后的位置了。

第二次冒泡的过程中，因为数组最后一个元素已经是最大的元素，因此我们只需要对开头的 5 个元素排序即可。

第二次冒泡，此时数组为 4，5，3，2，1，6 ：

1、拿 4 和 5 对比，4 < 5 所以不做元素互换操作，此时数组为 4，5，3，2，1，6

2、拿 5 和 3 对比，5 > 3 所以交换这两个元素的位置，此时数组为 4，3，5，2，1，6

3、拿 5 和 2 对比，5 > 2 所以交换这两个元素的位置，此时数组为 4，3，2，5，1，6

4、拿 5 和 1 对比，5 > 1 所以交换这两个元素的位置，此时数组为 4，3，2，1，5，6

到此，第二次冒泡结束（因为数组末尾的元素在第一次冒泡的时候已经确定的了），经过这次冒泡，倒数第二个元素也确定了下来。

我们一共有 6 个元素，所以还需要进行 4 次冒泡操作才能得到最后的排序结果。

冒泡排序优化

因为我们在冒泡过程中，实际上是对比相邻的两个元素，如果 $arr[$i] > $arr[$i + 1]，那么交换这两个元素的位置。

也就是说，如果一次冒泡过程中，完全没有发生数据交换，说明数组里面的数组都是从小到大有序的。这个时候我们就可以直接退出冒泡过程了。

PHP 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
$array = [1, 5, 3, 7, 9, 4, 20, 100, 55, 67, 66];

function bubble_sort($arr)
{
    $n = count($arr);
    if ($n == 1) return $arr;

    // 是否有发生数据交换操作，如果一次冒泡中没有发生数据交换操作说明已经有序，可以直接退出冒泡过程
    $flag = true;

    // 冒泡操作
    for ($i = 0; $i < $n; $i++) {
        // $i 是已经排好序的元素个数，-1 是要拿 $arr[$j] 和 $arr[$j + 1] 比较，这样只要到前一个元素就可以处>理完全部数据
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
                $flag = false;
            }
        }

        if (!$flag) break;
    }

    return $arr;
}

var_export(bubble_sort($array));

问题

  1. 冒泡排序是否是原地排序算法？

冒泡的过程中，只有相邻数据位置互换，不需要开辟新的空间来进行操作，所以是原地排序算法。

  1. 冒泡排序是否是稳定的算法？

冒泡过程中，我们只在 $arr[$j] > $arr[$j + 1] 的时候，才互换位置，相等的两个元素，位置不会变动，所以是稳定的算法。

  1. 冒泡排序的时间复杂度是多少?

最好的情况下，数组已经有序，只需要进行一次冒泡即可，时间复杂度是 O(n)。

最坏的情况下，完全逆序，冒泡过程总遍历次数为 (n - 1) + (n - 2) + ... + 1，也就是 n*(n-1)/2，所以时间复杂度是 O(n²)。

插入排序

先看一个简单的问题。一个有序的数组，我们往里面添加一个新的数据后，如何继续保持数据有序呢？很简单，我们只要遍历数组，找到数据应该插入的位置将其插入即可。我们可以通过这种方法保持集合中的数据一直有序。

插入排序的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

在插入排序中，我们会将数据列表划分为两个部分，一部分是有序区间，另一部分是无序区间。插入排序的过程就是，遍历无序区间里面的每一个元素，在有序区间里面遍历找到一个合适的位置进行插入，直到无序区间的数据全部插入到有序区间里面，这个时候数据列表就完全有序了。

初始状态下，一般会将第一个元素 $arr[0] 视作有序区间，然后 $arr[1...n-1] 为无序区间，我们会遍历 $arr[1...n-1] 中的每一个元素，拿来插入到有序区间中，直到遍历完无序区间的全部数据。

例子

假设要对一组数据排序（数组）：4，5，6，3，2，1，按顺序排序。

开始的时候，我们的有序区间是 $arr[0...0]，无序区间是 $arr[1...n-1]。

第一次遍历，我们拿到无序区间的第一个元素 5($arr[1])，将其与 4 对比，5 > 4，所以位置不变，因为有序区间只有一个元素，所以此次遍历结束。但是此时有序区间已经是 $arr[0...1]，无序区间是 $arr[2...n-1]。

第二次遍历，我们拿到无序区间的第一个元素 6($arr[2])，我们将其与有序区间的最后一个元素，也就是 5 对比，发现 6 比 5 大，是有序区间最大的元素，所以此次遍历结束。但是此时有序区间已经是 $arr[0...2]，无序区间是 $arr[3...n-1]。

我们这里是从有序区间的最后一个元素开始对比，但从有序区间第一个元素开始对比也是可以的。只是操作上稍有不同，如果从第一个元素开始对比，在我们找到合适的位置的时候，需要先将有序区间剩余的元素往后挪动即可。但是需要注意这种情况下对结果稳定性的影响，也就是说，这种情况下，我们比较的时候需要使用 >= 或 <= 这种包含相等情况的也进行位置互换操作。这样才能保证排序结果的稳定性。

如此遍历，直到无序区间的元素被全部遍历完毕。

PHP 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function insertion_sort($arr)
{
    $n = count($arr);
    if ($n <= 1) return $arr;

    // 0~$i-1 为有序区间
    // $i~$n-1 为无序区间
    for ($i = 1; $i < $n; $i++) {
        $value = $arr[$i];
        // 查找插入的位置
        for ($j = $i - 1; $j >= 0; $j--) {
            if ($arr[$j] > $value) {
                $arr[$j + 1] = $arr[$j]; // 数据移动
            } else {
                break;
            }
        }
        // 到这里的时候说明: 1. $arr[$j] <= $value(找到了插入的位置) 或 2. $j = -1 (循环终止，$value 是目前有序区间最小的数)
        $arr[$j + 1] = $value; // 插入数据
    }

    return $arr;
}

var_export(insertion_sort($array));

问题

  1. 插入排序是原地排序算法吗？

在插入排序的过程中，我们并不需要额外的存储空间，所以空间复杂度为 O(1)，也就是说，插入排序是一个原地排序算法。

  1. 插入排序是稳定的排序算法吗?

在插入排序中，对于值相同的元素，我们并不交换位置，可以保持原有的前后顺序不变，所以是稳定的排序算法。

  1. 插入排序的时间复杂度是多少？

最好的情况下，如果数据已经是有序的，我们并不需要移动任何数据，每次只需要比较一次就能确定插入的位置。这种情况下，时间复杂度是 O(n)。注意这里是从尾到头遍历已经有序的数据。

最坏的情况下，数据是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，需要移动数据的次数为 O(n²)，所以最坏情况时间复杂度为 O(n²)。

我们在数组中插入一个数据的平均时间复杂度是 O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n²)。

选择排序

选择排序和插入排序有点类似，在排序的过程中，数据也被划分成有序区间和无序区间。但是选择排序是每次从未排序的区间里面选择最小的元素，将其放到已排序区间的末尾。

PHP 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function selection_sort($arr)
{
    $n = count($arr);
    if ($n <= 1) return $arr;

    for ($i = 0; $i < $n - 1; $i++) {
        // 假设一开始最小的元素都是未排序区间的第一个元素，如果有更小的，则替换
        $min = $arr[$i];
        $minIndex = $i;
        // 选择最小元素，获取其值和下标
        for ($j = $i; $j < $n; $j++) {
            if ($arr[$j] < $min) {
                $min = $arr[$j];
                $minIndex = $j;
            }
        }
        // 将最小的元素跟未排序区间的第一个元素交换
        $arr[$minIndex] = $arr[$i];
        $arr[$i] = $min;
    }

    return $arr;
}

var_export(selection_sort($array));

问题

  1. 选择排序是原地排序算法吗？

在选择排序的过程中，只需要两个变量来存储最小元素的值和最小元素的下标，不需要其他额外的空间，所以是原地排序算法。

  1. 选择排序是稳定的算法吗？

由于每次选择排序会将最小元素跟未排序区间第一个元素互换，这个互换过程会改变原有数据的顺序，所以是不稳定的算法。

  1. 选择排序的时间复杂度是多少?

选择排序所需时间为 n + (n - 1) + ... + 1，即 n(n + 1)/2，所以时间复杂度是 O(n²)。

冒泡和插入时间复杂度一样，为什么插入排序更受欢迎？

因为每一次循环过程中，冒泡排序需要 3 个赋值操作，而插入排序只需要一个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 冒泡排序中数据的交换操作：
if (a[j] > a[j + 1]) { // 交换
    int tmp = a[j];
    a[j] = a[j + 1];
    a[j + 1] = tmp;
    flag = true;
}

// 插入排序中数据的移动操作
if (a[j] > value) {
    a[j + 1] = a[j]; // 数据移动
} else {
    break;
}

所以，虽然冒泡排序和插入排序在时间复杂度上是一样的，都是 O(n²)，但是如果我们希望把性能优化做到机智，那肯定首选插入排序。插入排序的算法思路也有很大的优化空间 => 希尔排序。

小结

冒泡排序、插入排序、选择排序对比

是否是原地排序？ 是否稳定？ 最好 最坏 平均
冒泡排序 是 是 O(n) O(n²) O(n²)
插入排序 是 是 O(n) O(n²) O(n²)
选择排序 是 否 O(n²) O(n²) O(n²)

这三种时间复杂度为 O(n²) 的排序算法中，冒泡排序、选择排序，可能就纯粹停留在理论的层面了，学习的目的也只是为了开拓思维，实际开发中应用并不多，但是插入排序还是挺有用的。有些编程语言的排序函数实现原理会用到插入排序算法。

这三种排序算法，实现代码都非常简单，对于小规模数据的排序，用起来非常高效。但是在大规模数据排序的时候，这个时间复杂度还是稍微有点高，所以更倾向于使用时间复杂度为 O(nlogn) 的排序算法。

Posted on Edited on

在未安装之前替换

  1. 替换 brew 默认源
1
export HOMEBREW_BREW_GIT_REMOTE=https://mirrors.ustc.edu.cn/brew.git
  1. 替换 homebrew/homebrew-core 默认源（中科大源）：
1
export HOMEBREW_CORE_GIT_REMOTE=https://mirrors.ustc.edu.cn/homebrew-core.git

如果想下次启动的时候，还使用这两个源，需要做以下修改：

1
2
3
4
5
6
7
替换brew.git:
cd "$(brew --repo)"
git remote set-url origin https://mirrors.ustc.edu.cn/brew.git

替换homebrew-core.git:
cd "$(brew --repo)/Library/Taps/homebrew/homebrew-core"
git remote set-url origin https://mirrors.ustc.edu.cn/homebrew-core.git

参考链接：

https://lug.ustc.edu.cn/wiki/mirrors/help/brew.git