Sorting
冒泡排序
插入排序
计数排序
Counting sort，牺牲内存空间来换取低时间复杂度的算法
基础版
- 找出待排序的数组中最大值
- 统计数组中每个值为 i 的元素出现的次数，存入计数数组 C 的第 i 项
优化版
基础版能够解决一般的情况，但是它拥有空间浪费的缺陷。
- 比如一组数据 {101, 109, 108, 102, 110, 107, 103}，按照基础版则需要创建一个长度为 111 的计数数组，但是前面的 [0, 100] 的空间根本没有使用
- 即不仅要找出最大值，还要找出最小值，根据两者的差来确定计数数组的长度
进阶版
进行累加操作，使计数数组存储的元素值，等于原始数组中相应元素的最终排序位置
例如：arr = [5, 3, 1, 1]
计数后： count = [2, 0, 1, 0, 1]
累加后： count = [2, 2, 3, 3, 4]
原数组元素 | 1 | 3 | 5 | ||
Count | 2 | 3 | 4 |
- 倒序遍历会更稳定（待补充）
即目标数组
- 第 2 项 是 1
- 第 3 项 是 3
- 第 4 项 是 5
归并排序
Merge sort
共有 个数
Divide
- 第一层，分为 2 个子区间
- 第二层，分为 4 个子区间
- 第三层，分为 8 个子区间 …
Conquer
- 在第 层（最底层），每个子区间的长度为 1，共 个子区间，每相邻两个子区间进行合并，总共合并 次 …
这个时间复杂度是稳定的，不随需要排序的序列不同而产生波动。
快速排序
Quick sort
参考视频
- 快速排序算法不检查输入数组是否有序，它始终尝试对其进行排序。
- 比如数据（局部）有序或者数字完全相同等
一些特殊情况中，数组不会被分成两半，而是拥有一个空的子数组。
- 最好的情况：每次选的 pivot 几乎能把数据均分成两半，这样递归树的深度是 ，快排的时间复杂度为
- 最坏的情况：每次找的 pivot 将数组分成两部分，其中有一部分是空，这样递归树就变成了一棵倾斜的树。树的深度为 ，快排的时间复杂度变成 。
- 解决方法：选 pivot 的时候随机选，而不是每次选第一个或者最后一个。
- 平均情况：
步骤
- 从数组中随意选择一个基准元素 (pivot element) （假设取第一个）
- 设置左右两个指针
- 一个从最右边开始往左找比基准值小的数（右边先走）
- 一个从最左边开始往右找比基准值大的数
- 找到后将它们指向的数字进行交换
- 即比基准数小的元素放左边，大的放右边
- 不断重复前两步，直到左右指针相遇（left>=righ）
- 停下来之后，将当前指针的位置与这一轮基准数进行交换，并重新设置基准数
相关代码
课件选择最后一个为 privot
快速选择
基于快速排序的算法：在数组中快速找到一个排名第 k 大或者第 k 小的元素
- 法一：进行完整的快速排序过程（代码和上方相同）
- （第 k 大）升序排序后，输出
nums[nums.length - k]
- 法二：没必要进行整体的排序，只需要找到满足条件的元素即可
- 参数选择
right=k，输出nums[k]