最前端

算法

# 复杂度

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。

# 时间复杂度

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。

实际计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，因此，另一种更为通用的方法就出来了：「大 O 符号表示法」，即 T(n) = O(f(n))。

举个例子：

for (let i = 1; i <= n; i++) {
    let j = i;
    j++;
}

通过「大 O 符号表示法」，这段代码的时间复杂度为：O(n)，为什么呢？

在 大 O 符号表示法中，时间复杂度的公式是： T(n) = O(f(n))，其中 f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

具体到上面的例子，假设每行代码的执行时间都是一样的，我们用 1 颗粒时间 来表示，那么这个例子的第一行耗时是 1 个颗粒时间，第三行的执行时间是 n 个颗粒时间，第四行的执行时间也是 n 个颗粒时间（第二行和第五行是符号，暂时忽略），那么总时间就是 1 颗粒时间 + n 颗粒时间 + n 颗粒时间 ，即 (1+2n) 个颗粒时间，即：T(n) = (1+2n) * 颗粒时间，从这个结果可以看出，这个算法的耗时是随着 n 的变化而变化，因此，我们可以简化的将这个算法的时间复杂度表示为：T(n) = O(n)。

为什么可以这么去简化呢，因为大 O 符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。

所以上面的例子中，如果 n 无限大的时候，T(n) = time(1+2n) 中的常量 1 就没有意义了，倍数 2 也意义不大。因此直接简化为 T(n) = O(n) 就可以了。

常见的时间复杂度量级有：

  • 常数阶 O(1)
  • 对数阶 O(㏒N)
  • 线性阶 O(n)
  • 线性对数阶 O(n㏒N)
  • 平方阶 O(n²)
  • 立方阶 O(n³)
  • K 次方阶 O(n^k)
  • 指数阶 (2^n)

上面从上至下依次的时间复杂度越来越大，执行的效率越来越低。

# 空间复杂度

既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

空间复杂度比较常用的有：O(1)、O(n)、O(n²)。

# 位运算

位运算在算法中很有用，速度可以比四则运算快很多。

在学习位运算之前应该知道十进制如何转二进制，二进制如何转十进制。这里说明下简单的计算方式

  • 十进制 33 可以看成是 32 + 1，并且 33 应该是六位二进制的（因为 33 近似 32，而 32 是 2 的五次方，所以是六位），那么 十进制 33 就是 100001，只要是 2 的次方，那么就是 1 否则都为 0
  • 那么二进制 100001 同理，首位是 2^5，末位是 2^0，相加得出 33

# 左移 <<

10 << 1 // 10*(2^1) -> 20

左移就是将二进制全部往左移动，10 在二进制中表示为 1010，左移一位后变成 10100，转换为十进制也就是 20，所以基本可以把左移看成以下公式 a * (2 ^ b)。

# 右移 >>

10 >> 1 // -> 5

算数右移就是将二进制全部往右移动并去除多余的右边，10 在二进制中表示为 1010，右移一位后变成 101，转换为十进制也就是 5，所以基本可以把右移看成以下公式 int v = a / (2 ^ b)。

右移很好用，比如可以用在二分算法中取中间值：

13 >> 1 // 13/(2^1) -> 取整 -> 6

# 按位操作

# 按位与

每一位都为 1，结果才为 1

8 & 7 // -> 0
// 1000 & 0111 -> 0000 -> 0

# 按位或

其中一位为 1，结果就是 1

8 | 7 // -> 15
// 1000 | 0111 -> 1111 -> 15

# 按位异或

每一位都不同，结果才为 1

8 ^ 7 // -> 15
8 ^ 8 // -> 0
// 1000 ^ 0111 -> 1111 -> 15
// 1000 ^ 1000 -> 0000 -> 0

从以上代码中可以发现按位异或就是不进位加法。

面试题：两个数不使用四则运算得出和

这道题中可以按位异或，因为按位异或就是不进位加法，8 ^ 8 = 0 如果进位了，就是 16 了，所以我们只需要将两个数进行异或操作，然后进位。那么也就是说两个二进制都是 1 的位置，左边应该有一个进位 1，所以可以得出以下公式 a + b = (a ^ b) + ((a & b) << 1)，然后通过迭代的方式模拟加法：

