一、衡量算法的指标

1. 时间复杂度

大致估计算法执行时间的量级。

master公式计算递归复杂度，只适用于子问题规模一致，用到时直接百度公式

2. 空间复杂度

大致估计算法执行所需内存空间的量级

3. 对数器

使用最笨方法实现一个最基本的算法，作为对数器，来校验算法是否正确。

二、排序算法

1. 如何分类

a. 是否基于元素之间的比较进行排序

- 基于比较的排序：插入、冒泡、归并等
- 不基于比较的排序：桶排序，基数排序

b. 排序后是否稳定【排序后相等元素仍保持其原有顺序】

• 简单判断：看相等元素是否在比较过程中被其他元素交换位置。不稳定的排序交换量很大。

  • 比较排序：比较过程中，小就交换，前面的相等元素在和后面相等元素的后面较小元素交换掉位置。
  • 插入排序：相等元素比较时不交换就可保证稳定性
  • 冒泡排序：相等元素比较时不交换就可保证稳定性
  • 归并排序：相等元素比较时不交换就可保证稳定性
  • 快速排序：等于区收集过程中就会出现不稳定

• 稳定的：

• 不稳定的：

c. 排序时间复杂度是否线性【排序时间复杂度的类型，线性，指数型】

d. 是否需要额外的内存空间

• 不需要：
• 常数额外空间：
• n额外空间：

2. 排序算法

怎样才能非常熟练的掌握所有排序算法？大量的输出，反复输出，直到可以下意识的说出所有排序算法的实现流程、复杂度及优缺点。

很详细的一份讲解文档：https://javaguide.cn/cs-basics/algorithms/10-classical-sorting-algorithms.html

0. 排序是什么

排序，将一组数据按大小重排，过程中元素之间可以相互比较，也可以不比较按照定下的标准坑位去填。

在排序过程有的需要额外的内存空间来用于交换位置或比较。

排完后，相等元素的顺序是可以保持不变的，这样的稳定性可用于商品的多条件筛选。

排序算法非常简单的理解方法：将数据划分为已排序区，未排序区，注意好边界情况即可。

1. 选择排序

• 由左往右排序，已排序区 | 未排序区，待排序元素和后面所有元素比较，选出最小元素加入到已排序区。循环遍历选择，直到结束。
• 为什么叫选择排序，排序过程中是选择最小元素加入到已排序区的。
• O(n^2)
• 需要1个临时变量用于元素比较后的交换。 O(1)
• 不是稳定的，在选择最小元素的过程中，前面的相等元素会通过比较被换到后面。
  • 未排序区选出下一个排序元素的过程需要所有元素的参与，且相等元素之间没有直接的比较，所以无法固定下相等元素的位置关系。
• 总结：
  • 算法步骤：未排序区中所有元素相互比较，获得最小元素加入排序区。
  • 时间复杂度：O(N^2)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 是否基于比较的排序：是

2. 插入排序

• 由左向右排序，已排序区 | 未排序区，未排序区的第一个元素从右往左与已排序区元素遍历比较，小则交换，大则结束，即为已放到合适位置。循环比较然后插入，直到结束。
• 为什么叫插入排序，数据是插入到排序区的。
• O(n^2)
• 需要1个临时变量用于元素比较后的交换。 O(1)
• 相等的元素不交换，是稳定的
  • 未排序区选出下一个排序元素的过程只需要一个元素参与
• 总结：
  • 算法步骤：未排序区的第一个元素和排序区的所有元素比较，确立该元素在排序区的位置。
  • 时间复杂度：O(N^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 是否基于比较的排序：是

3. 冒泡排序

• 由右向左排序，未排序区 | 已排序区，在未排序区内，相邻元素比较，大的往后换，直到最后，后面的值即为有序区。循环比较然后交换，直到结束。
• 为什么叫冒泡排序，每次遍历过程，总会将最大元素换到最后，向水泡浮上来的过程。
• O(n^2)
• 需要1个临时变量用于元素比较后的交换。 O(1)
• 相等的元素不交换，是稳定的
  • 未排序区选出下一个排序元素的过程需要所有元素的参与，且相等元素之间有直接的比较，所以可以固定下相等元素的位置关系。
• 总结：
  • 算法步骤：未排序区每个元素参与比较，将最大的加入有序区。
  • 时间复杂度：O(N^2)
  • 空间复杂度：O(1)
  • 稳定性：稳定
  • 是否基于比较的排序：是

4. 归并排序

• 当一个集合只有一个元素时，这个集合就是已排好序的集合了。
• 将未排序集合二分，然后将排好序的二分合并起来。二分和排序的过程需要递归实现。最后合并完成后就排好序了。
• 为什么叫归并排序，排序的重点在于将两个有序部分合并起来，所以叫归并排序（Merge Sort）。
• O(n*logn)
• 总结：
  • 算法步骤：归并排序重点在合并。分治思想化大为小，小的排好序，再合并起来，最终达到整个数组排好序。
  • 时间复杂度：O(N*logN)
  • 空间复杂度：O(N)
  • 稳定性：稳定
  • 是否基于比较的排序：是

5. 快速排序

• 选择一个元素作为基准，将所有元素划分为小于区，等于区，大于区，然后在小于区、大于区中做递归。
• 为什么叫快速排序，快速排序是在归并排序的基础上说的，快排不需要归并排序的归并过程，所以快。
  • 归并排序两个子数组之间的大小是不确定的需要合并时再次比较排序
  • 而快速排序，两个子元素大小已确定，合并时无需再排序
• O(n*logn)
• 总结：
  • 算法步骤：随机取一个元素作为标准，划分为小于区，等于区，大于区，等于区的位置都是已排好序的元素。遍历递归所有小于区、大于区，使其所有变为等于区时，就排好序了。
  • 时间复杂度：O(N*logN)
  • 空间复杂度：O(logN)
  • 稳定性：不稳定
  • 是否基于比较的排序：是

6. 堆排序

• 基于大根堆或小根堆实现排序
• 总结：
  • 算法步骤：取出根节点加入排序区，然后将堆尾元素放到根位置，调整堆再次为大根堆。重复上面步骤，直到堆为空。
  • 时间复杂度：O(N*logN)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 是否基于比较的排序：是

7. 桶排序

• 桶是一种容器，对数据要求较高
• 总结：
  • 算法步骤：计数排序的升级版，使用映射函数将数据映射到桶上，然后和计数排序一样的步骤。
  • 是否基于比较的排序：否

8. 计数排序

• 数据范围限制：整数
• 总结：
  • 算法步骤：设置计数标准，每个标准就是一个桶，遍历数组，对应桶记录个数，最后依次拿出对应个数的桶，就是排序好的数组
  • 时间复杂度：O(N)
  • 空间复杂度：O(M)
  • 稳定性：稳定
  • 是否基于比较的排序：否

9. 基数排序

• 数据范围限制：非负的十进制数
• 总结：
  • 算法步骤：准备十个桶，所有数据比较低位数进桶，然后按桶顺序出桶，再比较高一位的位数进桶，然后再按桶顺序出桶。循环直至遍历完最高位，最后就是排序号的数组。
  • 时间复杂度：O(N)
  • 空间复杂度：O(N)
  • 稳定性：稳定
  • 是否基于比较的排序：否

10. 希尔排序

• 是插入排序改进后的版本，更高效
• 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。
• 总结：
  • 算法步骤：分割子数组，子数组插入排序，然后整个数组再插入排序。
  • 时间复杂度：O(N*logN)
  • 空间复杂度：O(1)
  • 稳定性：不稳定
  • 是否基于比较的排序：是