排序算法
稳定性
能保证排序前两个相等的数在排序后顺序不变, 则是稳定的
好处
排序算法如果是稳定的, 那么从一个键上排序, 然后再从另一个键上排序, 第一个键的结果可以为第二个键排序所用.
稳定性分析
- 冒泡排序: 稳定的
- 相邻两个数两两比较, 相同时一般不会交换, 所以稳定
- 选择排序: 不稳定
- 每次循环找到最小的数, 与当前循环次数下标交换位置, 会将原位置的数替换过来, 所以是不稳定的
- 插入排序: 稳定的
- 每个元素往前对比, 比左边小则交换, 否则停止, 遇到相同的数时不会交换, 所以稳定
- 快速排序: 不稳定
- 分为 left, right 时, 与指标相同的数可能被分到左边, 也可能分到右边, 导致顺序变更
- 优化
- 用于比较值的选取, 可以取开始, 中间, 结尾三个数进行比较, 然后取中间值作为比较值
- 处理重复元素问题: 可以将数据分为三块, 比p小, 等于p, 比p大
- 处理小数组效率, 小数组用选择排序来排序
- 用循环代替递归
- 并行计算
- 归并排序: 稳定的
- 希尔排序: 不稳定的
- 堆排序: 不稳定
- 初始化建堆时间复杂度: O(n)
- 更改元素后重建堆时间: O(nLogN)
- 原地排序空间复杂度: O(1)
- 插入删除元素的时间复杂度都是: O(logN)
外排序有哪些
- 归并排序
- 桶排序
- 堆排序
常见外排序用途
- 学生成绩, 年龄等小范围数量有限的: 使用计数排序
- 随机数: 归并排序
- d位数, 每个数位有k个取值: 基数排序
- 被排序数在某个范围内, 且服从均匀分布: 桶排序
流程
假设: 1G数据, 100m内存
- 读入 100m 至数据内, 使用外排序在内存中完成排序
- 将排序完成的数据写入磁盘
- 重复步骤1, 2直到所有数据都存入了不同的 100m 的块 (临时文件中)
- 读入每个临时文件(顺串)的前 10m 的数据放到内存中的输入缓冲取, 最后的 10m 作为输出缓冲区.
- [多路合并, 提高效率]执行10路归并算法, 将结果输出到缓冲区中, 一旦缓冲区满, 将缓冲区中的数据写到目标文件, 清空缓冲区, 一旦10个输入缓冲区中的一个变空, 就从这个缓冲区关联的文件中读入下一个10m数据,除非这个文件已经读完.
优化
- 并行计算
- 多磁盘处理数据, 加快磁盘读写速度
- 使用多线程处理, 利用多核心
- 异步输入输出, 可以同时排序和归并, 同时是读写
- 多台计算机分担计算任务
- 提高硬件速度
- 增加内存, 减小磁盘读写速度, 减小归并次数
- 使用快速的外存设备, 比如固态
- 使用更多核心 CPU
- 提高软件速度
- 对于特殊的数据, 在第一步中使用特定的排序算法
- 压缩输入输出文件和临时文件
排序算法
快排
思路: 在数组中选择一个数作为比较数p, 然后双指针指向数组左右 l, r, r从右向左遍历, 找到第一个比 p 小的数, l 从左向右遍历, 找到第一个比 p 大的数, 找到后交换 l, r 的值. 当 l >= r 时, 交换 p 和 l, 一趟排序完成. 然后递归排序 [start, l-1), (l+1, end]. 递归完成则排序完成.
代码:
func quickSort(arr []int, start, end int) {
if start >= end {
return
}
// 取比较点
p := arr[start]
l, r := start, end
for l < r {
// 先从右侧找小于p的数,
for l < r && arr[r] >= p {
r--
}
for l < r && arr[l] <= p {
l++
}
if l < r {
arr[l], arr[r] = arr[r], arr[l]
}
}
arr[l], arr[start] = arr[start], arr[l]
quickSort(arr, start, l-1)
quickSort(arr, l+1, end)
}