function sum(a, b) {
    if (a == 0) return b;
    if (b == 0) return a;
    let newA = a ^ b;
    let newB = (a & b) << 1;
    return sum(newA, newB);
}

# 排序算法

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 O(n²) O(n) O(n²) O(1) In-place 稳定
选择排序 O(n²) O(n²) O(n²) O(1) In-place 不稳定
插入排序 O(n²) O(n) O(n²) O(1) In-place 稳定
希尔排序 O(n*㏒n) O(n*㏒²n) O(n*㏒²n) O(1) In-place 不稳定
归并排序 O(n*㏒n) O(n*㏒n) O(n*㏒n) O(n) Out-place 稳定
快速排序 O(n*㏒n) O(n*㏒n) O(n²) O(㏒n) In-place 不稳定
堆排序 O(n*㏒n) O(n*㏒n) O(n*㏒n) O(1) In-place 不稳定
计数排序 O(n+k) O(n+k) O(n+k) O(k) Out-place 稳定
桶排序 O(n+k) O(n+k) O(n²) O(n+k) Out-place 稳定
基数排序 O(n×k) O(n×k) O(n×k) O(n+k) Out-place 稳定

提示

  • In-place: in-place algorithm, 原地算法。是基本上不需要借助额外的数据结构，在解决问题过程中，只开辟了常数量的空间就能对输入的数据进行变换的算法。

  • Out-place: out-place algorithm, 异地算法。不满足「原地」原则，开辟的辅助空间与问题规模有关的算法。

  • 稳定性： 稳定性的意思就是对于相同值来说，相对顺序不发生改变。通俗的讲有两个相同的数 A 和 B，在排序之前 A 在 B 的前面，而经过排序之后，B 跑到了 A 的前面，对于这种情况的发生，我们管他叫做排序的不稳定性。

    稳定性有什么意义？个人理解对于前端来说，比如我们熟知框架中的虚拟 DOM 的比较，我们对一个列表进行渲染，当数据改变后需要比较变化时，不稳定排序或操作将会使本身不需要变化的东西变化，导致重新渲染，带来性能的损耗。

# 冒泡排序

  • 简介：冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢「浮」到数列的顶端。
  • 时间复杂度：O(n²)
  • 实现思路：
    1. 比较相邻的元素，前者比后者大的话，两者交换位置
    2. 对每一对相邻元素做相同操作，从开始第一对到最后一对，这样子最后的元素就是最大元素
    3. 针对 n 个元素重复以上步骤，每次循环排除当前最后一个
    4. 重复步骤 1~3，直到排序完成

冒泡排序可视化

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
                var temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

// test
var arr = [6,48,29,5,41,15,36,26,17,2,43,4,29,30,55];
console.log(bubbleSort(arr)); // [2,4,5,6,15,17,26,29,29,30,36,41,43,48,55]

优化 1：设置一标志性变量 pos，用于记录每趟排序中最后一次进行交换的位置。由于 pos 位置之后的记录均已交换到位，故在进行下一趟排序时只要扫描到 pos 位置即可。

// 优化
function bubbleSort1(arr) {
    var i = arr.length - 1;  // 初始时,最后位置保持不变
    while ( i > 0) {
        var pos = 0; // 每趟开始时，无记录交换
        for (var j = 0; j < i; j++)
            if (arr[j]> arr[j+1]) {
                pos = j; // 记录交换的位置
                var tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1]=tmp;
            }
        i = pos; // 为下一趟排序作准备
     }
     return arr;
}

// test
var arr = [6,48,29,5,41,15,36,26,17,2,43,4,29,30,55];
console.log(bubbleSort1(arr)); // [2,4,5,6,15,17,26,29,29,30,36,41,43,48,55]

优化 2：利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值（最大者和最小者），从而使排序趟数几乎减少了一半。

