排序算法

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

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

什么是数据结构

就是数据的结构。

一般来说是这样的：

1. 我们要解决一个跟数据相关的问题
2. 分析这个问题，想出对应的数据结构
3. 分析数据结构，想出算法

数据结构和算法是互相依存、不可分开的
你学习完排序算法，就能了解常见的数据结构

大分类

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

我们前端主要使用分治法——分而治之。

排序算法

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

1. 体育委员两两摸头法（冒泡排序）
2. 体育老师一指禅法（选择排序）
3. 起扑克牌法（插入排序）
4. 强迫症收扑克牌法（基数排序）
5. 快排
6. 归并排序
7. 堆排序

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

排序算法

1. 冒泡

其实基本思想就是逐个的比较：
外层循环，从最大值开始递减，因为内层是两两比较，因此最外层当>=2时即可停止；
内层是两两比较，从0开始，比较inner与inner+1，因此，临界条件是inner<outer -1

function bubleSort(arr) {
    var len = arr.length;
    for (let outer = len ; outer >= 2; outer--) {
        for(let inner = 0; inner <=outer - 1; inner++) {
            if(arr[inner] > arr[inner + 1]) {
                [arr[inner],arr[inner+1]] = [arr[inner+1],arr[inner]]
            }
        }
    }
    return arr;
}

2. 选择排序

外层循环的i表示第几轮，arr[i]就表示当前轮次最靠前(小)的位置；
内层从i开始，依次往后数，找到比开头小的，互换位置即可

function selectSort(arr) {
    var len = arr.length;
    for(let i = 0 ;i < len - 1; i++) {
        for(let j = i ; j<len; j++) {
            if(arr[j] < arr[i]) {
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr
}

3. 插入排序

1. i是外循环，依次把后面的数插入前面的有序序列中，默认arr[0]为有序的，i就从1开始
2. j进来后，依次与前面队列的数进行比较，因为前面的序列是有序的，因此只需要循环比较、交换即可
3. 注意这里的break，因为前面是都是有序的序列，所以如果当前要插入的值arr[j]大于或等于arr[j-1]，则无需继续比较，直接下一次循环就可以了。

function insertSort(arr) {
    for(let i = 1; i < arr.length; i++) {  //外循环从1开始，默认arr[0]是有序段
        for(let j = i; j > 0; j--) {  //j = i,将arr[j]依次插入有序段中
            if(arr[j] < arr[j-1]) {
                [arr[j],arr[j-1]] = [arr[j-1],arr[j]];
            } else {
                break;
            }
        }
    }
    return arr;
}

4. 快速排序

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;  //递归出口
    }
    var left = [],
        right = [],
        current = arr.splice(0,1); //注意splice后，数组长度少了一个
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < current) {
            left.push(arr[i])  //放在左边
        } else {
            right.push(arr[i]) //放在右边
        }
    }
    return quickSort(left).concat(current,quickSort(right)); //递归
}

辅助记忆

• 时间复杂度记忆

  • 冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)(一遍找元素O(n)，一遍找位置O(n)）
  • 快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)(一遍找元素O(n)，一遍找位置O(logn))

• 稳定性记忆-“快希选堆”（快牺牲稳定性）