什么是算法

算法

以下是高德纳在他的著作《计算机程序设计艺术》里对算法的特征归纳：

输入：一个算法必须有零个或以上输入量。
输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。
明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确地匹配要求或期望，通常要求实际运行结果是确定的。
有限性：依据图灵的定义，一个算法是能够被任何图灵完备系统模拟的一串运算，而图灵机只有有限个状态、有限个输入符号和有限个转移函数（指令）。而一些定义更规定算法必须在有限个步骤内完成任务。
有效性：又称可行性。能够实现，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。

什么是数据结构

就是数据的结构。

一般来说是这样的：

我们要解决一个跟数据相关的问题
分析这个问题，想出对应的数据结构
分析数据结构，想出算法
数据结构和算法是互相依存、不可分开的
你学习完排序算法，就能了解常见的数据结构

大分类

分治法：把一个问题分区成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
动态规划法：当问题的整体最优解就是由局部最优解组成的时候，经常采用的一种方法。
贪婪算法：常见的近似求解思路。当问题的整体最优解不是（或无法证明是）由局部最优解组成，且对解的最优性没有要求的时候，可以采用的一种方法。
线性规划法：见词条。
简并法：把一个问题通过逻辑或数学推理，简化成与之等价或者近似的、相对简单的模型，进而求解的方法。
我们前端主要使用分治法——分而治之。

排序算法

中国学生学不好排序算法主要是因为这些算法的名字是外国人取的

体育委员两两摸头法（冒泡排序）
体育老师一指禅法（选择排序）
起扑克牌法（插入排序）
强迫症收扑克牌法（计数排序，直播的时候说成了『基数排序』，抱歉）
快排
归并排序
堆排序

排序可视化：https://visualgo.net/bn/sorting

冒泡排序

const arr = [234,5,6,7,23,34,5432,6,76,23,432,342,6,234,234]
for (let i=0;i<arr.length-1;i++) {
  if (arr[i] > arr[i+1]) {
    [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
  }
}

console.log(arr)

将每一项与后一项对比，一轮即可找出最大的一项并放到最后。

const arr = [234,5,6,7,23,34,5432,6,76,23,432,342,6,234,234]

for (let j=0;j<arr.length-1;j++) {
  for (let i=0;i<arr.length-1;i++) {
    if (arr[i] > arr[i+1]) {
      [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
    }
  }
}

console.log(arr)

遍历 arr.length - 1 轮即可完成排序，但是每次遍历以后都能确定一个最大值，所以每轮底下的比较长度需要剪短，即：i < arr.length - 1 - j

const arr = [234,5,6,7,23,34,5432,6,76,23,432,342,6,234,234]

for (let j=0;j<arr.length-1;j++) {
  for (let i=0;i<arr.length-1- j;i++) {
    if (arr[i] > arr[i+1]) {
      [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
    }
  }
}

console.log(arr)

计数排序

快，但费内存

const arr = [234,5,6,7,23,34,5432,6,76,23,432,342,6,234,234]
const inputArr = [] // 输入
arr.map(v => inputArr[v] ? (inputArr[v] += 1) : (inputArr[v] = 1))
const output = [] // 输出
inputArr.map((v,i) => [...Array(v)].map(() => output.push(i)))
console.log(output)

桶排序

相比计数排序，一个桶放更多数字

arr = [12,21,6,6,33,34,2,0,2]
计数: {
  0: 1,
  2: 2,
  6: 2,
  12: 1,
  21: 1,
  33: 1,
  34: 1
}
桶: {
  1: [6,6,2,0,2], // 小于10的一个桶
  2: [12],
  3: [21],
  4: [33, 34]
}

占用内存更少了，第一个桶里虽然数字多了、还需二次排序，但是可以运用快排的思路（快排为什么快，因为每次比较不用跟所有数字比较，只需要跟部分比较就行）。

基数排序

可以排更大的数字，需要更少的桶
如图，以十进制数字为例：先以数字的个位进行入桶操作，然后出桶，再以数字的十位入桶，出桶，重复操作，最后即可完成排序。

堆排序

先按数组顺序生成二叉树，从右往左（因为只有完全二叉树才能用数组表示）最小的二叉树比较，逐渐生成最大堆。

图片参考

排序算法的时间复杂度和空间复杂度

注：

1 归并排序可以通过手摇算法将空间复杂度降到O(1)，但是时间复杂度会提高。

2 基数排序时间复杂度为O(N*M)，其中N为数据个数，M为数据位数。

辅助记忆

时间复杂度记忆-
冒泡、选择、直接排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)）（一遍找元素O(n)，一遍找位置O(n)）
快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）
稳定性记忆-“快希选堆”（快牺牲稳定性）
排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

算法与数据结构