// 优化
function bubbleSort2(arr) {
    var low = 0;
    var high = arr.length - 1; // 设置变量的初始值
    var tmp, j;
    while (low < high) {
        // 正向冒泡，找到最大者
        for (j = low; j < high; ++j) {
            if (arr[j] > arr[j+1]) {
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
        --high; // 修改 high 值，前移一位


        // 反向冒泡，找到最小者
        for (j = high; j > low; --j) {
            if (arr[j] < arr[j-1]) {
                tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
            }
        }
        ++low; // 修改 low 值，后移一位
    }

    return arr;
}

// test
var arr = [6,48,29,5,41,15,36,26,17,2,43,4,29,30,55];
console.log(bubbleSort2(arr)); // [2,4,5,6,15,17,26,29,29,30,36,41,43,48,55]

# 快速排序

  • 简介：快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
  • 时间复杂度：O(n*㏒n)
  • 实现思路：
    1. 从数列中挑出一个元素，称为「基准」（pivot）
    2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
    3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序

快速排序可视化

// 方法一
function quickSort(arr) {
    // 递归出口就是数组长度为 1
    if (arr.length <= 1) return arr;

    // 获取中间值的索引，使用 Math.floor 向下取整；
    let index = Math.floor(arr.length / 2);
    // 使用 splice 截取中间值，第一个参数为截取的索引，第二个参数为截取的长度；
    // 如果此处使用 `pivot = arr[index]` 那么将会出现无限递归的错误；
    // splice 影响原数组
    let pivot = arr.splice(index, 1)[0],
        left = [],
        right = [];

    for (let i = 0; i < arr.length; i++) {
        if (pivot > arr[i]) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return quickSort(left).concat([pivot], quickSort(right));
}

// test
var arr = [3, 5, 10, 3, 18, 37, 29, 2, 9, 3];
console.log(quickSort(arr));

# 插入排序

  • 简介：插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
  • 时间复杂度：O(n²)
  • 实现思路：
    1. 从第一个元素开始，该元素可以认为已经被排序
    2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
    3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
    4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置
    5. 将新元素插入到该位置后
    6. 重复步骤 2~5

插入排序可视化

function insertionSort(arr) {
    let len = arr.length;

    for (let i = 0; i < len; i++) {
        let key = arr[i];
        let j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }

    return arr;
}

// test
var arr = [10, 2, 23, 75, 0, 19, 15];
console.log(insertionSort(arr));

优化：查找插入位置时使用二分查找的方式

function binaryInsertionSort1(arr) {
    for(var i = 1; i < arr.length; i++) {
        var key = arr[i],
            left = 0,
            right = i - 1;

        while(left <= right) {
            var middle = parseInt((left + right) / 2);
            if(key < arr[middle]) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }

        for(var j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }

        arr[left] = key;
    }

    return arr;
}

// test
var arr = [10, 2, 23, 75, 0, 19, 15];
console.log(insertionSort(arr));

# 希尔排序

  • 简介：希尔排序算法又叫缩小增量排序算法，是一种更高效的插入排序算法。和普通的插入排序算法相比，希尔排序算法减少了移动元素和比较元素大小的次数，从而提高了排序效率。
  • 时间复杂度：O(n*㏒²n)
  • 实现思路：
    1. 将待排序序列划分成多个子序列，使用普通的插入排序算法对每个子序列进行排序
    2. 按照不同的划分标准，重复执行第一步
    3. 使用普通的插入排序算法对整个序列进行排序

希尔排序可视化

function shellSort(arr) {
    let len = arr.length,
        temp,
        gap = 1;

    // 动态定义间隔序列
    while(gap < len/3) {
        gap = gap*3 + 1;
    }

    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (let i = gap; i < len; i++) {
            temp = arr[i];
            for (let j = i - gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

// test
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));

# 选择排序

  • 简介：选择排序（Selection-sort）是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
  • 时间复杂度：O(n²)
  • 实现思路：
    1. 初始状态：无序区为 R[1..n]，有序区为空
    2. 第 i 趟排序 (i=1,2,3...n-1) 开始时，当前有序区和无序区分别为 R[1..i-1] 和 R(i..n。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第 1 个记录 R 交换，使 R[1..i] 和 R[i+1..n) 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区
    3. n-1 趟结束，数组有序化了

选择排序可视化

function selectionSort(array) {
    var len = array.length,
        temp;

    for(var i = 0; i < len - 1; i++) {
        var min = array[i];
        for(var j = i + 1; j < len; j++) {
            if (array[j] < min) {
                temp = min;
                min = array[j];
                array[j] = temp;
            }
        }
        array[i] = min;
    }
    return array;
}

// test
var arr = [10, 2, 23, 75, 0, 19, 15];
console.log(selectionSort(arr));

# 堆排序

  • 简介：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
  • 时间复杂度：O(n*㏒n)
  • 实现思路：
    1. 创建一个堆 H[0...n-1]
    2. 把堆首（最大值）和堆尾互换
    3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置
    4. 重复步骤 2，直到堆的尺寸为 1

堆排序可视化

堆排序可视化 2

let len; // 因为声明的多个函数都需要数据长度，所以把 len 设置成为全局变量

// 建立大顶堆
function buildMaxHeap(arr) {
    len = arr.length;
    for (let i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}

// 堆调整
function heapify(arr, i) {
    let left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function heapSort(arr) {
    buildMaxHeap(arr);

    for (let i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}

// test
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(heapSort(arr));

# 归并排序

  • 简介：归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为 2-路归并。
  • 时间复杂度：O(n*㏒n)
  • 实现思路：
    1. 把长度为 n 的输入序列分成两个长度为 n/2 的子序列
    2. 对这两个子序列分别采用归并排序
    3. 将两个排序好的子序列合并成一个最终的排序序列

归并排序可视化

function mergeSort(arr) {
    let len = arr.length;
    // 子序列少于 2 个时，不再进行分割
    if(len < 2) {
        return arr;
    }
    let middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);

    // 递归，将分割的子序列分别进行排序，然后合并
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

// test
var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));

# 计数排序

  • 简介：计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
  • 时间复杂度：O(n+k)
  • 实现思路：
    1. 遍历统计数组中每个值出现的次数，以值为下标，存入新数组中
    2. 遍历新数组，按下标取出对应的值，计数为几，就按顺序出现几次，结果放入新数组

计数排序可视化

function countSort(arr) {
    let len = arr.length;
    let countArr = [];

    // 以值为下标，存入新数组中
    for(let i = 0; i < len; i++) {
        let index = arr[i];
        countArr[index] = countArr[index] ? countArr[index] + 1 : 1;
    }

    let countLen = countArr.length;
    let resultArr = [];
    // 遍历新数组，取出对应值
    for (let k = 0; k < countLen; k++) {
        if (countArr[k] > 0) {
            resultArr = resultArr.concat(new Array(countArr[k]).fill(k));
        }
    }

    return resultArr;
}

// test
var arr = [34,12,10,4,12,56,26,12,5,4,12];
console.log(countSort(arr));

优化 1：如果待排序的序列范围不是从 0 开始，比如是 500-600 之间取值，这其实只用了 101 个空间，这时候如果创建从 0-600 的初始数组，这无疑浪费了 0-499 的空间。所以优化下，只创建 101 个空间大小，第一次遍历时，取出最大和最小值，将 item - min 的值作为下标。

function countSort1(arr) {
    let len = arr.length,
        min = arr[0],
        max = arr[0];

    // 计算出原始数组的最大最小值
    for(let i = 0; i < len; i++) {
        min = min <= arr[i] ? min : arr[i];
        max = max >= arr[i] ? max : arr[i];
    }

    // 计算计数数组的容量
    let countLen = max - min + 1;
    // 创建计数数组，并设置所有数的计数初始值为0
    let countArr = new Array(countLen).fill(0);
    // 遍历初始数组，给对应下标(arr[j] - min)计数加1
    for(let j = 0; j < len; j++) {
        countArr[arr[j] - min]++;
    }

    let resultArr = [];
    // 遍历结果队列的指针
    for (var k = 0; k < countLen; k++) {
        if (countArr[k] > 0) {
            resultArr = resultArr.concat(new Array(countArr[k]).fill(k + min));
        }
    }

    return resultArr;
}

// test
var arr = [34,12,10,4,12,56,26,12,5,4,12];
console.log(countSort1(arr));

优化 2：使用以上计数方式排序后，序列中的相同值，就无法分清它在初始队列中哪个先哪个后出现的了，是一个不稳定的算法。比如：[3,1,2,1]，当计数统计后为：[2,1,1]，那么在 1 位置上的两个 1，最终会变成：[1,1,2,3]，排序后我是分不清之前是哪个 1 先哪个 1 后，如果我希望排序后，不要改变相同元素的相对位置，也就是让它变成一个稳定的算法。

要保持计数排序算法稳定，那么就要使计数数组的计数值即是最后排序结果的下标，这样我们就能基于原数组来进行遍历输出稳定的排序结果。当前计数数组的计数值表示的是原数组元素出现的次数，我们用 arr[i] = arr[i] + arr[i-1] 公式计算即可使计数数组的计数值与结果数组的下标相匹配。

function countSort2(arr) {
    let len = arr.length,
        min = arr[0],
        max = arr[0];

    // 计算出原始数组的最大最小值
    for(let i = 0; i < len; i++) {
        min = min <= arr[i] ? min : arr[i];
        max = max >= arr[i] ? max : arr[i];
    }

    // 计算计数数组的容量
    let countLen = max - min + 1;
    // 创建计数数组，并设置所有数的计数初始值为0
    let countArr = new Array(countLen).fill(0);
    // 遍历初始数组，给对应下标(arr[j] - min)计数加1
    for(let j = 0; j < len; j++) {
        countArr[arr[j] - min]++;
    }

    // 从第 2 个数开始，将后面元素的计数变成与前面所有元素的计数之和
    for(let k = 1; k < countLen; k++) {
        // 加上前一位的计数次数（也就是之前所有元素的计数之和）
        // 使每个值等于最后结果数组的下标
        countArr[k] += countArr[k - 1];
    }

    let resultArr = [];
    // 对初始序列，进行从后往前遍历
    for (let z = len - 1; z >= 0; z--) {
        // 因为下标 0 占了一位，所以下标要减 1
        resultArr[countArr[arr[z] - min] - 1] = arr[z];
        countArr[arr[z] - min]--;
    }

    return resultArr;
}

// test
var arr = [34,12,10,4,12,56,26,12,5,4,12];
console.log(countSort2(arr));

分析：当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 O(n+k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组 countArr 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上 1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

# 桶排序

  • 简介：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。
  • 时间复杂度：O(n+k)
  • 实现思路：
    1. 设置一个定量的数组当作空桶
    2. 遍历输入数据，并且把数据一个一个放到对应的桶里去
    3. 对每个不是空的桶进行排序
    4. 从不是空的桶里把排好序的数据拼接起来

桶排序可视化

/**
 * 桶排序
 * @param  array 数组
 * @param  num   桶的数量
 */
function bucketSort(array, num) {
    if (array.length <= 1) {
        return array;
    }

    let len = array.length,
        buckets = [],
        result = [],
        min = max = array[0],
        regex = '/^[1-9]+[0-9]*$/',
        space,
        n = 0;

    num = num || ((num > 1 && regex.test(num)) ? num : 10);

    for (let i = 1; i < len; i++) {
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
    }

    space = (max - min + 1) / num;
    for (let j = 0; j < len; j++) {
        let index = Math.floor((array[j] - min) / space);
        if (buckets[index]) { // 非空桶，插入排序
            let k = buckets[index].length - 1;
            while (k >= 0 && buckets[index][k] > array[j]) {
                buckets[index][k + 1] = buckets[index][k];
                k--;
            }
            buckets[index][k + 1] = array[j];
        } else { // 空桶，初始化
            buckets[index] = [];
            buckets[index].push(array[j]);
        }
    }

    while (n < num) {
        result = result.concat(buckets[n]);
        n++;
    }

    return result;
}

var arr = [7,36,65,56,33,60,110,42,42,94,59,22,83,84,63,77,67,101];
console.log(bucketSort(arr, 4));

# 基数排序

  • 简介：基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
  • 时间复杂度：O(n*k)
  • 实现思路：
    1. 取得数组中的最大数，并取得位数
    2. arr 为原始数组，从最低位开始取每个位组成 radix 数组
    3. 对 radix 进行计数排序（利用计数排序适用于小范围数的特点）

基数排序可视化

/**
 * 基数排序适用于：
 * 1. 数据范围较小，建议在小于 1000
 * 2. 每个数值都要大于等于 0
 *
 * @param  arr 待排序数组
 * @param  maxDigit 最大位数
 */
function radixSort(arr, maxDigit) {
    let mod = 10;
    let dev = 1;
    let counter = [];

    for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(let j = 0; j < arr.length; j++) {
            let bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]== null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }

        let pos = 0;
        for(let j = 0; j < counter.length; j++) {
            let value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }

    return arr;
}

var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(radixSort(arr, 2));

基数排序有两种方法：

  1. MSD: 从高位开始进行排序
  2. LSD: 从低位开始进行排序

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶
  • 计数排序：每个桶只存储单一键值
  • 桶排序：每个桶存储一定范围的数值

# 系统排序实现

  • 简介：sort() 方法用原地算法对数组的元素进行排序，并返回数组。默认排序顺序是在将元素转换为字符串，然后比较它们的 UTF-16 代码单元值序列时构建的。
  • 时间复杂度：O(n*㏒n)
var arr = [
    { name: '张飞', age: 34 },
    { name: '关羽', age: 30 },
    { name: '刘备', age: 50 }
];

/**
 * 字符排序可以用 A.localeCompare(B) 若 A 大于 B 则返回大于 0 的数字，相等返回 0
 */
arr.sort(function (a, b) {
    if (a.name > b.name) {
        return 1;
    } else if (a.name < b.name) {
        return -1;
    }

    return 0;
    // return a.name.localeCompare(b.name);
});

对于 JS 来说，数组长度大于 10 会采用快排，否则使用插入排序。选择插入排序是因为虽然时间复杂度很差，但是在数据量很小的情况下和 O(n*㏒n) 相差无几，然而插入排序需要的常数时间很小，所以相对别的排序来说更快。

对于 Java 来说，还会考虑内部的元素的类型。对于存储对象的数组来说，会采用稳定性好的算法。稳定性的意思就是对于相同值来说，相对顺序不能改变。

# 参考资料

# 动态规划

动态规划有时为什么被认为是一种与递归相反的技术呢？是因为递归是从顶部开始将问题分解，通过解决掉所有分解出小问题的方式，来解决整个问题。动态规划解决方案从底部开始解决问题，将所有小问题解决掉，然后合并成一个整体解决方案，从而解决掉整个大问题。

使用递归去解决问题虽然简洁，但效率不高。包括 JavaScript 在内的众多语言，不能高效地将递归代码解释为机器代码，尽管写出来的程序简洁，但是执行效率低下。但这并不是说使用递归是件坏事，本质上说，只是那些指令式编程语言和面向对象的编程语言对递归的实现不够完善，因为它们没有将递归作为高级编程的特性。

动态规划三要素：重叠子问题、最优子结构、状态转移方程

# 斐波那契数列

斐波那契数列就是从 0 和 1 开始，后面的数都是前两个数之和：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89....

那么显然易见，我们可以通过递归的方式来完成求解斐波那契数列：

function fibo(n) {
    if (n < 2 && n >= 0) return n;
    return fibo(n - 1) + fibo(n - 2);
}

// test
fibo(10);

以上代码已经可以完美的解决问题。但是以上解法却存在很严重的性能问题，当 n 越大的时候，需要的时间是指数增长的，这时候就可以通过动态规划来解决这个问题。

动态规划的本质其实就是两点：

  1. 自底向上分解子问题
  2. 通过变量存储已经计算过的解

根据上面两点，我们的斐波那契数列的动态规划思路也就出来了：

  1. 斐波那契数列从 0 和 1 开始，那么这就是这个子问题的最底层
  2. 通过数组来存储每一位所对应的斐波那契数列的值
function fibo(n) {
    let array = new Array(n + 1).fill(null);

    array[0] = 0;
    array[1] = 1;

    for (let i = 2; i <= n; i++) {
        array[i] = array[i - 1] + array[i - 2];
    }

    return array[n];
}

// test
fibo(10);

更进一步，这里的数组可以去掉，换做局部变量来实现可以省下不少内存空间：

function fibo (n) {
    if (n <= 1) return n;

    let result,
        a = 0,
        b = 1;

    for (let i = 2; i <= n; i++) {
        result = a + b;
        a = b;
        b = result;
    }

    return result;
}

// test
fibo(10);

甚至，可以再节省一个变量：

function fibo (n) {
    if (n <= 1) return n;

    let a = 0,
        b = 1;

    for (let i = 2; i <= n; i++) {
        b = a + b;
        a = b - a;
    }

    return b;
}

// test
fibo(10);

# 爬楼梯问题

题目具体说明可查看 LeetCode (opens new window)。爬第 n 阶楼梯的方法数量，等于两部分之和：

  • 爬上 n-1 阶楼梯的方法数量
  • 爬上 n-2 阶楼梯的方法数量

所以，状态转移方程可表示为 dp[i] = dp[i-1] + dp[i-2]:

const climbStairs = function(n) {
    const dp = [];

    // 限制边界
    dp[0] = 1;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }

    return dp[n];
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

在此基础上，我们还可以通过压缩空间来对算法进行优化。因为 dp[i] 只与 dp[i-1] 和 dp[i-2] 有关，没有必要存储所有出现过的 dp 项，只用两个临时变量去存储这两个状态即可：

const climbStairs = function(n) {
    let a1 = 1;
    let a2 = 1;
    for (let i = 2; i <= n; i++) {
        // const temp = a2;
        // a2 = a1 + a2;
        // a1 = temp;
        [a1, a2] = [a2, a1 + a2];
    }
    return a2;
}

# 0-1 背包问题

# 最长递增子序列

题目具体说明可查看 LeetCode (opens new window)。

我们可以将状态 dp[i] 定义为以 nums[i] 这个数结尾（一定包括 nums[i]）的最长递增子序列的长度，并将 dp[i] 初始化为 1，因为每个元素都是一个单独的子序列。

定义状态转移方程：

  • 当我们遍历 nums[i] 时，需要同时对比已经遍历过的 nums[j]
  • 如果 nums[i] > nums[j]，nums[i] 就可以加入到序列 nums[j] 的最后，长度就是 dp[j] + 1

注：(0 <= j < i) (nums[j] < nums[i])

const lengthOfLIS = function(nums) {
    let n = nums.length;
    if (n == 0) {
        return 0;
    }
    let dp = new Array(n).fill(1);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Math.max(...dp);
}
  • 时间复杂度：O(n²)
  • 空间复杂度：O(n)

# 参考资料

# 贪心算法

<!-- Todo -->

# 约瑟夫环

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号 1, 2, 3 ... n 分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。

例如：有 10 个人围成一圈进行此游戏，每个人编号为 1-10 。若规定数到 3 的人出圈。则游戏过程如下：

  1. 开始报数，第一个数到 3 的人为 3 号，3 号出圈 1, 2, [3], 4, 5, 6, 7, 8, 9, 10
  2. 从 4 号重新从 1 开始计数，则接下来数到 3 的人为 6 号，6 号出圈 1, 2, [3], 4, 5, [6], 7, 8, 9, 10
  3. 从 7 号重新从 1 开始计数，则接下来数到 3 的人为 9 号，9 号出圈 1, 2, [3], 4, 5, [6], 7, 8, [9], 10
  4. 从 10 号重新从 1 开始计数，由于 10 个人称环形结构，则接下来数到 3 的人为 2 号，2 号出圈 1, [2], [3], 4, 5, [6], 7, 8, [9], 10
  5. 从 4 号重新从 1 开始计数，则接下来数到 3 的人为 7 号，7 号出圈 1, [2], [3], 4, 5, [6], [7], 8, [9], 10
  6. 从 8 号重新从 1 开始计数，则接下来数到 3 的人为 1 号，1 号出圈 [1], [2], [3], 4, 5, [6], [7], 8, [9], 10
  7. 从 4 号重新从 1 开始计数，则接下来数到 3 的人为 8 号，8 号出圈 [1], [2], [3], 4, 5, [6], [7], [8], [9], 10
  8. 从 10 号重新从 1 开始计数，则接下来数到 3 的人为 5 号，5 号出圈 [1], [2], [3], 4, [5], [6], [7], [8], [9], 10
  9. 从 10 号重新从 1 开始计数，则接下来数到 3 的人为 10 号，10 号出圈 [1], [2], [3], 4, [5], [6], [7], [8], [9], [10]
  10. 最终剩余 4 号，4 号为胜利者

# 数组求解

解题思想：用数组求解的基本思想就是用一个一维数组去标识这 n 个人的状态，默认全为 1 ，也就是都在圈子内，当数到 m的人出圈之后，标识置为 0（就是出圈了），同时报数器清 0，下一个人要从 1 开始。在每次报数之前要判断他是否在圈子内（也就是他的标识是否为 1 ），如果在圈子里面才会继续报数。定义一个变量记录出圈的人数， 出圈的人数等于 n-1 时，则游戏结束。

/**
 * @param {number} n 人数
 * @param {number} m 出圈报数
 * @return {number}
 */
function josephRing(n, m) {
    // 当参数不满足条件时，这个游戏无法进行
    if (n <= 1 || m < 1) {
        console.log('you can\'t play Joseph\'s game. n must be bigger than 1, m must be bigger than 0');
        return;
    }

    // 长度为 n 的数组，位置从 0 - n-1，就代表了 n 个人的编号，并将数组所有元素设定为 1 代表未出圈
    let arr = new Array(n).fill(1);
    let count = 0;  // 纪录出圈人数
    let num = 0;    // 报数器

    // 设定循环结束条件：当 count = n-1，即只剩下一个人的时候，游戏结束
    while (count < n - 1) {
        // 第二层循环，循环数组
        for (let i = 0; i < arr.length; i++) {
            // 当这个位置的元素为 1 时，就执行接下来的代码
            if (arr[i] === 1) {
                num++; // 每经过一个元素为 1 的位置时，就让报数器加 1

                // 当报数器等于 m 时，就执行接下来的代码
                if (num === m) {
                    arr[i] = 0; // 让这个位置的元素为 0，表示这个位置已经出圈了
                    count++; // 纪录出圈人数的变量加 1
                    num = 0; // 将报数器清零
                }

                // 当 m = 1 时，只有当 count = n 才会退出第二层循环（for循环），此时数组内的所有元素都变为了 0，为了避免这个问题，必须要有这个 if 判断句，达到特定条件时强制退出
                // 其实当 m = 1 时，结果就是 n，也可以将 m = 1 作为特殊情况来处理，即写在 while 循环以外，如此 m = 1 时就不会进入循环
                if (count === n - 1) {
                    break;
                }
            }
        }
    }

    // 找到数组中元素为 1 的位置，将这个位置输出
    let winner = arr.findIndex(item => item === 1) + 1;
    console.log(`${winner} is the winner`);
}

// test
// test
let start = new Date().getTime();
josephRing(10000, 3);
let end = new Date().getTime()
console.log('====' + (end - start) + '====')

# 动态规划求解

/**
 * @param {number} n 人数
 * @param {number} m 出圈报数
 * @return {number[]}
 */
function josephRing(n, m) {
    if (n <= 1 || m < 1) {
        console.log('you can\'t play Joseph\'s game. n must be bigger than 1, m must be bigger than 0');
        return;
    }

    let r = 0;
    for (let i = 2; i <= n; i++) {
        // 会先计算 n = 2 时的结果，最终得到的 r 就是胜利者
        r = (r + m) % i;
    }
    console.log(r + 1 + ' is the winner.');
}

// test
let start = new Date().getTime();
josephRing(10000, 3);
let end = new Date().getTime()
console.log('====' + (end - start) + '====')

# 参考资料

上次更新: 2024/10/31 08:48:42