sort
冒泡排序 (bubble sort)
算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
复杂度
| 复杂度 | 值 |
|---|---|
| 最好 | O(n) |
| 最坏 | O(n^2) |
| 平均 | O(n^2) |
插入排序 (insert sort)
算法步骤
- 从第一个元素开始,作为初始排序元素
- 取下一个元素和第一个元素比较后,若数值更大向后插入
- 后续元素和以排序数组元素比较,插入对应位置
- 重复上述步骤返回结果
复杂度
| 复杂度 | 值 |
|---|---|
| 最好 | O(n) |
| 最坏 | O(n^2) |
| 平均 | O(n^2) |
选择排序 (Selection sort)
算法步骤
- 从未排序的元素中找出最小值,放入数组最前面
- 遍历剩余未排序元素将最小的元素插入第二个位置
- 重复上述步骤
复杂度
| 复杂度 | 值 |
|---|---|
| 最好 | O(n) |
| 最坏 | O(n^2) |
| 平均 | O(n^2) |
归并排序 (merge sort)
算法步骤
归并算法分为两部分
- 拆分
- 从元数组中间分割为两个子数组进行排序
- 重复步骤一
- 合并
- 比较两个子数组 a[0],b[0],取小的值放入新数组 c[0],假设 a[0] 为包含较小值的数组
- 比较 a[1],b[0],取小的值放入新数组 c[1]
- 重复上述步骤知道遍历完一个子数组
- 将剩余元素放入 c 数组中
- 重复步骤 1-4 直到合并结束
复杂度
| 复杂度 | 值 |
|---|---|
| 最好 | O(n) |
| 最坏 | O(n^2) |
| 平均 | O(n^2) |
快速排序 (quick sort)
算法步骤
- 选取数组 a 中任一项为分区点,这里默认取第一项,a[0]
- 遍历数组 a,小于数组 a[0],放入数组 b,大于等于则元素放入数组 c
- 对数组 b,c 重复步骤 1,2
- 返回数组 b,a,c 的合并结果
复杂度
| 复杂度 | 值 |
|---|---|
| 最好 | O(n) |
| 最坏 | O(n^2) |
| 平均 | O(n^2) |
桶排序 (bucket sort)
算法步骤
- 将数组 a 按照范围区间分割为一系列子数组 b,c,d
- 对 b,c,d 采用快速排序
- 按照顺序组合结果
复杂度
| 复杂度 | 值 |
|---|---|
| 最好 | O(n) |
| 最坏 | O(n^2) |
| 平均 | O(n^2) |
计数排序 (counting sort)
算法步骤
思想类似桶排序,但区间粒度更细,单一元素作为一个区间,适用于 区间范围狭小且固定,但数据量巨大的场景
- 按照区间范围,将每个单一元素拆分为一个数组容器
- 遍历数组,存入对应元素的数组
- 合并所有离散数组即可
复杂度
| 复杂度 | 值 |
|---|---|
| 最好 | O(n) |
| 最坏 | O(n^2) |
| 平均 | O(n^2) |