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